● Network Flow
○ Flows, constraints, augmenting paths, residual graphs
○ Ford-Fulkerson
○ S-t cuts, cut capacities, max flow min-cut theorem
Copyright By PowCoder代写 加微信 powcoder
○ Reductions
● NP-Completeness
○ Reductions
○ Problems to Know
Network Flow
● Flow network: G = (V, E) with capacity ce for each edge e ○ has a single source node s and single sink node t
● Flow: a s-t flow is a mapping from the set of edges to non-negative real numbers ○ Constraints:
■ Capacity: 0 ≤ f(e) ≤ ce for each edge e
■ Conservation: for all internal nodes, the flow going out must equal the flow
● Value: value v(f) of flow f is the
○ flow coming out of s (source) = also the flow entering the t (sink)
f(e1) = 2 f(e2) = 1 f(e3) = 1 f(e4) = 0 f(e5) = 1
2/2 a 1/5 s 1/1
Residual Graphs
● Residual graph: Gf for flow network G and flow f where each directed edge in Gf has a value which denotes the amount of leftover flow that could be pushed in that direction
○ Forward Edges: Have value ce – f(e)
○ Backwards Edges: Have value f(e)
● Augmenting path: path from s to t in the residual graph
2/2 a 1/5 s 1/1
Residual Graphs
● Flow is 0 initially for all edges
● While there is an augmenting path:
○ Use the path to update f(e) for each edge e in the path
○ Update the residual graph
● Return final flow (max flow)
● Runtime ?
○ Runtime: with integer capacities, O(mC) – m is # of edges in G, C is max-flow
○ “Pseudopolynomial” – A polynomial bound on the runtime based on the magnitude of the inputs
– How do I pick a path to send flow?
– How much flow do I push along a path?
Where is the min-cut?
– Can I tell from this graph?
– Is it easy?
Where is the min-cut?
– Can I tell from this graph?
– Is it easy? ❌
Before constructing the residual graph, what is the capacity of this min-cut?
– Do I have enough information?
Can there ever not be a min-cut?
– By well-ordering principle that has to be a minimum
Can the min-cut not be equal to the max-flow? Explain without just citing the theorem)?
Are capacities of cuts (usually) > or < than values of flows? a. >
Can a cut have capacity less than the max-flow?
– Flow goes from s to t
– Cut is amount of flow allowed from s to t
● s-t cut: partition (A,B) of V where s has to be in A and t has to be in B
● Capacity of s-t cut: sum of capacities leaving A
Max-flow min-cut Theorem:
● Max flow (no augmenting path) = an s-t cut (A’, B’) that has the lowest capacity and v(f) =
● To find the min-cut, use BFS/DFS starting on s on the residual graph with the max flow
● Min cut does not always have to be unique!
● For e.g., in the homework, we found a min cut by doing a BFS from t on the reversed residual
Prelim Tip
● Practice calculating residual graphs, finding augmenting paths, augmenting a residual graph, finding min-cuts, etc.
● If you’re able to solve these quickly, you can get through the first half of the prelim fast!
Example Problem
● What is the value of the flow? Is this a max (s,t) flow?
● Draw the residual graph and determine if there’s an augmenting path
Example Problem
2/2 a 1/5 s 1/1
● What is the value of the flow? (2)
● Is this a max (s,t) flow? (no)
● Draw the residual graph and determine if there’s an augmenting path (s → b → a → t)
Example Problem
2/2 a 1/5 s 1/1
● Find min s-t cut
Example Problem
2/2 a 1/5 s 1/1
● Find min s-t cut
Why do we enforce, integer value flows ?
Example of Pseudo polynomial Runtime!!!!!
Reductions
● Feasibility Reductions
○ Bipartite Matching
○ Interview scheduling
○ Hospital to patients
● Min cut (optimizing a certain quality) Reductions
○ Computer applications and costs
○ Project selection
Matching Problem #1 (ch. 7, ex. 6)
– Given locations n light switches and n light bulbs
– Each light switch can be paired to one light bulb
– Determine if there exists an “ergonomic” set of pairings switches and bulbs (every bulb can be seen
from its switch)
Matching Problem #1 (ch. 7, ex. 6)
Edge capacities are 1
– If flow into t equals n, then layout is
ergonomic.
– Edges with flow from
bulbs to switches indicate what the ergonomic set of pairings is
If you were allowed to use certain bulbs or switches more than once, increase corresponding edge capacities
Matching Problem #2 (Ch. 7, s.e. 2)
– k vacation periods, where each period is a set of vacation days corresponding to a particular holiday
– n doctors, where each doctor has a set of vacation days that they are available to work
– Determine if there is an assignment of doctors to work on vacation days, with the following
constraints
1. Each doctors can be assigned to work at most c vacation days
2. No doctor can work more than one vacation day in the same vacation period
Matching Problem #2 (Ch. 7, s.e. 2)
– First Approach: Set up bipartite graph, use edge capacities to satisfy constraint #1 (at most c days per doctor)
– Problem: How do we enforce at most 1 vacation day per period for each doctor?
Matching Problem #2 (Ch. 7, s.e. 2)
– In general: We want to assign individual flow limits from left nodes to specific sets of right nodes
Ex. We want to assign individual limits to – A→Red
(s, t, edge capacities not shown)
Matching Problem #2 (Ch. 7, s.e. 2)
– In general: We want to assign individual flow limits from left nodes to specific sets of right nodes
– Add a “gadget” for each (left node, subset of right nodes) pair
– Edge capacity going into gadget is flow limit from the corresponding left node to set of right nodes
Max flow from A to red
Max flow from A to blue
Max flow from B to red
Max flow from B to blue
Matching Problem #2 (Ch. 7, s.e. 2)
– Set up bipartite graph
– Use [source → doctor] edge capacities to limit each doctor to c days in total (restraint 1)
– Add layer of “gadgets”, use [doctor → gadget] capacities limits from each doctor to 1 day per
vacation period (constraint #2)
– Valid matching exists if = # of vacation days
Conversion to Matching:
Flow from gadget (i,j) to vacation day k means Doctor i should work on Vacation Day k
Matching Problem #2 (Ch. 7, s.e. 2)
– Reduction takes O(n * # of vacation days) time
– Ford fulkerson is O(mC), because each edge has integer capacity
– In this case, is O(# doctors * # holidays), C is O(number of holidays)
– You need to be explicit about what m and C are in big O to apply the limit on Ford Fulkerson runtime Proof Of Correctness
– Valid Matching Existence → Max flow = # of vacation days
– Explain how if you have a valid matching, you can set flow through each edge such that flow into t = # of
vacation days
– This is max flow because (V\t, t) is (s,t) cut with min cut of # of vacation days
– Max flow = # of vacation days→ Valid Matching Existence
– If max flow is number of vacation days, each vacation day has flow to it from some gadget
– Flow from a gadget for doctor i to vacation day k means Doctor i should work on Vacation Day k
– Show that this matching obeys both constraints
– Reductions to Network Flow allows us to use – theorem to solve problems with the following properties
– Goal is to find an “optional” partition set of “objects” into sets A and B
– Optimal: maximize total reward minus total penalty
– Ex. Select some subset of objects (don’t select the others)
– Reward/Penalty comes from:
a) An object being in set A
b) An object being in set B
c) A pair of objects being split across the two sets
– May contain “dependencies” → basically just (c) above in disguise
– Ex. Project Selection (Section 7.11 in textbook)
– Need to split projects into “selected” and “not selected”
– Projects have positive or negative reward for being selected
– Has dependencies (certain projects cannot be selected without others being selected)
To use network flows, we want to convert goal into “minimize penalty of partition”
– Set up flow network such that the capacity of any s,t cut (A,B) is exactly equal to the penalty for
partitioning the set of objects into A and B
– Why this is useful: Max flow = Min cut = Min total penalty
– Determine max flow then find cut in residual graph
Converting “Maximize Reward” objective into “Minimize Penalty” objective
– Reward for selecting object to be in A → Penalty for not selecting it (It being in B)
– Setting up Flow Graph:
– For each object, create a node u in the flow networks
– s → u capacity: Penalty for u being in B (f(u))
– u → t capacity: Penalty for u being in A (g(u))
– ui → uj capacity: Penalty for ui being in A but uj being in B (h(ui,uj))
– Example: Goal is to partition {u1, u2} into subsets A and B, to minimize total “penalty”
Reduction (Possible Partitions from last slide)
B = {u1,u2}
h(u1,u2) t
A = {u2} B = {u1}
s h(u2,u1) h(u1,u2)
A = {u1} B = {u2}
s h(u2,u1)
uu 22 uu 11
h(u ,u ) t A = {u1, u2} s h(u2,u1) 1 2 B = {}
h(u ,u ) 1 2
– Dependencies
– ex. uj can only be in A if ui is in A too
How to handle this
– Use infinite capacity for uj → ui edge
– Why this works:
If an s,t cut (A,B) were to place uj in A but ui in B, the cut would have infinite capacity because of uj → ui edge
A = {u2}, B = {u1} would not happen because of infinite capacity from u2 → u1
Application Porting (Chapter 7, Exercise 29)
– The problem
– You have a collection of n software applications running on an old system
– Need to choose some subset of applications from {2, …, n} to be ported to a new system (#1 must stay behind)
– Goal is to choose subset to maximize monetary benefit – Rewards/Penalties
– Receive +bi benefit for porting application i to the new system
– Expense xij for porting one of i or j to the new system but not both
– Projects have positive or negative reward for being selected
– Has dependencies (certain projects cannot be selected without others being selected)
How to set up flow network to solve with min cut reduction? Nodes? Edges? Edge Capacities?
Application Porting (Chapter 7, Exercise 29)
– Applications
– Excluding application 1 (since it’s always with s)
– Let’s try to construct a graph, where for a given cut A/B, a node being in B represents
the application being ported, and a node being in A represents the application not
being ported.
– How do we set up edge capacities between the applications and s/t, so that
minimizing the capacity of the cut also maximizes our profit?
Application Porting (Chapter 7, Exercise 29)
– Formally, given a cut A/B, our profit equals:
– Maximizing this equals minimizing:
Application Porting (Chapter 7, Exercise 29)
● This equation is much easier to work with! We want the capacity of an A/B cut to equal that value.
● For every node v in A (representing an application not ported), we would like a b_v
capacity edge going across the cut.
○ Hence, add a b_i capacity edge from every application node i to the sink, t.
● For every pair of nodes u in B and v in A (representing u being ported, but not v), we would like a xu, v capacity edge going across the cut.
○ Hence, add an xu, v capacity edge between every pair of application nodes.
○ Note that xu, v = xv, u, so we are essentially adding an edge from u to v and
an edge from v to u, both with equal capacity .
Application Porting (Chapter 7, Exercise 29)
A more intuitive explanation – you can think of bi as the “penalty” for not porting application i, since that is the missed reward/opportunity cost you are paying for not porting i. Hence, we would like the i -> t edge to represent that penalty.
– Edges + Capacities – s → application i
– Penalty for i being ported – x1i
– application i → t
– Penalty for i not being ported
– application i → application j
– Penalty for j being ported but not i – xij
Application Porting (Chapter 7, Exercise 29)
x2b 12 x 2
– Edges + Capacities – s → application i
– Penalty for i being ported – x1i
– application i → t
– Penalty for i not being ported
– application i → application j
– Penalty for j being ported but not i – xij
Application Porting (Chapter 7, Exercise 29)
– Edges + Capacities – s → application i
– Penalty for i being ported – x1i
– application i → t
– Penalty for i not being ported
– application i → application j
– Penalty for j being ported but not i – xij
x 2b 12 x 2
s ∞ 1 x 3 b t 13 3
Prelim Tip
● For setting up max-flow reductions, try to think of the setup as “layers” of nodes. Then, you can reason about edges between layers of nodes more easily.
● Setting the edge capacities in min-cut reductions can be confusing: as a first step, decide what you want your sets A and B in the cut to represent
○ For e.g. in the application porting problem, we decided that a node being in B meant that it was ported, and it being in A meant it wasn’t ported.
○ This will help you intuitively reason about what the capacity of any given cut should be, to ensure that minimizing the capacity equals maximizing the profit.
NP-Completeness
Comparing “Hardness” of Problems
● Another application of reductions
● X is at least as “hard” as Y if
○ If we’re able to solve X efficiently, then we can also solve Y efficiently
○ X is at least as “hard” as Y
■ Y can be reduced to X using a polynomial time reduction ● Bipartite Matching ≤P Finding a max flow in a flow network
Reductions
● Solving one problem by converting it into an instance of another problem
● Create efficient algorithms by bootstrapping off algorithms you already know
○ Bipartite Matching →
○ Finding →
Polynomial Time Reductions
● For polynomial time reduction from Y to X
a. Polynomial time preprocessing to convert to instances of X
b. Polynomial number of calls to a black-box subroutine that solves X
c. Polynomial time post-processing on the result to get a result for Y.
● 𝜎: polynomial time function 𝜎 mapping instances of Y to instances of X,
● τ: polynomial time function τ mapping results of X back to results of Y.
● For decision problems
○ 𝜏 is the identity function
○ To show equivalence, we need to show that
these notes
y is a yes-instance of Y iff 𝜎(y) is a yes-instance of X
Important Considerations
● Y ≤PX implies that if we can solve X in polynomial time, we could also solve Y in polynomial time.
● The contrapositive of this also holds: if we cannot solve Y in polynomial time, then we cannot solve X in polynomial time.
● The direction of the reduction is a common tripping point – remember that to show that X is at least as hard as Y, we want to convert every instance of Y to some instance of X, not the other way around.
● Also note that ≤P is transitive, since compositions of polynomial-time reductions are still polynomial time.
What is NP-Completeness?
NP – The set of decision problems where there exists a certifier and certificate: verify “yes” solution in polynomial time
NP-Complete – The set of decision problems X that are in NP such that any decision problem Y in NP may be reduced to X (NP-Hard)
P – The set of decision problems that can be solved in polynomial time
Complexity Classes: NP
● Formally, a problem X is in NP if for every instance x of X, there exists a polynomial time verifier 𝜓(w) that takes in a polynomial-length witness w, where 𝜓(w) is true iff x is a yes-instance of the problem.
● This shows that there is a polynomial time algorithm (an efficient certifier) to verify that x is a yes-instance of X.
● You can also show a problem A is in NP by showing that A ≤P B, where B is some problem in NP. (The former option is often easier, though).
Complexity Classes: NP-hard problems
● We define NP-hard problems to be problems that are at least as hard as every problem in NP. (Implying that they are at least as hard as the hardest problems in NP)
● This means that there is a polynomial time reduction from every problem in NP to an NP-hard problem.
Example NP Hard Problems
SAT/3SAT: Given a CNF form formula involving n variables, is there a variable assignment that makes the formula true?
Vertex Cover: Does there exist of subset of vertices of size ≤ k which covers every edge?
Independent Set: Does there exist of subset of vertices of size ≥ k with no shared edges?
Hamiltonian Path: Does there exist a path which contains every vertex exactly once?
Set Cover: Given subsets of objects, does there contain a
set of size ≤ k of these subsets whose union covers all objects?
NP-completeness
● NP Complete: In NP and NP Hard
● Step 1: To show that a problem X is NP-hard, we can just reduce from any NP-complete problem to X.
● Step 2: Show X is in NP (Polynomial time verifier exists)
Step 1: Reducing to X from an NP-complete problem gives us a lower bound for the hardness of X
Step 2: Showing that X can be deterministically verified in polynomial time gives us an upper bound for the hardness of X.
Showing NP-completeness
Here is the general structure for proving that X is NP-complete.
1. Show that X is NP-hard. This involves showing that Y ≤PX, where Y is some NP-complete problem.
○ Define a mapping 𝜎 from an arbitrary instance y of Y to some instance x of X.
○ Show that y is a yes-instance of Y ⇒ 𝜎(y) is a yes-instance of X.
○ Show that 𝜎(y) is a yes-instance of X ⇒ y is a yes-instance of Y.
○ Show that the mapping 𝜎 takes polynomial time.
Showing NP-completeness (step 1 continued)
Technically we can reduce using any NP-complete problem, but a key skill is being able to identify similar patterns between X and an NP-complete problem you know of, to make the reduction easier. As you learn about more NP-complete problems, the range of problems you can use for reductions will increase!
If X involves…
● selecting at most k items, try reducing from Vertex Cover/Set Cover
● selecting at least k things, try Independent Set/Set Packing/Clique/Near-Clique
● giving an ordering over n items, try reducing from Hamiltonian Cycle/Hamiltonian
Path/Travelling Salesman.
If all else fails/these patterns don’t apply, SAT/3SAT is a good starting point! Section 8.10 in the book gives a useful overview of common NP-complete problems you can use.
Showing NP-completeness
2. Show that X is in NP. This involves showing that for any instance of X, there exists a polynomial length string w that can be verified in polynomial time to check if the instance is a yes-instance. (sounds scary but is usually the easy part)
○ Define a polynomial length w for every instance x that can be computed in polynomial time.
○ Define the predicate 𝜓, and show that 𝜓(w) is true iff x is a yes-instance.
○ Show that 𝜓(w) takes polynomial time to compute.
Proving Y is NP-Complete (Summary)
1. Y is in NP – motivate the certificate and certifier
a. Certificate: A string of polynomial length with respect to the instance of Y, describing a
“solution”
i. e.g. A set of vertices for Verte
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com