Lecture 24: Applications of Overview of Graph Algorithms
Maximum Flow Overview
Given a directed graph with special vertices s and t, find a maximum flow from s to t.
Copyright By PowCoder代写 加微信 powcoder
The flow through each edge (u, v) cannot exceed the capacity of (u, v).
For each node v ∈ V \ {s, t}, the total amount of flow entering v must be equal to the total amount of flow leaving v.
Finding the maximum flow is equivalent to finding the min-cut: i.e., the partition of nodes in two disjoint sets S and T such that sS, tT and the sum of capacities of edges connecting a node in S to a node in T are minimized.
Residual graph.
For every edge (u,v) in the original graph, create an opposite edge (v,u). Initially, the
residual capacity cf(u,v) equals the capacity of (u,v), and cf(v,u)=0.
Let f(u,v) be the flow passing through edge (u, v): c (u,v) decreases by f(u,v) and c (v,u)
increases by f(u,v).
The following Ford Fulkerson Algorithm operates on the residual graph.
Ford Fulkerson Algorithm
Start with ( )=0 for each edge .
Construct Residual Graph Gf for current flow ( )=0 While there exists some s-t path in Gf
Let 𝑓(P) be the maximum amount of flow that can be pushed through P Push 𝑓(P) units of flow along the edges
Construct Gf for new flow f(e)
Integrality property: if all edge capacities are integers, then there exists a max flow for which every flow value is an integer and the F-F algorithm constructs such a flow.
Complexity: Assuming that all capacities are integer, and we choose paths at random, the worst case cost is O(E *), where * is the maximum flow (pseudo-polynomial complexity).
If we choose, shortest paths (in terms of number of edges), the cost is O(VE2).
Applications
The setup can model (surprisingly) many (seemingly) unrelated problems.
The idea is to express the problem as a max flow and then feed individual instances into our max flow solver.
The examples seen below all share the property that they are integer flow problems, e.g., all capacities are integral, so running-time analyses can use Ford-Fulkerson for integral flows.
1. Maximum Bipartite Matching 2. Edge-Disjoint Paths
3. Circulations with Demands
4. Baseball Elimination
Maximum Bipartite Matching
A graph G = (V, E) is Bipartite if there exists partition V = X Y with X ∩ Y = and E X × Y.
A Matching is a subset M E
such that v V at most one edge in M is incident upon v.
The Size |M| is the number of edges in M.
A Maximum Matching is matching M such that
every other matching M′ satisfies |M′ | ≤ M.
Problem: Given bipartite graph G, find a Maximum Matching. Applications: Assign jobs to people, tasks to machines, etc.
Bipartite Matching Example
1-1′, 2-2′, 3-3′ 4-4′
Matching 1-2′, 3-1′, 4-5′
From Bipartite Matching to Flow
Max flow formulation.
Create directed graph .
to , and assign them capacity .
, and unit capacity edges from to each node in .
Direct all edges from
Add source Add target
, and unit capacity edges from each node in 1 1 1′
Maximum Bipartite Matching: Proof of Correctness
Theorem. Max cardinality matching in value of max flow in .
Pf. if max cardinality matching in then max flow in
Given max matching of cardinality .
Consider flow that sends 1 unit along each of the edges.
(s,x), (x,y), (y,t), where (x,y) is an edge in the matching is a flow, and has cardinality .
2 2′ 12 2’1
G5 5′ 5 5’G’
Maximum Bipartite Matching: Proof of Correctness
Theorem. Max matching in
value of max flow in . max cardinality matching in
be a max flow in of value
or for every edge (because of integrality of F-F solution)
computed by Ford-Fulkerson
max flow in then
set of edges from to with .
– each node in and participates in at most one edge in
12 2’1 2 2′
s 3 3′ t 3 3′ 4 4′ 4 4′
Maximum Bipartite matching: Running time
Algorithm:
Run F-F on the constructed graph
Report all original edges from that have flow 1 Correct by analysis on previous page
Correct no matter how augmenting paths are chosen
Running time:
Each iteration increases
Each iteration takes
Specialized algorithms
by 1. time.
. /
[Hopcroft–Karp, 1973]
using matrix multiplication [Mucha-Sankowski, 2004]
[Madry, 2013]
But in practice, they are not as good as using max flow algorithms.
Bipartite Matching : Feasible Schedule Assume n roommates r1,…rn.
For fairness, every day d1,…dn a different roommate is supposed to cook dinner.
However, due to other obligations, some roommates are unable to cook on certain days.
Let Ci,j=true, if ri can cook on day dj.
Describe an algorithm to determine if is possible to have a feasible schedule such that each roommate cooks exactly once during the n days.
Bipartite Matching: Feasible Schedule
Ci,j=true, if ri can cook on day dj.
Describe an algorithm to determine if is possible to have a feasible schedule such
that each roommate cooks exactly once during the n days. Solution: This is a matching problem.
Create bipartite graph in which each roommate r1,…rn and each day d1,…dn are nodes.
Construct edge (ri, dj) iff Ci,j=true.
Add source node s with outgoing edges to all roommates r1,…rn , and terminal node t with incoming edges from all days d1,…dn. Set all edge capacities equal 1.
A feasible schedule exists if and only if r The bipartite graph has a perfect matching, i.e., 1 1 A matching touching every vertex. r2
This happens iff
the max s-t flow has value n.
Bipartite Matching: Balanced Assignment
Your company wishes to assign n customers c1,…cn to k facilities f1,…fk.
Each customer can only be served by some facility in his vicinity:
Ci,j=true means that customer ci can be served by facility fj.
An assignment of customers to facilities is balanced,
if each facility serves the same number n/k of customers (assume that n/k is integer).
Given the constraints Ci,j, describe an algorithm to determine if is possible to construct a balanced assignment
Bipartite Matching: Balanced Assignment
Ci,j=true means that customer ci can be served by facility fj.
Given constraints Ci,j, describe an algorithm to determine if is possible to
construct a balanced assignment
Solution: Create a bipartite graph.
Each customer c1,…cn and each facility f1,…fk are nodes. Edge (ci, fj) exists iff Ci,j=true.
Add source s connected to all customers c1,…cn ,
and terminal node t with incoming edges from all facilities f1,…fk .
All edge capacities = 1,
except for the edges fj whose capacity is n/k.
A balanced assignment exists 1 if and only if s
maximum s-t flow has value n.
Bipartite Matching: Constrained Assignment
Your company now wishes to assign n customers c1,…cn to k facilities f1,…fk.
Each customer can only be served by some facility in his vicinity: Ci,j=true means that customer ci can be served by facility fj
An assignment of customers to facilities is constrained,
so that facility fi can serve ni customers where ni .
Given the constraints Ci,j and the ni, describe an algorithm to determine if is possible to construct a constrained assignment that serves all of the customers and, if such an assignment exists, to construct it.
Bipartite Matching: Constrained Assignment
Ci,j=true means that customer ci can be served by facility fi. Facility fi serves at most ni customers where ni
Describe an algorithm to determine if is possible to construct
a constrained assignment given the constraints Ci,j and values ni
Solution: Create a bipartite graph in which
each customer c1,…cn and each facility f1,…fk are nodes.
Edge (ci, fj) exists iff Ci,j=true. Add
source s with outgoing edges to customers c1,…cn terminal t with incoming edges from all facilities f1,…fk s All edge capacities equal 1, except for the edges
fj whose capacity is ni
A constrained assignment exists
if and only if maximum s-t flow has value n.
Edge Disjoint Paths
Disjoint path problem. Given a directed graph
and two nodes and , find the max number of edge- disjoint s-t paths.
Def. Two paths are edge-disjoint if they have no edge in common.
Application: Communication networks. 25
Edge Disjoint Paths
Max flow formulation: assign unit capacity to every edge. 111
if participates in some path
Theorem. Max number edge-disjoint s-t paths equals max flow value.
Proof. if max number s-t paths then max flow
Suppose there exists edge-disjoint paths
Since paths are edge-disjoint, is a flow of value .
; else set
Edge Disjoint Paths
Max flow formulation: assign unit capacity to every edge. 111
Proof. if max flow
Let be a max flow in
max number s-t paths
of value computed by Ford-Fulkerson
The proof above also provides an algorithm.
or for every edge (integrality property).
Consider any edge with
– By conservation, there exists edge
– Continue to find the next unused edge out of until reaching .
After finding one path, flow value decreases by 1.
Repeat the process times to find edge-disjoint paths.
a number of source vertices number of target vertices
, each with a supply of
Circulation with Demands
Input: A directed connected graph
, in which ;
every edge has a capacity
, each with a demand of
Output: A flow that meets capacity and conservation conditions, and
At each source vertex At each target vertex
capacity demand
Solving Circulation with Demands using
Algorithm:
Add a “super source” and a “super target” . Add an edge from to each with capacity
. Add an edge from each to with capacity .
Compute the max flow .
, then return
; else return “no solution”.
Baseball (Basketball) Elimination
Remaining Against =
Rule: Order teams by the number of wins. Each win is 1 point. There are no ties in the games. Losses are 0 points.
Q: Does Team 4 still have a chance to finish in first place (tie is OK)?
A: No, obviously. Even if it wins last 2 games, it will have 2 points, whereas team 1 has already 3 points.
Basketball Elimination
Remaining Against =
Q: Does Team 4 still have a chance to finish in first place (tie is OK)?
A: No, because
Team 4 has to win both remaining games against team 2 and 3. Team 1 has to lose both remaining games against team 2 and 3. Then 2 and 3 will both have 3 wins.
The game between team 2 and 3 will give one of them one more win.
Baseball Elimination: Definition
One particular team, say
Team has won
Team and still need to play
(without loss of generality) games already
For each remaining game, consider two possible outcomes.
Team has a total of
games, or .
games to play
possible combinations, where
“Yes”, if there is an outcome for each remaining game such that team finishes with the most wins (tie is OK). “No”, if no such possibilities.
Brute-force algorithm:
Baseball Elimination: Formulation
Can team (in this example team 4) finish with most wins?
; and an edge from
; and an edge from it to
2 𝑤 + 𝑟 − 𝑤 t
Assume team wins all remaining games
Flow network construction:
A source and a target
A node for each remaining game with capacity 1
A node for each team
with capacity
All other teams must have
to it has edges to team node and , with capacity 1
1-2 1-3 2-3
team 2 is allowed to win this many more games
game nodes
team nodes
Baseball Elimination: Formulation
Claim: There is a way for team to finish in the first place iff the max flow has value , .
Proof: “ ”: Suppose there is an outcome for each remaining game
such that team finishes the first. First set .
For each remaining game
if wins,set if wins,set
games, so it can send all incoming flow to .1
1-2 1-3 2-3
2 𝑤 + 𝑟 − 𝑤 t
team 2 is allowed to win this many more games
game nodes
team nodes
Baseball Elimination: Formulation
Proof: “ ”: Suppose the max flow has . It must saturate all edges out of .
Look at each game node
must have 1 unit of flow (integrality property):
, let , let
win the game; win the game.
. Exactly one of its outgoing edges
units of flow, each 1
corresponding to one win, so it cannot beat team .
receives 1-2
2-3 game nodes
2 𝑤 + 𝑟 − 𝑤 t
team nodes
team 2 is allowed to win this many more games
Overview of Graph Algorithms
Breadth First Search (BFS)
Starting from node s, BFS visits all nodes reachable from s in increasing order of their distance (number of edges from s)
Cost O(V+E) (O(E) if graph is connected)
Many applications: finding connected components, max flows..
for each vertex −{ }
. ←h;.←∞;.← . ← ;.←0
initialize empty FIFO queue Enqueue( , )
≠Ø do ←Dequeue( )
foreach []
if. =hthen
. ← Enqueue( , )
; . ← . +1; . ←
Depth First Search (DFS)
Starting from node s, DFS recursively visits all nodes reachable from s Cost O(V+E) (O(E) if graph is connected)
Many applications: cycle detection..
for each vertex do .←h;.←
for each vertex do if. =hthen DFS-Visit( )
DFS-Visit( ): .←
for each node in adj list of do if. =hthen
.← DFS-Visit( )
Topological Sort
Given a DAG, generate a topological ordering: a linear ordering of the vertices such that if (u,v) is in the graph, u appears before v in ordering
Cost O(V+E)
Initialize Q to be an empty FIFO queue for each u in V do
if in-degree(u) = 0 then Enqueue(u);
while Q is not empty do u = Dequeue(Q);
for each v in Adj-list of u do
in-degree(v) = in-degree(v)- 1; if in-degree(v) = 0 then
Enqueue(v);
Minimum Spanning Trees
Given a connected, undirected, graph G = (V, E), a spanning tree is an acyclic subset of edges T E that connects all the vertices together.
Assuming G is weighted, we define the cost of a spanning tree T to be the sum of edge weights in the spanning tree
w(T) = (u,v)T w(u,v)
A minimum spanning tree (MST) is a spanning tree of minimum weight.
Prim’s Algorithm: pseudo-code
Kruskal’s Algorithm: idea
We sort the edges in increasing order of their weight
We keep adding edges to the MST provided that the new edge to be added does not create a cycle
We identify cycles using a disjoint-set data structure Initially every node is a set
When we add an edge (u,v), we perform a union of the sets of u and v
We finish when we consider all edges
If u and v are already in the same set, there is a cycle; so the edge is not added to the MST
Kruskal’s Algorithm: pseudo-code
MST-Kruskal (G, s) For each vertex u G
make-set(u) //we create a set that initial only contains u A=
Sort all edges in increasing order of weight For each edge (u,v) in the sorted order
If find-set(u) find-set(v) A= A {(u,v)}
set-union(u,v)
Cost is O(ElogE) = O(ElogV) – same a cost of sorting
Kruskal’s Algorithm: example
Sorted 4 edges:
(d,b), 1 b (a,s), 2
1 (a,d), 2 (a,b), 3
(a,d), 2 b (a,b), 3
1 (s,b), 4 2
2 4 (a,d),2 2 4 (a,b),3 2 4
3 (a,b), 3 (s,b), 4 b (s,b),4 a 3 b
Shortest Paths
Given a graph G = (V, E) with a weight function w, and a path p=
The shortest path from u to v is the path connecting the two vertices that has the minimum weight
All algorithms, except Dijkstra, allow negative weights, but there can be no negative cycle.
Two types of algorithms: (1) single source: find the shortest paths from a source to every other node; (2) all pairs shortest paths
Single Source SPs with Negative Weights: Bellman-Ford Algorithm
Like all SP algorithms it is based on edge relaxation: relaxing an edge (u,v) means that we use the edge in order to find a SP to from s to v that passes through u.
Since, in the worst case the SP may contain up to |V|-1 edges, it suffices to relax all edges |V|-1 times.
Bellman-SP(G,s)
For each node u, set an upper bound d[u] of the distance to s
Initially, d[s]=0, and d[u]= us For i 1 to |V|-1 // executed |V|-1 times
For each edge RELAX(u,v)
RELAX(u,v)
If d[u]+w(u,v) < d[v]
d[v]=d[u]+w(u,v)
Set u to be the predecessor of v
Cost O(EV), which is O(V3) for dense graphs
Single Source SPs in DAGs
If the graph contains no cycles, we just have to relax each edge exactly once. However, when we relax (u,v) to compute the distance of v, we must make sure that the distance of u is final.
To achieve this, we relax edges according to a topological order of the vertices.
DAG-Shortest-Path( , ) topologically sort the vertices of for each vertex
.←∞;.← ;.←0
for each vertex in topological order
for each vertex v in list of if . + (u,v)