9
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ Are you asking about network flow in a bipartite graph, or in general graphs? $\endgroup$
    – D.W.
    Oct 12, 2016 at 4:46
  • $\begingroup$ I was thinking about max flow in general graphs. $\endgroup$ Oct 12, 2016 at 16:11
  • 1
    $\begingroup$ 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? $\endgroup$
    – Raphael
    Oct 12, 2016 at 22:04
  • $\begingroup$ @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." $\endgroup$ Oct 13, 2016 at 4:56
  • $\begingroup$ 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.) $\endgroup$
    – Raphael
    Oct 13, 2016 at 8:01

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$ Jul 23, 2021 at 2:25
-2
$\begingroup$

So here is a try at answering your question:

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|.

I mean this is everything in my opinion that you asked in the question and this is my potential answer :).

$\endgroup$
4
  • 2
    $\begingroup$ Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$
    – D.W.
    Oct 12, 2016 at 21:21
  • 1
    $\begingroup$ Can you clarify how this answers the question? Are you constructing an algorithm to solve the max-flow problem in general graphs, using an algorithm for maximum bipartite matching? If so, what is the algorithm? It seems like all you are doing is showing how to solve the max-flow problem for the special case of bipartite graphs in the special case where all capacities are 1. But of course that problem is trivially equivalent to maximum matching, as the question already explains, so I'm not seeing how this adds anything new. I also don't see how Konig's theorem or vertex covers are relevant. $\endgroup$
    – D.W.
    Oct 12, 2016 at 21:22
  • $\begingroup$ The reduction in this case is the key to answer the question set. And I believe this in exactly what @templatetypedef is looking for. I do not believe that polynomial-time reduction from max-flow (in general graphs) would be different. I will think about it again and perhaps add something extra but I can hardly see why we would need different instances to have a more general reduction. But fair points. $\endgroup$ Oct 12, 2016 at 21:38
  • $\begingroup$ This is the standard textbook reduction FROM bipartite matching TO maximum flow. The question is asking for a reduction in the opposite direction: FROM maximum flow TO bipartite matching. $\endgroup$
    – JeffE
    Mar 29, 2017 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.