Unit D - Study Guide
21 Apr 2022Flow Networks
- What is an augmenting path?
- Augmenting paths contains only
- Non-full forward edges
- Non-empty backward edges
- What are the residual graph $G_f$ edge equations?
- Forward: $c(e) - f(e)$
- Backward: $f(e)$
- Explain the Ford-Fulkerson algo
- Initialize $f(e) = 0$ for all $e \in E$
- Construct residual network $G_f$, each forward edge set to $c(e)$, and no backward edges (meaning, there is 0 flow you could remove, because we have sent none)
- Continually increase flow by one unit along augmenting path, setting backward edges to $f(e)$ and forward to $c(e) - f(e)$
- How many iterations?
-
Integers - bounded by max flow ($ f^* $), - Rational values - integer capacity, $\approx 2^{32}$
- Irrational values could lead to an infinite loop
- Running time?
-
For integer capacities, $O( f^* * E )$, where $E$ comes from BFS and $ f^* $ b/c bounded by max flow.
- Edmond-karp runtime?
-
$\Theta(\text{min}( f^* * E , V E^2 ))$ = O( V E ^2) - Note there are other algos that can do in diff way but total cubic, like $V^3$ or $V^2 E$
- How did we prove MaxFlow/Ford-Fulkerson?
- Cut theorem
-
Conservation of flow across cut from source to sink requires that $max f \le min_cut$
Maximum bipartite matching (dog lovers and dogs)
-
How do we reduce MBM to MF?
- Make $G$ into $G’$, all edges will now have weight one
- Call max flow on $G’$
-
Return $M$ as all ‘middle edges’ with flow 1
- Runtime of MBM?
-
$\Theta(E*V)$, because Karp does $min$, and $ f \le L$
Reductions
- What are the three parts of a reduction?
convert(A->B)
execute(B)
- we want this to be the slow partsolve(B->A)
Lower bound proofs
- Explain lower bounds for reductions.
We know that if $A \in \Omega(f(n))$ then $B \in \Omega(f(n))$, so $A \le_p B$.
MIS, MVC
- Give the definition of MIS and how it can be converted to a decision problem.
- $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?’ - NP-Complete b/c polynomial verifiable
- How do we convert from MIS to MVC?
- The complement of the independent $S$ is a vertex cover
P, NP, NP-C, NP-H
- What is an NP problem?
- Verifiable in polynomial time
- What is an NP-Hard problem?
- Every problem in NP/P can reduce to it
- What is an NP-Complete problem
- Satisfies verifiability of NP and an NP-Hard/NP-Complete problem reduces to it
- How do we prove P = NP?
- If any NP-H or NP-C problem reduces to a problem in P (can be solved in polynomial time), then P = NP
3-SAT
- What is 3-SAT?
- $OR$s in parentheses, $AND$s connect.
- Is there an assignment of $T$ or $F$ to each variable to make the 3-CNF true?
- NP-Hard
- How does 3-SAT reduce to $k$IS?
- Triangle graphs of the CNFs, connect each variable to its complement
- Is there a $k$ independent set where $k =$ the number of triangles?