Lecture 9 (cont.) – Flow networks II:
Applications
The University of Sydney
Page 1
Reduction to Max Flows
Max Flow Problem
Problem A
Max Flow Algorithm
Solution A
The University of Sydney Page 2
Max Flow Solution
7.7 Extensions to Max Flow
The University of Sydney Page 3
Circulation with supply and demand
Circulation with demands.
– DirectedgraphG=(V,E).
– Edgecapacitiesc(e),eÎE.
– Nodesupplyanddemandsd(v),vÎV.
demand if d(v) > 0; supply if d(v) < 0; transshipment if d(v) = 0Definition: A circulation is a function that satisfies: – For each e Î E: 0 £ f(e) £ c(e) (capacity)– For each v Î V: å f(e) – å 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 4 Circulation with demands.– Directed graph G = (V, E).– Edge capacities c(e), e Î E.– Node supply and demands d(v), v Î V.Definition: A circulation is a function that satisfies:– For each e Î E: 0 £ f(e) £ c(e)– ForeachvÎV: åf(e) – åf(e) = d(v)(capacity) (conservation)supplyG:-777106 493 411e in to v e out of v -8-6The University of SydneyPage 510 0capacitydemand Circulation with demands.– Directed graph G = (V, E).– Edge capacities c(e), e Î E.– Node supply and demands d(v), v Î V.Definition: A circulation is a function that satisfies:– For each e Î E: 0 £ f(e) £ c(e)– ForeachvÎV: åf(e) – åf(e) = d(v)(capacity) (conservation)supplye in to v e out of v -861 47710 66 3-6 G:-77 42 9 3 41110 04capacityflowdemand The University of SydneyPage 6 Circulation with supply and demandNecessary condition: sum of supplies = sum of demands. åd(v) = å -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 41110 04capacityflowdemand The University of SydneyPage 7 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
7
8
6
supply
G’:
77
106 49
34
0 10
11
demand
The University of Sydney
Page 8
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 demand dv iff for all cuts (A, B) ,
SvÎB dv ≤ cap(A, B). Proof idea: SvÎB dv is net flow from A to B.
The University of Sydney Page 9
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 (V, E, !, c, d), does there exists a circulation?
Theorem: There exists a circulation in G iff there exists a circulation in G’. If all demands, capacities, and lower bounds in G are integers, then there is a circulation in G that is integer-valued.
The University of Sydney Page 10
7.8 Survey Design
The University of Sydney Page 11
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 12
Survey Design: Algorithm
Formulate as a circulation problem with lower bounds. – Include an edge (i, j) if customer own product i.
– Integer circulation Û feasible survey design.
1
[c1, c1′]
2
s 3 4
consumers 5
¥
[0, 1] 1′
[p1, p1′] 2′
3′ 4′ 5′
t
products
The University of Sydney
Page 13
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 14
Lecture 10:
NP and Computational Intractability
The University of Sydney
Page 15
Algorithms and hardness
Algorithmic techniques:
– Greedy algorithms [Lecture 3]
– Divide & Conquer algorithms [Lectures 4 and 5]
– Dynamic programming algorithms [Lectures 6 and 7] – Network flow algorithms [Lectures 8 and 9]
Hardness:
– NP-hardness [Lecture 10]: O(nc) algorithm is unlikely – Coping with hardness [23 Oct]
Recap [30 Oct]
The University of Sydney
Page 16
Outline of today’s lecture
• 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 17
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 18
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 19
8.1 Polynomial-Time Reductions
The University of Sydney Page 20
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 21
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 22
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 24
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 36
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 38
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 39
Decision ≤ P Optimization ≤ P Search
Decision problem:
Does there exist a matching of size 3 k? Optimization problem:
What is the size of the maximum matching? Search problem:
Find a maximum matching.
Decision ≤ P Optimization
– Proof: Run the optimization algorithm and check if its output 3 k Optimization ≤ P Search
– Proof: Run the search algorithm and return size of its output The University of Sydney
Page 40
Decision ≥ P Optimization ≥ P Search
Decision problem:
Does there exist a matching of size 3 k? Optimization problem:
What is the size of the maximum matching? Search problem:
Find a maximum matching. Optimization ≤ P Decision
– Size of maximum matching = largest k such that decision problem is YES.
– Binary search (O(log m) calls to decision algorithm) The University of Sydney
Page 41
Decision ≥ P Optimization ≥ P Search
Search ≤ P Optimization (uses technique called self-reducibility)
Proof:
Key observation: If removing edge e from G does not reduce size of max matching, then there exists a max matching not containing edge e.
Let OPT(G) denote size of max matching of G. Reduction:
– For each edge e:
– If OPT(G {e}) = OPT(G), remove e from G
Uses m calls to optimization algorithm. The University of Sydney
Page 42
Decision o P Optimization o P Search
This holds true in general, not just for bipartite matching.
This justifies focusing on decision problems which are easier to construct and analyze reductions for.
The University of Sydney Page 44
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 45
Reduction Strategies
The University of Sydney
Page 46
1. Reduction by simple equivalence.
2. Reduction from special case to general case.
3. Reduction by encoding with gadgets.
Independent Set
INDEPENDENT-SET: Given a graph G = (V, E) and an integer k, is there a subset of vertices S Í V such that |S| 3 k, and for each edge at most one of its endpoints is in S?
independent set
The University of Sydney Page 48
Independent Set
INDEPENDENT-SET: Given a graph G = (V, E) and an integer k, is there a subset of vertices S Í V such that |S| 3 k, and for each edge at most one of its endpoints is in S?
Ex. Is there an independent set of size 3 6? Yes. Ex. Is there an independent set of size 3 7? No.
independent set
The University of Sydney Page 51
Vertex Cover
VERTEX-COVER: Given a graph G = (V, E) and an integer k, is there a subset of vertices S Í V such that |S| £ k, and for each edge, at least one of its endpoints is in S?
The University of Sydney Page 52
Vertex Cover
VERTEX-COVER: Given a graph G = (V, E) and an integer k, is there a subset of vertices S Í V such that |S| £ k, and for each edge, at least one of its endpoints is in S?
Ex. Is there a vertex cover of size £ 4? Yes. Ex. Is there a vertex cover of size £ 3? No.
vertex cover
The University of Sydney
Page 53
Vertex Cover and Independent Set
Theorem: VERTEX-COVER oP INDEPENDENT-SET. (VC £P IS and IS £P VC)
The University of Sydney
Page 54
Vertex Cover and Independent Set
Theorem: VERTEX-COVER oP INDEPENDENT-SET. (VC £P IS and IS £P VC) Proof:
We claim S is an independent set iff VS is a vertex cover.
independent set vertex cover
The University of Sydney
Page 55
VERTEX-COVER oP INDEPENDENT-SET We claim S is an independent set iff VS is a vertex cover.
Given this claim, we can construct the following reductions:
– VC £P IS
– VC instance (G, k) → IS instance (G, n-k) – Yes for VC instance iff Yes for IS instance
– IS £P VC
– IS instance (G, k) → VC instance (G, n-k) – Yes for IS instance iff Yes for VC instance
Analysis:
1. Both transformations take O(n+m) time.
2. Both proofs of correctness follow from the claim as it implies:
There exists a VC of size k iff there exists an IS of size n-k.
The University of Sydney Page 56
Vertex Cover and Independent Set
Claim: S is an independent set iff VS is a vertex cover.
Proof: We show S is an independent set iff VS is a vertex cover.
independent set vertex cover
Þ– Let S be any independent set.
– Consider an arbitrary edge (u, v).
– SindependentÞuÏSorvÏS Þ uÎVSorvÎVS. – Thus, VS covers (u, v) Þ VS vertex cover.
uv uv
Ü– Let VS be any vertex cover.
– ConsidertwonodesuÎSandvÎS.
– Observe that (u, v) Ï E since VS is a vertex cover.
– Thus, no two nodes in S are joined by an edge Þ S independent set. ▪
The University of Sydney Page 57
uv
Reduction Strategies
The University of Sydney
Page 58
1. Reduction by simple equivalence.
2. Reduction from special case to general case.
3. Reduction by encoding with gadgets.
Set Cover
SET-COVER: Given a set U of elements, a collection S1, S2, . . . , Sm of subsets of U, and an integer k, does there exist a collection of k of these sets whose union is equal to U?
Sample application.
– m available pieces of software.
– Set U of n capabilities that we would like our system to have.
– The ith piece of software provides the set Si Í U of capabilities. – Goal: achieve all n capabilities using fewest pieces of software.
Example:
U = { 1, 2, 3, 4, 5, 6, 7 } k=2
S1 ={3,7}
S2 ={3,4,5,6} S3 ={1}
S4 ={2,4}
S5 ={5}
S6 = {1,2,6,7}
The University of Sydney
Page 59
Set Cover
SET-COVER: Given a set U of elements, a collection S1, S2, . . . , Sm of subsets of U, and an integer k, does there exist a collection of k of these sets whose union is equal to U?
Sample application.
– m available pieces of software.
– Set U of n capabilities that we would like our system to have.
– The ith piece of software provides the set Si Í U of capabilities. – Goal: achieve all n capabilities using fewest pieces of software.
Example:
U = { 1, 2, 3, 4, 5, 6, 7 } k=2
S1 ={3,7}
S2 ={3,4,5,6}
S3 ={1}
S4 ={2,4}
S5 ={5}
S6 = {1,2,6,7}
The University of Sydney
Page 60
Vertex Cover Reduces to Set Cover
Theorem: VERTEX-COVER £P SET-COVER.
Proof: Given a VERTEX-COVER instance G = (V, E), k, we construct a set cover
instance whose size equals the size of the vertex cover instance.
Construction.
– Create SET-COVER instance:
• k=k, U=E, Sv ={eÎE:eincidenttov}
– Set-cover of size £ k iff vertex cover of size £ k. ▪
VERTEX COVER
ab
e7 e2 e3 e4
f e6 c
k=2
e1
e5
ed
The University of Sydney
Page 61
Vertex Cover Reduces to Set Cover
Theorem: VERTEX-COVER £P SET-COVER.
Proof: Given a VERTEX-COVER instance G = (V, E), k, we construct a set cover
instance whose size equals the size of the vertex cover instance.
Construction.
– Create SET-COVER instance:
• k=k, U=E, Sv ={eÎE:eincidenttov}
– Set-cover of size £ k iff vertex cover of size £ k. ▪
VERTEX COVER
ab
e7 e2 e3 e4
f e6 c
k=2
e1
e5
ed
SET COVER
U = { 1, 2, 3, 4, 5, 6, 7 }
k=2
Sa = {3, 7}
Sc = {3, 4, 5, 6} Se = {1}
Sb = {2, 4}
Sd = {5}
Sf= {1, 2, 6, 7}
The University of Sydney
Page 62
Vertex Cover Reduces to Set Cover
Theorem: VERTEX-COVER £P SET-COVER.
Proof: Given a VERTEX-COVER instance G = (V, E), k, we construct a set cover
instance whose size equals the size of the vertex cover instance.
Construction.
– Create SET-COVER instance:
• k=k, U=E, Sv ={eÎE:eincidenttov}
– Set-cover of size £ k iff vertex cover of size £ k. ▪
VERTEX COVER
ab
e7 e2 e3 e4
f e6 c
k=2
e1
e5
ed
SET COVER
U = { 1, 2, 3, 4, 5, 6, 7 }
k=2
Sa = {3, 7}
Sc = {3, 4, 5, 6} Se = {1}
Sb = {2, 4}
Sd = {5}
Sf= {1, 2, 6, 7}
The University of Sydney
Page 63
Reduction Strategies
The University of Sydney
Page 64
1. Reduction by simple equivalence.
2. Reduction from special case to general case.
3. Reduction by encoding with gadgets.
Satisfiability
Literal: A Boolean variable or its negation. Clause: A disjunction of literals.
Conjunctive normal form (CNF): A propositional formula F that is the conjunction of clauses.
xi or xi
Cj = x1 Ú x2 Ú x3
F= C1ÙC2ÙC3ÙC4 SAT: Given CNF formula F, does it have a satisfying truth assignment?
3-SAT: SAT where each clause contains exactly 3 literals.
(xÚx Úx )Ù(xÚx Úx )Ù(x Úx Úx )Ù(xÚx Úx ) 123123123123
Ex:
Yes: x1 = true, x2 = true x3 = false.
The University of Sydney Page 65
3 Satisfiability Reduces to Independent Set
Theorem: 3-SAT £P INDEPENDENT-SET.
INDEPENDENT-SET: Given a graph G = (V, E) and an integer k, is there a subset of vertices S Í V such that |S| 3 k, and for each edge at most one of its endpoints is in S?
The University of Sydney Page 66
3 Satisfiability Reduces to Independent Set
Theorem: 3-SAT £P INDEPENDENT-SET.
Proof: Given an instance F of 3-SAT, we construct an instance (G, k) of
INDEPENDENT-SET that has an independent set of size k iff F is satisfiable.
The University of Sydney Page 67
3 Satisfiability Reduces to Independent Set
Theorem: 3-SAT £P INDEPENDENT-SET.
Proof: Given an instance F of 3-SAT, we construct an instance (G, k) of
INDEPENDENT-SET that has an independent set of size k iff F is satisfiable. Construction.
– G contains 3 vertices for each of the k clauses, one for each literal. – Connect 3 literals in a clause in a triangle.
– Connect literal to each of its negations.
(G, k = 3)
x1 x2 x1
The University of Sydney
x2 x3 x1 x3 x2 x4 F = (x1 Ú x2 Ú x3)Ù (x1 Ú x2 Ú x3) Ù (x1 Ú x2 Ú x4)
Page 68
3 Satisfiability Reduces to Independent Set
Claim. G contains independent set of size k = |F| iff F is satisfiable.
Proof: Þ Let S be independent set of size k.
– S must contain exactly one vertex in each triangle.
– Set these literals to true.
– Truth assignment is consistent and all clauses are satisfied.
Proof: Ü Given satisfying assignment, select one true literal from each triangle. This is an independent set of size k. ▪
(G, k = 3)
x1 x2 x1
The University of Sydney
x2 x3 x1 x3 x2 x4 F = (x1 Ú x2 Ú x3)Ù (x1 Ú x2 Ú x3) Ù (x1 Ú x2 Ú x4)
Page 69
3 Satisfiability Reduces to Independent Set
Claim. G contains independent set of size k = |F| iff F is satisfiable.
Proof: Þ Let S be independent set of size k.
– S must contain exactly one vertex in each triangle.
– Set these literals to true.
– Truth assignment is consistent and all clauses are satisfied.
Proof: Ü Given satisfying assignment, select one true literal from each triangle. This is an independent set of size k. ▪
(G, k = 3)
x1 x2 x1
The University of Sydney
x2 x3 x1 x3 x2 x4 F = (x1 Ú x2 Ú x3)Ù (x1 Ú x2 Ú x3) Ù (x1 Ú x2 Ú x4)
Page 70
Clique
A clique of a graph G is a complete subgraph of G.
clique of size 4
clique of size 3
CLIQUE: Given a graph G=(V,E) and an integer k, does G=(V,E) contain a clique of size ≥ k?
The University of Sydney Page 71
3 Satisfiability Reduces to Clique
Theorem: 3-SAT £P CLIQUE.
Idea:
– Make “column” for each of the k clauses.
– No edge within a column.
– All other edges present except between x and x.
The University of Sydney
Page 72
3 Satisfiability Reduces to Clique
Example:
G=
E = (x Ú y Ú z) Ù (x Ú y Ú z) Ù ( y Ú z)
x y
z
x
y
z
y
z
Observation: G has a k-clique, if and only if E is satisfiable.
The University of Sydney
Page 73
Review
Basic reduction strategies.
– Simple equivalence: INDEPENDENT-SET oP VERTEX-COVER.
– Special case to general case: VERTEX-COVER £P SET-COVER. – Encoding with gadgets: 3-SAT £P INDEPENDENT-SET.
3-SAT £P CLIQUE Transitivity. If X £P Y and Y £P Z, then X £P Z.
Proof idea: Compose the two algorithms.
Example: 3-SAT £P INDEPENDENT-SET £P VERTEX-COVER £P SET-COVER.
The University of Sydney
Page 74
Reviews
There are no reviews yet.