Unit D

21 Apr 2022

Graph Cuts

• Cut - A partition of a graph $(V, E)$ into two sets $S$ and $V-S$. You either respect or cross the cut

Cut Theorem

• A set of edges $A \subseteq T$, where $T$ is an MST, let $(S, V-S)$ be any cut which $A$ respects. $A \cup {e}$ is also a subset of an MST.

Flow Networks

• Graph $G = (V, E)$
• Source node $s \in V$
• Sink node $t \in V$
• Edge capacities $c(e) \in \mathbb{R}^+$
• Inflow must equal outflow $\forall v \in V - {s, t}$
• Augmenting paths contains only
  • Non-full forward edges
  • Non-empty backward edges
• Bottleneck capacity - edge in augmenting path with lowest capacity

Residual Graphs

• $G_f$ models additional flow that is possible
  • Forward edge - how much flow could I add? $c(e) - f(e)$
  • Backward edge - how much flow could I remove? $f(e)$

Ford-Fulkerson Algorithm

1. Initialize $f(e) = 0$ for all $e \in E$
2. Construct residual network $G_f$
3. While there is an augmenting path $p$ in $G_f$:

• $c$ = bottleneck capacity (may be a difference of $c(e) - f(e)$ at some node, not just $c(e)$ unless it’s the first iteration)
• Add $c$ unit of flows to $G$ based on augmenting path $p$

Number of Iterations?

• Integer-valued capacities, min-weight is 1, number of iterations is bounded by max flow ($

  f^*

  $)

• Rational values - integer capacity, $\approx 2^{32}$
• Irrational values could lead to an infinite loop

Edmonds-Karp Algorithm

Same thing except for step 3 - while there is an augmenting path, let $p$ be the path with the fewest hops. $\Theta(\text{min}(Ef^*, VE^2))$

Showing correctness of Ford-Fulkerson/Showing max flow

• $MaxFlow$ is $\Theta(E*V)$
• Build the cut by ssurrounding the areas when augmenting paths stop
• Sum forward edges that cross the cut

Edge-Disjoint Paths

Reduction - convert vertex-disjoint problem into edge-disjoint by copying each node, one connected to incoming edges and one to outgoing

Maximum bipartite matching (dog lovers and dogs)

Problem statement - a graph $(L, R, E)$

$\Theta(E*V)$

1. Make $G$ into $G’$
2. Compute max flow on $G’$
3. Return $M$ as all ‘middle edges’ with flow 1

MBM is a reduction of MF

Reductions

Easier problem reduces to the harder problem. If $A$ reduces to $B$, we denote this as $A \le_p B$, unless it reduces linearly, in which we denote it $A \le_n B$

Examples

• EDP reduces to MF
• VDP reduces to EDP reduces to MF
• MBM reduces to MF

Runtime

• convert(A->B)
• execute(B) - we want this to be the slow part
• solve(B->A)

Lower bound proofs

We know that if $A \in \Omega(f(n))$ then $B \in \Omega(f(n))$, so $A \le_p B$. Both MIS and MVC are NP-Complete.

Maximum Independent Set (MIS)

$S \subseteq V$ is an independent set if no two nodes in $S$ share an edge

• Convert to decision by saying ‘Can I have a $k$ sized independent set?’

$k$IS

Verification

• Check if size $k$ - $\Theta(V)$
• Check independent set - $\Theta(V^2)$

Generalized Baseball (MinVertCov)

• Fewest number of defenders needed

• Convert to decision by saying ‘Can I have a $k$ sized vertex cover?’

$k$VC

Verification

• Check if size $k$ - $\Theta(V)$
• Check each edge connected to vertex - $\Theta(E)$

Conversion from MIS to MVC

• $S$ is an independent set of $G$ iff $V - S$ is a vertex cover of $G$

Proof

• Consider any edge $E \in V$, there must be only one endpoint of $v_1 \oplus v_2 \in S$, and the other must be in the complement

NP

Solvers reduce to deciders

• NP - Verifiable in polynomial time (requires a certificate, or proposed solution)

NP-Hard

• $B$ is NP-Hard if $\forall A \in NP, A \le_p B$ - every NP/P problem can be reduced to this NP-Hard

P = NP, how to prove

If any NP-hard or NP-complete (which is NP-hard) problem can be solved in polynomial time, then P = NP

NP-Complete

• The ‘hardest’ problems in NP

To prove:

• Prove NP (verifiable in polynomial time)
• Prove NP-hard, show a reduction for every problem in NP or show a reduction from another NP-hard problem.

3-Sat

• NP-Hard
• Given a 3-CNF is there an assignment of true/false to each variable to make the formula true

Reduce to $k$IS

• Create a graph, triangle grpahs of the CNFs, edges connecting each node to its complements in other graphs
• If there’s an independent set