[SOLVED] CS algorithm Lecture 8a

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 E R, E).
M I 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 E R E {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 21
G3 3s33tG 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 21
1 1
G3 3s33t 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 U 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 21
G3 3s33tG 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:
LetfbeamaxflowinGofvaluek.
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 (LE s, RE t) and use Flow Value Lemma
1 1 1
2 2 12 21
G3 3s33tG 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:
LetfbeamaxflowinGofvaluek.
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 (LE s, RE 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 0; supply if d(v) < 0; transshipment if d(v) = 0Definition: A circulation is a function that satisfies: For each e I E: 0 f(e) c(e) (capacity) For each v I V: a f(e) – a f(e) = d(v) (conservation)e in to v e out of vCirculation problem: Given (V, E, c, d), does there exist a circulation?Generalization of max flow The University of SydneyPage 23 Circulation with demands. Directed graph G = (V, E). Edge capacities c(e), e I E. Node supply and demands d(v), v I V.Definition: A circulation is a function that satisfies: For each e I E: 0 f(e) c(e) ForeachvIV: af(e) – af(e) = d(v)(capacity) (conservation)supplyG:-777106 493 411e in to v e out of v -8-6The University of SydneyPage 2410 0capacitydemand Circulation with demands. Directed graph G = (V, E). Edge capacities c(e), e I E. Node supply and demands d(v), v I V.Definition: A circulation is a function that satisfies: For each e I E: 0 f(e) c(e) ForeachvIV: af(e) – af(e) = d(v)(capacity) (conservation)supplyG:-77 42 9e in to v e out of v -861 47710 66 3-63 411Qn: How to reduce Is there a flow of value at least L in G to acirculation problem?The University of SydneyPage 2510 04capacityflowdemand Circulation with supply and demandNecessary condition: sum of supplies = sum of demands. ad(v) = a -d(v) =: Dv:d(v)>0 v:d(v)< 0Proof: Sum conservation constraints for every demand node v. G:-7-861 47710 66 3-6 supply7 42 9 3 411 10 04capacityflowdemand The University of SydneyPage 26 Circulation with supply and demandMax flow formulation. Add new source s and sink t. For each v with d(v) < 0, add edge (s, v) with capacity -d(v). For each v with d(v) > 0, add edge (v, t) with capacity d(v).
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) ,
SvIB dv cap(A, B).
Proof idea: () Use SvIB 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 I E. Node supply and demands d(v), v I V.
Definition: A circulation is a function that satisfies: For each e I E: !(e) f(e) c(e)
(capacity) (conservation)
For each v I V: a f(e) e in to v
a 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 U 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 todays 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: IfXP YandYP 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