Network Flows Flashcards
What is a Bipartite graph?
A graph where the vertices V are partitioned into two disjoint sets L, R s.t. every edge has one endpoint in L and one endpoint in R.
What is a matching?
In G set of edges E’ s.t. every vertex is adjacent to at most one edge in E’.
What concepts constitute Network Flows?
- Greedy and local-search heuristics :
- non-trivial greedy/local search algorithms
- heuristic on choosing next step crucial for performance
- Reductions and completeness
- If solution for A, then reduce B to A and use solution for A. Map output of A to output of B through a function
- Complete for efficient solutions
- Duality:
- optimum solution to max and min is the same
True or False
Any problem that can be solved in poly-time can be encoded as an instance of Network Flows.
True!
This is because Net flows are complete for problems with efficient solutions.
True or False
In network flows, solution for maximization = solution for minimization
True! This is due to duality
Define a Network Flow
- Directed graph G=(V,E)
- source node (no incoming edges)
- target node (no outgoing edges)
- Each edge e has a capacity c(e) ≥ 0 (usually integers or rationals)
What is a flow in a network flow G?
- Positive number for each edge e f(e) satisfying:
- capacity constraint
- flow conservation
What are the capacity constraints?
- For each edge e, 0 ≤ f(e) ≤ c(e)
What is the flow conservation?
- For each vertex v, s.t. v≠s or v≠t,
- → sum of flow into v = sum of flow leaving v
What is the value of a flow?
sum of flow leaving source node.
Define the Max Flow problem
- Input:
- Network flow G with s, t, and c(e) for all edges
- Output:
- Flow f with maximum value
What naive way does not work to solve the Max Flow problem and what is the solution?
- Picking an s-t path and pushing all the flow we can on that path. Stop when we can’t push any more
- SOLUTION:
- re-routing
What is a residual graph?
- Graph which will record all possible ways in which we can reroute the flow
- G_f copy of network flow G but:
- Forward edges:
- c(e) - f(e)
- Backward edges:
- f(e)
- Forward edges:
Define what a simple s-t path is.
Path with no repeating vertices.
What is an augmenting path?
- G network flow
- f flow on G
- G_f residual graph
- augmenting path P is any simple s-t path in G_f
In your own words, describe the steps of the function Augment
-
Input: net flow G=(v,E), flow f, augmenting path P on G_f
- Get the minimum value on an edge of P = b
- For every edge in P:
- if (u,v) in E (in net flow) → f’(e) = f(e) + b
- so augment the flow on that edge by b
- if (v,u) in E (in net flow) → f’(e) = f(e) - b
- so augment the flow but backwards.
- if (u,v) in E (in net flow) → f’(e) = f(e) + b
- Return the augmented flow f’
Describe on your own words the steps in Ford-Fulkerson
-
Input: Network flow G=(V,E) with s and t
- Initialize f(e) = 0 for all edges
- Construct residual graph G_f
- while there is an augmenting path P:
- f’ = Augment(f,P)
- Update G_f
- Return f
True or False
The augmenting path chosen through Ford-Fulkerson will negatively affect finding the correct optimal solution.
FALSE
You can take any augmenting path and will ALWAYS get to the correct solution.
True or False
The choice of augmenting path in Ford-Fulkerson will affect the run-time of the algorithm.
True
It heavily affects the run-time
What is the runtime of Ford-Fulkerson?
O(|E| * C)
Where C = total capacity of edges leaving s
What can greatly affect the runtime of Ford-Fulkerson?
- The Augmenting Path choice in FF
- The total capacity of the edges coming from s
- ex) they can add to C = 1000000 then the runtime is O(|E| * 1000000 )
True or False
val(f) ≤ C
- TRUE
- val(f) is the sum of the flows on edges leaving s
- C sum of capacities on edges leaving s
Explain why Ford-Fulkerson is O(|E|*C)
- Finding an augmenting path can take O(|V| + |E|) = O(|E|)
- the while loop will trigger at most C times (increase flow by 1 each time)
- So we get O(|E|*C)
True or False
Runtime of FF is actually exponential in the length of its input.
TRUE
- integers are encoded in binary:
- integer c is actually O(log c)
- which makes C exponentially on it’s lenght
What are the two properties that weill always be true of the output of FF?
- Let U be the set of vertices reachable from s in the output graph of FF
- every edge leaving U is saturated
- sum of flow of all edges leaving U = val(f)
CONCLUSION: U is an s-t cut
What is an s-t cut?
- Let U be a subset of vertices such that s is in U but t is not.
- c(U) = sum of the capacities of the edges leaving U
In a few sentences, explain why if U is an s-t cut
val(f) = fout(U) - fin(U) ≤ c(U)
Weak duality for flows
- C = sum of capacities of edges leaving s
- val(f) = sum of flow of edges leaving s
- Note that because of flow conservation, the flow coming into U has to be the same as coming out of U
- consider adding a vertex to U then the flow into v and out of v gives a flow = out - in which you can add to val(f)
- SEE NOTES p. 8
- val(f) ≤ c(U) by def
Why do we minimize over cut capacities?
Because by the Weak duality for flows, we know that the every flow cannot be greater than the capacity of a cut. So the minimizing problem is constraint by this.
Strong Duality for Flows
When FF ends, let U* be an s-t cut.
val(f) = c(U*)
Explain why in a few sentences
- val(f) = fout(U) - fin(U) ≤ c(U)
- By definition, FF ended, no more s-t augmenting paths → fout(U) = c(U) since saturated
- In G, edges entering U have flow 0 because otherwise in G_f there is an edge leaving U so an s-t path with is a contradiction to the setting.
- So fin(U) = 0
- val(f) = fout(U) - 0 = c(U)
True or False
Maximum flow on G = capacity of any min cut on G
True
This is the Max-Flow/Min-Cut Theorem
What are some of the problems with the Ford-Fulkerson Algorithm?
- Exponential time on C → O(2}E})
- This is because the bottleneck of the algorithm depends on the minimal value on an edge on an augmenting path and on the integrality of net flows.
What is the main idea behind Capacity Scaling?
# * Choose the path with largest residual capacity out of all the paths * Or actually choose the path with *_sufficiently large capacity_*
What is Gf(DELTA) in the Capacity Scaling Algorithm?
- Let DELTA be any integer
- Gf(DELTA) is the new graph obtained from G_f by discarding all the edges e in G_f with weight < DELTA
True or False
Any augmenting path in G_f(delta) is also an augmenting path in G_f.
True.
This is because G_f(delta) is the same as G_f but without low weight edges.
Describe the steps in the Capacity scaling algorithm in your own words.
- Input: flow network G
- Initialize
- f(e) = 0 for all edges
- G_f
- C := the max capacity of an edge leaving s
- delta := largest power of 2 ≤ C
- while delta ≥ 1:
- while augmenting path P in G_f(delta)
- f ‘= Augment(f, P)
- update G_f
- delta = delta/2
- while augmenting path P in G_f(delta)
True or False
The Capacity Scaling algorithm outputs the max flow
True
because FF does
What is the capacity of an s-t cut U* G_f(delta) when the Capacity scaling algorithm ends?
c(U*) < val(f) + |E|* delta
What is the runtime for Capacity Scaling Algorithm?
O(|E|2logC)
Is there a case where Ford-Fulkerson is faster than Capacity Scaling?
Yes, when C is small
When is Capacity Scaling faster than Ford Fulkerson?
When C = x(|E|log|E|)
This is because otherwise C is small enough so that FF is faster.
Informally describe what a reduction is.
- You have problem B and algorithm that solves it X
- You have problem A but no solution
- A is similar to B
- You can create an algorithm F s.t. it maps the input of A into inputs of B and outputs of B into outputs of A.
- This way you can use X to solve A
What is a matching?
- Let G=(V,E)
- Matching is a set of edges E’ such that every edge in E’ does not share a vertex with each other.
What is bipartite graph?
- Let G=(V,E) be a graph
- G is bipartite if you can partition the vertices into two subsets L, R such that, every vertex in L do not share an edge between each other and every vertex in R does not share any edge between each other either.
What is the algorithm that reduces the Bipartite Matching problem to Max-Flow?
- Direct all edges in G from L to R
- Add capacity inf to all edges
- Add vertex s and edges (s, u) s.t. u in L
- Add capacity 1 to these new edges
- Add vertex t and edges (v,t) s.t. v in R
- Add capacity 1 to these new edges
What is Konings Theorem?
max{|M| s.t. M is a matching} = min{|U| s.t. U is a vertex}
In a bipartite graph
Konings theorem only holds for bipartite graphs. But the Weak duality |M| ≤ |U| holds for any graph. Why?
- Let M be a matching and U a vertex cover
- Suppose max |M| = min |U| for any graph. Then we have |M| ≤ |U| but also |M| ≥ |U|
- We know that every edge in G is adjacent to a vertex v in U by definition
- Moreover, since edges in M cannot share a vertex, then every edge in M is associated to a vertex in U
- But since |M| ≥ |U| it means that there can be an edge e that is not adjacent to any v in U. Thus, U is not a vertex cover which is a contradiction.
What are some of the properties of Max Flow that are useful?
- It has capacities and flow constraints
- Goal: find the maximum flow that satisfies all the capacities and flow constraints
Describe the Image Segmentation Problem,
-
Input:
- Grid of pixels
- For every pixel i
- a_i = likelihood of belonging to foreground
- b_i = likelihood of belonging in background
- p_ij = penalty for pair of pixels i, j
- Ouput: Partition of pixels A, B s.t. A foreground, B background
- Goal:
- maximize q(A,B) which is the measure of quality
Given the problems solved in class, which one is the most relevant to reduce to in the Image Segmentation problem and why?
-
Min-Cut
- We want to partition the input.
- The pairwise relationship for pixels (penalty) is similar to edge constraints.
If we compare Min-Cut and image segmentation what is a difference between the two?
In Image segmentation, we want to maximize whereas in Min-Cut we want to minimize
While reducing the image segmentation problem to min cut, we run into the problem that min cut minimizes the objective function and image segmentation looks to maximize the objectigve function. What is the key step to solve this problem?
- We want to partition the set of pixels into A and B
- Let Q = sum over all pixels in A a_i + b_i + sum over all pixels in B a_i + b_i
- Manipulate such that you have something similar to q(A,B) but that can be minimized
What is the objective function to be maximized in the image segmentation problem?
- Let A, B be the partition of pixels
- q(A,B) = sum over A a_i + sum over B b_i - sum over every pair of pixels that are neighbours p_ij
What is the construction that allows us to reduce Image Segmentation to Min Cut?
- Let vertices be all the pixels and add the vertices s and t
- Let all neighbouring pixels i, j to have edges (i,j) and (j,i) with capacity pij
- Connect s to every pixel vertex with capacity a_i
- Connect every pixel vertex to t with capacity b_i
What is a Flow Network with demands?
- Flow Network which doesn’t have an s and t vertices.
- Each edge e in the graph is directed and has a capacity c(e)
- Each vertex v has a demand d(v) which is an integer number
- If d(v) < 0 then it is pushing out d(v) flow
- If d(v) ≥ 0 then it needs d(v) to come into v
What is a Circulation?
- It’s a sunction f s.t. for G a Flow network with demands
- f: E → R+
- Respects:
- Capacity constraints f(e) ≤ c(e)
- Demand constraint for every vertex:
- The sum of the flow into v minus the sum of flow leaving v = d(v)
Describe the circulation problem
-
Input:
- Flow Network with demands G
-
Output:
- True or False
-
Goal:
- decide if there exists a circulation f on G
How can you solve the Circulation problem?
Reduce to Max Flow?
Describe the construction to use when solving the Circulation problem?
Reduction to Max-Flow
- Add an s and t vertices
- For all vertices v s.t. d(v) < 0, create edges sv with capacity |d(v)|
- For all vertices v s.t. d(v) ≥ 0, create edges vt with capacity d(v)
If G (flow network with demands) has a circulation satisfying all constraints then?
Then the construction to reduce to Max-Flow, G’, has a flow of value D
where D is the sum of all the demands greater than 0.
When we reduce the circulation problem to a Max Flow problem, we get the construction G’.
If G’ has a flow with value D s.t.
D = sum of all the demands d(v) > 0
then….?
Then the flow network with demands G has a circulation satisfying all the constriants.
If Network Flow with demands G has a circulation with integral capacities and demands, then…
then there is a circulation on G where the flow on every edge is an integer.
What is a flow network with demands and lower bounds?
- G is a network flow with demands and lower bounds if:
- Every vertex has an integer value d(v)
- Every edge has two integer values:
- capacity: c(e) which is an upper bound
- lower bound: l(e) which is the minimum amount of flow that an edge should have
What is the Circulation with lower bounds problem?
- Input: G, demands d(v), lower bounds l(e) and capacities c(e)
- Output: True or False
- Goal: Decide if there is a valid flow or not in G
What are the constraints that have to be satisfied by a circulation in a network flow with demands and lower bounds?
-
Capacity constraint
- l(e) ≤ f(e) ≤ c(e)
-
Demand constraints
- sum of the flow into v - sum of the flow out of v = d(v)
How do you solve the Circulation with Demands and lower bounds problem?
You reduce it to Max-Flow
What construction do you have to do to solve the circulation with demands and lower bounds problem?
Reduce to Max-Flow
- Remove the lower bounds by creating a new capacity c’(e) = c(e) - l(e)
- Compute the total lower bound for vertex v: L(v) = sum of l(e) into v - sum of l(e) out of v
- Create a new demand for vertex v: d’(v) = d(v) - L(v)
- Create new circulation on edge e : f’(e) = f(e) - l(e)
True or False
Circulation with Demands and Lower Bounds problem does not satisfy the integrality theorem that is satisfied by the Circulation problem.
False It satisfies the theorem because of the same reasons
