Lecture 8a –
Flow networks III: More Applications
The University of Sydney
Page 1
Reductions
A reduction from Problem X to Problem Y is an algorithm of the following form:
Algorithm for X
f(I)
Instance Solution of Y for f(I)
Transform instance of X to instance of Y
Algorithm for Y
Transform solution for Y to a solution for X
Instance of X
I
Solution for I
The University of Sydney
Page 2
Reduction to Max Flow
A reduction from Problem X to Max Flow is an algorithm of the following form:
Instance of X
I
Solution for I
Algorithm for X
Flow Network
G(I)
Max Flow of G(I)
Transform instance of X to instance of Y
Algorithm for Max Flow
Transform solution for Y to a solution for X
The University of Sydney
Page 3
Bipartite Matching
– Input: undirected, bipartite graph G = (L È R, E).
– M Í E is a matching if each node appears in at most one edge
in M.
– Max matching: find a max cardinality matching.
1 1′ 2 2′
3 3′ 4 4′
max matching 1-1′, 2-2′, 3-3‘, 5-5′
5 5′
The University of Sydney L
R Page 4
Bipartite Matching: Reduction to Max Flow
Bipartite Matching Problem
Max Flow Problem
Step 1: Max flow formulation
Step 2: Use a Max flow algo
Step 3: Extract max matching from max flow
Bipartite Matching Solution Max Flow Solution
The University of Sydney
Page 5
Step 1: Max flow formulation
Max flow formulation.
– Create digraph G’ = (L È R È {s, t}, E’ ).
– Direct all edges from L to R, and assign unit capacity.
– Add source s, and unit capacity edges from s to each node in L. – Add sink t, and unit capacity edges from each node in R to t.
G’
1
1 1 1′ 2 2′
3 3′ 4 4′
1
s
t
The University of Sydney
L 5 5′ R
Page 6
Bipartite Matching: Reduction to Max Flow
Bipartite Matching Problem
Max Flow Problem
Step 1: Max flow formulation
Step 2: Use a Max flow algo
Step 3: Extract max matching from max flow
Bipartite Matching Solution Max Flow Solution
The University of Sydney
Page 7
Step 3: Extract Matching from Flow
1 1 1′
2 2′ 12 2’1
G3 3’s33’tG’ 4 4′ 4 4′
5 5′ 5 5′
1 1′
Matching
M = edges from L to R with f(e) = 1
Max flow f
By Integrality of Max Flow, there exists max flow such that each f(e) is 0 or 1.
The University of Sydney
Page 8
Bipartite Matching: Proof of Correctness
1 1 1′
2 2′ 12 2’1
1 1′
G3 3’s33’t 4 4′ 4 4′
5 5′ 5 5′
G’
Matching
M = edges from L to R with f(e) = 1
Max flow f
By Integrality of Max Flow, there exists max flow such that each f(e) is 0 or 1.
(Equivalence) Max cardinality matching in G Û value of max flow in G’. The University of Sydney Page 9
Bipartite Matching: Proof of Correctness
Theorem: Max cardinality matching in G = Max flow in G’. Proof: ≤
– Suppose max matching M has cardinality k.
– Consider a flow f that sends 1 unit along each of the k paths, defined by
the edges in M.
– fisaflow,andithasvaluek.
– Since M is matching, capacity constraints are satisfied ■
1 1 1′
2 2′ 12 2’1
G3 3’s33’tG’ 4 4′ 4 4′
1 1′
The Univers5ity of Sydney 5′ 5 5′ Page 10
Bipartite Matching: Proof of Correctness
Theorem: Max cardinality matching in G = Max flow in G’. Proof: ≥
– LetfbeamaxflowinG’ofvaluek.
– Integrality theorem Þ k is integral so f(e) is 0 or 1. – ConsiderM=setofedgesfromLtoRwithf(e)=1.
• each node in L and R participates in at most one edge in M
• |M| = k: consider cut (LÈ s, RÈ t) and use Flow Value Lemma
1 1 1′
2 2′ 12 2’1
G3 3’s33’tG’ 4 4′ 4 4′
1 1′
The Univers5ity of Sydney 5′ 5 5′ Page 11
Bipartite Matching: Proof of Correctness
Theorem: Max cardinality matching in G = Max flow in G’. Proof: ≥
– LetfbeamaxflowinG’ofvaluek.
– Integrality theorem Þ k is integral so f(e) is 0 or 1. – ConsiderM=setofedgesfromLtoRwithf(e)=1.
• each node in L and R participates in at most one edge in M
• |M| = k: consider cut (LÈ s, RÈ t) and use Flow Value Lemma
See also Ed post:
https://edstem.org/courses/3946/discussion/211368
The University of Sydney
Page 12
Bipartite Matching: Running Time
Bipartite Matching Problem
Max Flow Problem
O(n)
Generic augmenting path: O(mF) = O(mn) Edmonds-Karp: O(m2 log F ) = O(m2 log n)
Bipartite Matching Solution
Max Flow Solution
The University of Sydney
Page 13
O(n)
Bipartite Matching: Running Time
Which max flow algorithm to use for bipartite matching? – Generic augmenting path: O(mF) = O(mn).
– Edmonds-Karp: O(m2 log F ) = O(m2 log n).
– Best known: O(mn1/2). [Micali-Vazirani 1980]
Non-bipartite matching:
– Structure of non-bipartite graphs is more complicated, but
well-understood.
– Blossom algorithm: O(mn2).
[Tutte-Berge, Edmonds-Galai] [Edmonds 1965]
The University of Sydney
Page 14
Reduction Template for Decision Problems
Algorithm for X
Instance of Y
f(I)
Yes for f(I) No for f(I)
Transforms instance of X to instance of Y
Algorithm for Y
Instance of X
I
Yes for I No for I
Step 2
Step 1
Step 1: Construct a polynomial-time algorithm that transforms instance I of X to an instance f(I) of Y
Step 2: Prove correctness, which boils down to showing
Answer for I is Yes iff answer for f(I) is Yes
Note: Reduction is one-way but proof needs equivalence The University of Sydney
Page 15
7.12 Baseball Elimination
Team Wins Losses To play Against = rij
i wi li ri
Atl Phi NY Mon
Atlanta 83 71 Philly 80 79 NewYork 78 78 Montreal 77 82
8 – 1 6 1 31-02 6 6 0 – 0 3120-
Which teams have a chance of finishing the season with most wins?
– A team is said to be eliminated if no outcome of the remaining games results in the team finishing (or tying) with the most wins.
– Montreal eliminated since it can finish with at most 80 wins, and Atlanta already has 83.
– wi +ri
– Claim: G has circulation iff G’ has max flow of value D. s
saturates all edges leaving s and entering t
G’:
The University of Sydney
Page 27
7
8
6
supply
77
106 49
34
0 10
11
demand
t
Circulation with supply and demand
Integrality theorem. If all capacities and demands are integers, and there exists a circulation, then there exists one that is integer-valued.
Proof: Follows from max flow formulation and integrality theorem for max flow.
Characterization.
Given (V, E, c, d), there is a feasible circulation with demands dv iff for all cuts (A, B) ,
SvÎB dv ≤ cap(A, B).
Proof idea: (⇒) Use SvÎB dv = net flow of circulation from A to B. (⇐) Look at min cut in G’.
The University of Sydney
Page 28
Circulation with supply/demand and lower bounds
Feasible circulation.
– Directed graph G = (V, E).
– Edge capacities c(e) and lower bounds !(e), e Î E. – Node supply and demands d(v), v Î V.
Definition: A circulation is a function that satisfies: – For each e Î E: !(e) £ f(e) £ c(e)
(capacity) (conservation)
– For each v Î V: å f(e) – e in to v
å f(e) = d(v) e out of v
Circulation problem with lower bounds.
Given G = (V, E, !, c, d), does there exists a circulation?
Can reduce circulation with lower bounds to circulation w/o lower bounds.
Theorem: Suppose all demands, capacities, and lower bounds in G are
integers. If a circulation in G exists, then there is a circulation that is
integer-valued.
The University of Sydney Page 29
7.8 Survey Design
The University of Sydney Page 30
Survey Design: Problem
– Design survey asking n1 consumers about n2 products.
– Can only survey consumer i about a product j if they own it. – Ask consumer i between ci and ci’ questions.
– Ask between pj and pj’ consumers about product j.
Goal: Design a survey that meets these specs, if possible.
The University of Sydney
Page 31
Survey Design: Algorithm
Formulate as a circulation problem with lower bounds (no demands, i.e. d(v) = 0 for all v)
– Include an edge (i, j) if customer own product i. – Integer circulation Û feasible survey design.
The University of Sydney
Page 32
1
[c1, c1′]
2
s 3 4
consumers 5
¥
[0, 1] 1′
[p1, p1′] 2′
3′ 4′ 5′
t
products
Survey Design: Correctness
1. If the Circulation problem (with lower bounds) is feasible then the Survey Design problem is feasible.
2. If the Survey Design problem is feasible then the Circulation
problem is feasible.
¥
[0, 1] 1′
[p1, p1′] 2′
1
[c1, c1′]
2
s 3 4
consumers 5
3′ 4′ 5′
t
products
The University of Sydney
Page 33
Lecture 8b:
NP and Computational Intractability
The University of Sydney
Page 34
Outline of today’s lecture
• Decision vs Optimization vs Search
• Reduction: polynomial time
• Reduction by simple equivalence.
• Reduction from special case to general case.
• Reduction by encoding with gadgets.
• Definition of P and NP • NP-completeness
The University of Sydney
Page 36
Classify Problems According to Computational Requirements
Question: Which problems will we be able to solve in practice? A working definition. [Cobham 1964, Edmonds 1965, Rabin 1966].
Those with polynomial-time algorithms.
Yes
Probably no
Shortest path
Longest path
Matching
3D-matching
Min cut
Max cut
2-SAT
3-SAT
Planar 4-color
Planar 3-color
Bipartite vertex cover
Vertex cover
The University of Sydney
Page 37
Classify Problems
Aim: Classify problems according to those that can be solved in polynomial-time and those that cannot.
– Major goal in Theoretical Computer Science – Resolution of P vs NP is worth USD 1 million
Frustrating news: Huge number of fundamental problems have defied classification for decades.
This lecture: Show that these fundamental problems (in the grey area) are “computationally equivalent” and appear to be different manifestations of one hard problem.
The University of Sydney Page 38
8.1 Polynomial-Time Reductions
The University of Sydney Page 39
Reductions
We have seen a number of reductions in the last few lectures: – Maximum matching → Maximum flow
– Minimum cut → Maximum flow
– Image Segmentation → Minimum cut
– Maximum number of disjoint paths → Maximum flow
In all these cases we reduced X to Y, where
– X = new problem
– Y = problem we already knew how to solve
Reducing X to Y is, in a sense, equivalent to saying If “Y is easy” then “X is easy”
The University of Sydney
Page 40
Reductions are double-edged swords
Reducing X to Y also gives us the following statement: If “X is hard” then “Y is hard”
Our proof techniques do not allow to show unequivocally that a certain problem is “hard”, but certain problems are widely believed to be “hard”. Reductions allow us to transfer this belief.
Reducing X to Y gives us the following statement:
If “we believe that X is hard” then “we believe that Y is hard”
The University of Sydney Page 41
Polynomial-Time Reduction
Reduction. Problem X polynomial reduces to problem Y, denoted X £ P Y, if arbitrary instances of problem X can be solved using:
– Polynomial number of standard computational steps, plus
– Polynomial number of calls to an oracle/black box that solves problem Y.
A reduction from X to Y is an algorithm for X of the following form:
Algorithm for X
f(I)
Instance Solution of Y for f(I)
Transform instance of X to instance of Y
Algorithm for Y
Transform solution for Y to a solution for X
Instance of X
I
Illustration: single call of black box The University of Sydney
Solution for I
Page 43
Polynomial-Time Reduction
Purpose. Classify problems according to relative difficulty.
1. Design algorithms. If X £ P Y and Y can be solved in polynomial-time, then X can also be solved in polynomial time.
2. Establish intractability. If X £ P Y and X cannot be solved in polynomial-time, then Y cannot be solved in polynomial time.
Transitivity: If X £P Y and Y £P Z, then X £P Z. Equivalence: IfX£P YandY£P X,thenXoPY.
The University of Sydney Page 55
Decision vs Optimization vs Search
Decision problem:
Does there exist an object satisfying some given properties? Output: Yes/No.
Example: Is there a path from s to t?
Optimization problem:
What is the size of the biggest/smallest such object? Output: Number.
Example: What is the length of the shortest s-t path?
Search problem:
Find a biggest/smallest such object
Output: Object.
Example: Find a shortest s-t path. The University of Sydney
Page 57
Decision vs Optimization vs Search
Decision problem:
Does there exist a matching of size 3 k? Output: Yes/No.
Optimization problem:
What is the size of the maximum matching? Output: Number.
Search problem:
Find a maximum matching. Output: Set of edges.
Theorem. Decision o P Optimization o P Search The University of Sydney
Page 58