Weighted bipartite matching with no-cycle constraint

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

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?

• @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. Commented Jun 3 at 20:44

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.

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.