Reducing max flow to bipartite matching?

There's a famous and elegant reduction from the maximum bipartite matching problem to the max-flow problem: we create a network with a source node $s$, a terminal node $t$, and one node for each item to be matched, then add appropriate edges.

There's certainly a way to reduce maximum flow to maximum bipartite matching in polynomial time, since both of them can be each individually be solved in polynomial time. However, is there a "nice" polynomial-time reduction from max-flow (in general graphs) to maximum bipartite matching?

• Are you asking about network flow in a bipartite graph, or in general graphs?
– D.W.
Oct 12, 2016 at 4:46
• I was thinking about max flow in general graphs. Oct 12, 2016 at 16:11
• Poly-time reductions inside P are boring: just solve the instance and pick one of two hard-coded instances. I know that's not what you want, but can you specify more precisely what that is?
– Raphael
Oct 12, 2016 at 22:04
• @Raphael The last paragraph of my question alluded to what you mentioned, since yes, there's clearly a noninteresting reduction along the lines of what you said. I'm looking for a reduction that's more in line with the reduction from matching to max-flow - a structural transform that preserves the essential characteristics. Think something along the lines of the reductions done to prove NP-hardness rather than the trivial reduction of "solve the problem and output an instance." Oct 13, 2016 at 4:56
• Aren't gadget reductions typically linear-time? That's what I mean: try to find a more restricted class that prevents us from "cheating". (It's not clear what "preserves the essential characteristics" should mean.)
– Raphael
Oct 13, 2016 at 8:01

Strangely enough, no such reduction is known. However, in a recent paper, Madry (FOCS 2013), showed how to reduce maximum flow in unit-capacity graphs to (logarithmically many instances of) maximum $b$-matching in bipartite graphs.

In case you are unfamiliar with the maximum $b$-matching problem, this is a generalization of the matching, defined as follows: the input is a graph (in our case, a bipartite graph), $G=(V,E)$, and a set of integral demands for each vertex, with the demand of vertex $v$ denoted by $b_v$. The goal is to find a largest possible set of edges $S$ such that no vertex $v$ has more than $b_v$ edges in $S$ incident on $v$. It is a simple exercise to generalize the reduction from bipartite matching to maximum flows and show a similar reduction from bipartite $b$-matching to maximum flows. (One of) the surprising result(s) of Madry's paper is that in some sense these problems are equivalent, giving a simple reduction which reduces maximum flow in unit-capacity graphs (generally, graphs where the sum of capacities, $|u|_1$ is linear in the number of edges, $m$) to a $b$-matching problem in a graph with $O(m)$ nodes, vertices and sum of demands.

If you're interested in details, see section 3, up to Theorem 3.1 and section 4 (and proof of correctness in Appendix C) of the ArXiv version of Madry's paper, here. If the terminology is not self-evident, see section 2.5 for a recap concerning the $b$-matching problem, and bear in mind that $u_e$ is the capacity of edge $e$ in the original max flow instance.

• There is a classical reduction of vertex disjoint paths to perfect matching in a bipartite graph which generalizes to flows, but requires b-matchings instead. The reduction is easier with node-capacitated flow while the edge-capacitated flow case can be handled by first reducing to node-capacitiated flow --- Madry does it directly (he rediscovered this reduction it seems). You can look at Schrijver's book on Combinatorial Optimization (page 275). Jul 23, 2021 at 2:25

Konig’s theorem on bipartite matchings proved and consequently reduced using the Max-Flow Min-Cut theorem. Konig’s theorem states the following. If G a bipartite graph, then max{|M| : M is a matching } = min{|C| : C is a cover}. Proof. The part max{|M|} ≤ {|C|} is trivial. Let P and Q be the bipartition classes of G. We add two vertices, r and s to G, and arcs rp for every $p\in P$ and qs for every $q \in Q$, and direct edge pq from $p\in P$ to $q\in Q$. This is a digraph $G_{∗}$. We define capacities u(rp) = 1, u(pq) = $\infty$, u(qs) = 1. Let x be a feasible integral flow x, then x(e) = 0 or 1, so we can define M = {$e \in E$ : x(e) = 1}. M is a matching with |M| = $f_{x}$. Next, a matching M in G gives rise to a feasible integral flow x in $G_{∗}$ with flow value $f_{x}$ = |M| as follows. Define x(pq) = 1 if $pq \in M$, x(rp) = 1 if p is incident to an edge in M, x(qs) = 1 if q is incident to an edge in M, in all other cases x(e) = 0. Thus a maximum size matching M in G corresponds to a maximum flow in $G_{∗}$, whose size equals that of a minimum cut by the Max-Flow Min-Cut theorem. Consider a minimum r − s cut δ(R). It has finite capacity, so it contains no arc pq. Then every edge of G is incident with an element of C = (P\R) $\cup (Q \cap R)$, that is, C is a cover. Moreover, u(C) = |P \R|+$|Q \cap R|$ and so C is a cover of size |M|.