Max Flow Advanced

Question 1

Max feasible Flow algorithm

Answer 1

Step 1)
Construct the graph

Step 2)
Run a max flow algorithm on: G’=(V’,E’), s’, t’, c’
Get back: f’

Step 3)
If size(f') = Sum c'(s',*) = Sum c'(*,t') then f' is a feasible flow, otherwise, there is no feasible flow. 

Step 4)
Run a modified max flow algorithm with G(V,E), s, t, c with the initial flow equal to f= f’.

We modify the residual network as:
For (u,v) in E:
   if f(u,v) < c(u,v):
      add (u,v) to E^f
      add c^f(u,v) = c(u,v) - f(u,v)
      these are forward edges
   if f(u,v) - d(u,v) > 0:
      add (v,u) to E^f
      add c^f(v,) = f(u,v) - d(u,v)
      these are backward edges

Question 2

Max feasible flow graph construction

Answer 2

We want to define G’=(V’,E’), c’.

V’ = V + {s’, t’}. We’re adding s and t to the vertices.

E' = 
for(u,v) in E:
   add (u,v) to E'
   add c'(u,v) = c(u,v) - d(u,v)
for v in V:
   add (s',v) to E'
   add (v,t') to E'
   add c'(s',v) to Sum d(*,v)
   add c'(v,t') to Sum d(v,*)
add (t,s) to E'
add c'(t,s) = infinity
Here, we are  1) combining the demand and capacity together in c'. 2) Encoding the total demand in and out of a vertex as the capacities s' and t'. 3) Adding a special edge from t to s with unlimited capacity.

Question 3

Max feasible flow runtime

Answer 3

O(mC) with DFS, O(nm^2) with BFS

Question 4

Image segmentation graph construction

Answer 4

G=(V,E)

V represents pixels in the image
E represents an edge between each neighboring pixel

Additional parameters:
-f such that f(i) = likelihood that i is a foreground pixel
-b such that b(i) = likelihood that i is a background pixel
-p such that p(i,j) = separation penalty/cost of putting i and j in different objects.
All >= 0 for i,j in V.

Question 5

Max flow algorithm correctness

Answer 5

We encode the demands of each vertex into (s’,) and (,t’) so that we can verify that after a max flow is found, the demand in and out of each v is satisfied. If c(s’, *) are maxed (saturated), the demands are met.

We encode the demands of each edge into c’ by removing that capacity from c so that we never drop below demand bounds. Since max flow algorithm does not allow f(u,v) < 0, shifting that 0 to the demand means we won’t drop below the demands.

If we run max flow algorithm and find there is a feasible flow on G’, we then continue to find the max feasible flow. We modify a max flow algorithm to set the initial flow as our feasible flow. We also change the residual network construction to never drop below the demand flow.

Question 6

Image segmentation goal

Answer 6

Partition V into V = F union B.

w(F,B) = Sum f() + Sum b() - Sum p(,) where i in F, j in B, (i,j) in E and (i,j) are in F,B or B,F

Find partition (F,B) with max w(F,B)