7.7 Extensions to the Maximum-Flow Problem

• Directed graph G = (V, E)
• Edge capacities c(e), e ∈ E
• Node supply and demands d(v), v ∈ V:
  • If d(v) > 0: node v has demand of d(v) flow–> The node is a sink and wishes to receive d(v) units more flow than it sends out
  • If d(v) < 0: The node v has a supply of -d(v)–> The node is a source and wishes to send out -d(v) units more flow than it receives
  • If d(v) = 0: Then the node is neither a source nor a sink.
• A circulation is a function that satisfies:
  • For each e ∈ E: 0 ≤ f(e) ≤ c(e) (capacity condition)
  • For each v ∈ V: fⁱⁿ(v) - f^out(v) = d(v)(Demand conditions)
• Feasibility Problem: We want to know if there exists a circulation that satisfies the just-mentioned conditions
• If there exists a feasible circulation with demands {d(v)}, then ∑_v d(v) =0
  

• The problem of finding feasible circulation can be reduced to the problem of finding a maximum s-t flow in a different network.
• 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)
• ∑_v:d(v)>0d(v) = ∑_{v:d(v)< 0}-d(v). Let's call this common value D.
• Claim: G has circulation iff G' has max flow of value D
• Given (V, E, c, d), there does not exist a circulation iff there exists a node partition (A, B) such that:
  • Σ_v∈B d(v) > cap(A, B) ⇒ demand by nodes in B exceeds supply of nodes in B + max capacity of edges going from A –> B
    

• In many problems, not only do we want to satisfy demands at various nodes, but we also want to enforce the flow to make use of certain edges.
• That's why we need to place lower bounds on edges as well as the upper bounds restricted by the capacities
• Feasible circulation
  • Directed graph G = (V, E)
  • Edge capacities c(e) and lower bounds l(e)(Force flow to use certain edges), e ∈ E
  • Node supply and demands d(v), v ∈ V
• A circulation is a function that satisfies:
  • For each e ∈ E: 0 ≤ l(e) ≤ f(e) ≤ c(e) (capacity)
  • For each v ∈ V: fⁱⁿ(v) - f^out(v) = d(v)(conservation)
  • Goal: Decide whether or not there exists a feasible circulation(the circulation that satisfies the above conditions)
    

• Strategy: Reduce the problem to the one of finding a circulation with demands but no lower bounds, which can in turn be reduced to the Maximum-Flow Problem.
• How to proceed?:
  • On each edge, we need to send at least l(e) units of flow.
  • Update demands of both endpoints
    

I give this section a 7/10.