2
$\begingroup$

Given a weighted bipartite graph, I need to find a maximum-weight matching with the following additional constraint: the residual graph of the chosen matching is not allowed to contain any cycles. By residual graph, I mean the graph consisting of:

  • all edges that are not part of the matching, directed from left to right;
  • all edges that are part of the matching, directed from right to left.

For example, consider the graph with left vertices ${a,b,c}$ and right vertices ${A,B,C}$, where the edges and weights are

  • $(a,B): 6$
  • $(a,C): 10$
  • $(b,A): 15$
  • $(b,C): 10$
  • $(c,A): 15$
  • $(c,B): 6.$

Diagram of the example

One possible optimal matching is $(a,C)$ and $(b,A)$ with value $25$. The residual graph (with these edges reversed, in red) is illustrated above. Augmenting this matching with $(c,B)$ is not possible since reversing the direction of the $(c,B)$ edge would create a cycle $a\rightarrow B\rightarrow c\rightarrow A\rightarrow b\rightarrow C\rightarrow a$ in the residual graph.

Is there an algorithm for finding such a matching?

$\endgroup$
1
  • $\begingroup$ @D.W. I've added the definition and a picture above. I mean "residual graph" in the sense of graph you get as you push flow through the graph from left to right, if you interpret the matching problem as maximum-cost max flow. $\endgroup$
    – user168715
    Commented Jun 3 at 20:44

2 Answers 2

4
$\begingroup$

Claim: A matching $M$ has a cycle-free residual graph if and only if the graph $G[V(M)]$ induced on its vertex set has a unique perfect matching.

Given this, the problem is at least as hard as 2-approximation Directed Feedback Vertex Set. Let $D=(V,A)$ be a directed graph and let $G$ be the bipartite graph where every vertex $v_i \in V$ maps to two vertices $u_i, v_i$ in $G$, and $(u_i,v_j)$ is an arc in $G$ if and only if $(v_i,v_j)$ is an arc in $D$ or if $i=j$. Then $G$ has precisely one perfect matching if and only if $D$ is acyclic.

That is, if $S$ is a DFVS of $D$ then deleting both copies of $S$ in $G$ yields a graph with a unique perfect matching, and if $M$ is a matching in $G$ with acyclic residual graph then deleting in $D$ every vertex that does not have both copies in $V(M)$ yields a DFVS for $G$.

Since it is UGC-hard to find a constant-factor approximation for DFVS (reference: Wikipedia), finding a maximum-cardinality matching $M$ of your type is at least UGC-hard.

$\endgroup$
1
$\begingroup$

A more direct answer: this problem is NP-hard.

Reduce from Independent set: $G = (V,E)$ an undirected graph with $V = \{v_1, \ldots, v_n\}$. Build the bipartite graph $B$ whose vertices are $v_1, \ldots, v_n, v'_1, \ldots, v'_n$. Each $v_i$ is connected to $v_i'$ by an edge with weight 1 and for all $i \neq j$, $v_i$ is connected to $v'_j$ by an edge of weight 0 if and only if $\{v_i, v_j\} \in E$ (otherwise they are not connected). The second set of edges ensures that we never select both $\{v_i, v_i'\}$ and $\{v_j, v_j'\}$ when $v_i, v_j$ are neighbours in $G$, as this would create a cycle $v_1-v_i'-v_j-v_j'-v_i$.

It is then straightforward to prove that a matching of weight $k$ in $B$ comes down to finding an independent set with $k$ elements in $G$.

The problem of checking if there is a matching satisfying your requirements and of weight larger than a given $k$ is thus NP-hard. As a consequence, there is no polynomial-time algorithm for your problem unless P=NP.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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