Haonan's blog

Applications of Max flow

 
  • Sep 13, 2023

This blog talks about two applications of Max flow problem, that are bipartite matching problem and edge-disjoint path problem

Bipartite Matching

Matching Problem

  • Input: undirected graph $G=(V,E)$
  • A matching $M \subseteq E$ where each node appears in at most one edge.
  • Maximum Matching: Maximum possible size of $M$.
  • Maximal Matching: Matching that can’t be extended further.

Bipartite Matching Problem

Bipartite graph: Graph whose vertex set can be partitioned into two disjoint sets such that no two vertices from the same set are adjacent. We will try to solve the maximum matching problem in bipartite graph.

Reduction

Definition of Reduction

Problem ${ X }$ reduces to Problem ${ Y }$, ${ \underset{\text{p}}{\leq} }$ means that if ${ \exists }$ a polynomial algorithm that given any instance ${x }$ of ${ X }$, converts ${ x }$ to an instance ${ y \in Y }$ s.t. the solution of ${ y }$ can be converted to a solution of ${ x }$. (For more rigorous definition, move to this blog)

Reduction from Bipartite Matching to Max flow

  • Input: an undirected bipartite graph $G=(L \cup R, E)$.
  • Create a directed graph $G’=(V’, E’)$ as follows:
    • $V’ = ( L’ \cup R’ \cup {s,t} )$ where $L’ = L, R’ = R$
      • $s$: source
      • $t$: sink
    • Construct $E’$ as below:
      1. For each edge $e \in E$, copy it from $L’$ to $R’$.
      2. Add edges from $s$ to each node in $L’$
      3. Add an edge from each node in $R’$ to $t$.

Theorem: Size of the Maximum Matching in $G$ is equal to Max Flow in $G’$.

Proof.

1) Maximum Matching of $G$ $\leq$ Max Flow in $G’$.

  • Let $M$ be the edge set of maximum matching.
  • Denote the size of the Max Matching in $G$ be $m$.
  • Construct a flow $f$ by sending flow of value 1 through each edge of $M$. We know flow $f$ is valid and $v(f) = m$
  • Then $v(f_\max) \geq v(f) = m = \vert M \vert$. 2) Maximum Matching in $G$ $\geq$ Max Flow in $G’$.
  • Let $f_\max$ be the max flow in $G’$ with value $m$.
  • By integrality, we can find a flow where the flow is integral. If the capacity is 1, the flow value of every edge is either 0 or 1.
  • Let $M$ be the set of edges from $L’$ to $R’$ with flow value 1. Thus $ M = m$.
  • As all the capacities are 1 and flow needs to be conserved, each node in $L’$ and $R’$ participates in at most one edge in $M$.
  • Thus the edges in $M$ are vertex disjoint and forms a Matching set. That means $\vert M_\max \vert \geq \vert M \vert = m= v(f_\max) $. $\square$

Edge-Disjoint Path

Definition of Problem

Edge-Disjoint Path: Two $s-t$ paths are edge disjoint if they share no edges.

Edge-Disjoint Path Problem: Given a direct graph $G=(V, E)$ and two nodes $s, t$, the objective is to find all edge disjoint paths from $s$ to $t$.

Reduction from Edge-Disjoint Path to Max flow

We can construct the Max flow instance based on edge-disjoint path instance by adding capacity $1$ to each edge.

Theorem: Max Flow in $G’$ = #disjoint paths in $G$.

Proof.

1) Max Flow in $G’$ $\geq$ number of disjoint paths in $G$.

  • Let assume there are $m$ disjoint paths $P_1, …, P_m$ in $G$.
  • We construct a flow $f$, by setting flow of each edge in path $P_1,\cdots,P_m$, to $1$.
  • Note each path contributes one unit in the flow. As we have$m$ disjoint paths, $v(f) =m$. That means $v(f_\max) \geq v(f) = m$.

2) Max Flow in $G’$ $\leq$ number of disjoint paths in $G$.

  • Assume $G’$ has a max flow $f_\max$ of value $m$.
  • By integrality we assume flow is either 0 or 1.
  • Now we trace a path from $s$ to $t$ as follows:
    • By following flow conservation for each edge, if $f(s,u) = 1$ there must exists some $v$ such that $f(u,v) = 1$.
    • Continue this tracing until we reach $t$. Each adjacent node of $s$ gives one $s-t$ path.
  • As the value of max flow is $m$, we get total $m$ paths as each path carries a flow of value $1$ and each edge can’t be present in two different flows as its capacity is $1$. That means the number of disjoint paths in $G$ is at least $m$. $\square$
Search