Unit D - Study Guide

Flow Networks

  1. What is an augmenting path?
  1. What are the residual graph $G_f$ edge equations?
  1. Explain the Ford-Fulkerson algo
  1. How many iterations?
  1. Running time?
  1. Edmond-karp runtime?
  1. How did we prove MaxFlow/Ford-Fulkerson?

Maximum bipartite matching (dog lovers and dogs)

  1. How do we reduce MBM to MF?

  2. Make $G$ into $G’$, all edges will now have weight one
  3. Call max flow on $G’$
  4. Return $M$ as all ‘middle edges’ with flow 1

  5. Runtime of MBM?

Reductions

  1. What are the three parts of a reduction?

Lower bound proofs

  1. 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

  1. Give the definition of MIS and how it can be converted to a decision problem.
  1. How do we convert from MIS to MVC?

P, NP, NP-C, NP-H

  1. What is an NP problem?
  1. What is an NP-Hard problem?
  1. What is an NP-Complete problem
  1. How do we prove P = NP?

3-SAT

  1. What is 3-SAT?
  1. How does 3-SAT reduce to $k$IS?