Maximal Flow Problem

max-flow min-cut theorem

the maximum amount of flow passing from the source to the sink is equal to the total weight of the edges in a minimum cut
This is a special case of the duality theorem for linear programs

Ford-Fulkerson

Main idea: find valid flow paths until there is none left, and add them up

Flow Decomposition

Any valid flow can be decomposed into flow paths and circulations

correctness

Analysis

Assumption: capacities are integer-valued.

how do we find the min-cut?(use residual graph)

bipartite matching

definition of bipartite:
it is one where the node set V can be partitioned into sets X and Y in such a way that every edge has one end in X and the other end in Y.

example

bipartite matching is in P

There are a variety of polynomial-time algorithms for finding an optimal bipartite matching.
A common algorithm is one that reduces the matching problem into an equivalent max-flow instance

For any bipartitie graph, the maximum size of a matching is equal to the minimum size of a vertex cover.(konig)

duality

dominating set

a dominating set for a graph G is a subset D of its vertices, such that any vertex of G is either in D, or has a neighbor in D.

2-SAT

can be solved in polynomial time

Graph color

2-color

BFS O(m+n)

A graph G is 2-colorable if and only if it is bipartite

3-color is NP-complete

https://web.stanford.edu/class/cs97si/