Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

COMP 360: Algorithm Design > Network Flows > Flashcards

Network Flows Flashcards

1
Q

What is a Bipartite graph?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is a matching?

A

In G set of edges E’ s.t. every vertex is adjacent to at most one edge in E’.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What concepts constitute Network Flows?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

True or False

Any problem that can be solved in poly-time can be encoded as an instance of Network Flows.

A

True!

This is because Net flows are complete for problems with efficient solutions.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

True or False

In network flows, solution for maximization = solution for minimization

A

True! This is due to duality

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Define a Network Flow

A
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is a flow in a network flow G?

A
  • Positive number for each edge e f(e) satisfying:
    • capacity constraint
    • flow conservation
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What are the capacity constraints?

A
  • For each edge e, 0 ≤ f(e) ≤ c(e)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the flow conservation?

A
  • For each vertex v, s.t. v≠s or v≠t,
  • → sum of flow into v = sum of flow leaving v
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the value of a flow?

A

sum of flow leaving source node.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Define the Max Flow problem

A
  • Input:
    • Network flow G with s, t, and c(e) for all edges
  • Output:
    • Flow f with maximum value
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What naive way does not work to solve the Max Flow problem and what is the solution?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is a residual graph?

A
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Define what a simple s-t path is.

A

Path with no repeating vertices.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is an augmenting path?

A
  • G network flow
  • f flow on G
  • G_f residual graph
  • augmenting path P is any simple s-t path in G_f
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

In your own words, describe the steps of the function Augment

A
  • 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.
    • Return the augmented flow f’
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Describe on your own words the steps in Ford-Fulkerson

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

True or False

The augmenting path chosen through Ford-Fulkerson will negatively affect finding the correct optimal solution.

A

FALSE

You can take any augmenting path and will ALWAYS get to the correct solution.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

True or False

The choice of augmenting path in Ford-Fulkerson will affect the run-time of the algorithm.

A

True

It heavily affects the run-time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What is the runtime of Ford-Fulkerson?

A

O(|E| * C)

Where C = total capacity of edges leaving s

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What can greatly affect the runtime of Ford-Fulkerson?

A
  • 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 )
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

True or False

val(f) ≤ C

A
  • TRUE
  • val(f) is the sum of the flows on edges leaving s
  • C sum of capacities on edges leaving s
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Explain why Ford-Fulkerson is O(|E|*C)

A
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

True or False

Runtime of FF is actually exponential in the length of its input.

A

TRUE

  • integers are encoded in binary:
    • integer c is actually O(log c)
    • which makes C exponentially on it’s lenght
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What are the two properties that weill always be true of the output of FF?

A
  • 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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is an s-t cut?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

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

A
  • 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
28
Q

Why do we minimize over cut capacities?

A

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.

29
Q

Strong Duality for Flows

When FF ends, let U* be an s-t cut.

val(f) = c(U*)

Explain why in a few sentences

A
  • 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)
30
Q

True or False

Maximum flow on G = capacity of any min cut on G

A

True

This is the Max-Flow/Min-Cut Theorem

31
Q

What are some of the problems with the Ford-Fulkerson Algorithm?

A
  • 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.
32
Q

What is the main idea behind Capacity Scaling?

A 
# * Choose the path with largest residual capacity out of all the paths
* Or actually choose the path with *_sufficiently large capacity_*
33
Q

What is Gf(DELTA) in the Capacity Scaling Algorithm?

A
  • 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
34
Q

True or False

Any augmenting path in G_f(delta) is also an augmenting path in G_f.

A

True.

This is because G_f(delta) is the same as G_f but without low weight edges.

35
Q

Describe the steps in the Capacity scaling algorithm in your own words.

A
  • 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
36
Q

True or False

The Capacity Scaling algorithm outputs the max flow

A

True

because FF does

37
Q

What is the capacity of an s-t cut U* G_f(delta) when the Capacity scaling algorithm ends?

A

c(U*) < val(f) + |E|* delta

38
Q

What is the runtime for Capacity Scaling Algorithm?

A

O(|E|2logC)

39
Q

Is there a case where Ford-Fulkerson is faster than Capacity Scaling?

A

Yes, when C is small

40
Q

When is Capacity Scaling faster than Ford Fulkerson?

A

When C = x(|E|log|E|)

This is because otherwise C is small enough so that FF is faster.

41
Q

Informally describe what a reduction is.

A
  • 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
42
Q

What is a matching?

A
  • 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.
43
Q

What is bipartite graph?

A
  • 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.
44
Q

What is the algorithm that reduces the Bipartite Matching problem to Max-Flow?

A
  1. Direct all edges in G from L to R
  2. Add capacity inf to all edges
  3. Add vertex s and edges (s, u) s.t. u in L
  4. Add capacity 1 to these new edges
  5. Add vertex t and edges (v,t) s.t. v in R
  6. Add capacity 1 to these new edges
45
Q

What is Konings Theorem?

A

max{|M| s.t. M is a matching} = min{|U| s.t. U is a vertex}

In a bipartite graph

46
Q

Konings theorem only holds for bipartite graphs. But the Weak duality |M| ≤ |U| holds for any graph. Why?

A
  • 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.
47
Q

What are some of the properties of Max Flow that are useful?

A
  • It has capacities and flow constraints
  • Goal: find the maximum flow that satisfies all the capacities and flow constraints
48
Q

Describe the Image Segmentation Problem,

A
  • 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
49
Q

Given the problems solved in class, which one is the most relevant to reduce to in the Image Segmentation problem and why?

A
  • Min-Cut
    • We want to partition the input.
    • The pairwise relationship for pixels (penalty) is similar to edge constraints.
50
Q

If we compare Min-Cut and image segmentation what is a difference between the two?

A

In Image segmentation, we want to maximize whereas in Min-Cut we want to minimize

51
Q

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?

A
  • 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
52
Q

What is the objective function to be maximized in the image segmentation problem?

A
  • 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
53
Q

What is the construction that allows us to reduce Image Segmentation to Min Cut?

A
  • 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
54
Q

What is a Flow Network with demands?

A
  • 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
55
Q

What is a Circulation?

A
  • 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)
56
Q

Describe the circulation problem

A
  • Input:
    • Flow Network with demands G
  • Output:
    • True or False
  • Goal:
    • decide if there exists a circulation f on G
57
Q

How can you solve the Circulation problem?

A

Reduce to Max Flow?

58
Q

Describe the construction to use when solving the Circulation problem?

A

Reduction to Max-Flow

  1. Add an s and t vertices
  2. For all vertices v s.t. d(v) < 0, create edges sv with capacity |d(v)|
  3. For all vertices v s.t. d(v) ≥ 0, create edges vt with capacity d(v)
59
Q

If G (flow network with demands) has a circulation satisfying all constraints then?

A

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.

60
Q

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….?

A

Then the flow network with demands G has a circulation satisfying all the constriants.

61
Q

If Network Flow with demands G has a circulation with integral capacities and demands, then…

A

then there is a circulation on G where the flow on every edge is an integer.

62
Q

What is a flow network with demands and lower bounds?

A
  • 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
63
Q

What is the Circulation with lower bounds problem?

A
  • 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
64
Q

What are the constraints that have to be satisfied by a circulation in a network flow with demands and lower bounds?

A
  • 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)
65
Q

How do you solve the Circulation with Demands and lower bounds problem?

A

You reduce it to Max-Flow

66
Q

What construction do you have to do to solve the circulation with demands and lower bounds problem?

A

Reduce to Max-Flow

  1. Remove the lower bounds by creating a new capacity c’(e) = c(e) - l(e)
  2. Compute the total lower bound for vertex v: L(v) = sum of l(e) into v - sum of l(e) out of v
  3. Create a new demand for vertex v: d’(v) = d(v) - L(v)
  4. Create new circulation on edge e : f’(e) = f(e) - l(e)
67
Q

True or False

Circulation with Demands and Lower Bounds problem does not satisfy the integrality theorem that is satisfied by the Circulation problem.

A

False It satisfies the theorem because of the same reasons

COMP 360: Algorithm Design (2 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions