# CS代考程序代写 algorithm Lecture 9 (cont.) – Flow networks II:

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) = 0
Definition: 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 v
Circulation problem: Given (V, E, c, d), does there exist a circulation?
Generalization of max flow The University of Sydney
Page 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)
supply
G:
-7
77
106 49
3 411
e in to v e out of v -8
-6
The University of Sydney
Page 5
10 0
capacity
demand
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)
supply
e in to v e out of v -8
61 477
10 66 3
-6
G:
-7
7 42 9
3 411
10 0
4
capacity
flow
demand
The University of Sydney
Page 6
Circulation with supply and demand
Necessary condition: sum of supplies = sum of demands. åd(v) = å -d(v) =: D
v:d(v)>0 v:d(v)< 0
Proof: Sum conservation constraints for every demand node v.
G:
-7
-8
61 477
10 66 3
-6 supply
7 42 9
3 411
10 0
4
capacity
flow
demand
The University of Sydney
Page 7
Circulation with supply and demand
Max 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