patternMinor
Reducing max flow to bipartite matching?
Viewed 0 times
flowreducingbipartitemaxmatching
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#64499, answer score: 7
Revisions (0)
No revisions yet.