<p>Claim: A matching <span class="math-container">$M$</span> has a cycle-free residual graph if and only if the graph <span class="math-container">$G[V(M)]$</span> induced on its vertex set has a unique perfect matching.</p>
<p>Given this, the problem is at least as hard as 2-approximation Directed Feedback Vertex Set. Let <span class="math-container">$D=(V,A)$</span> be a directed graph and let <span class="math-container">$G$</span> be the bipartite graph where every vertex <span class="math-container">$v_i \in V$</span> maps to two vertices <span class="math-container">$u_i, v_i$</span> in <span class="math-container">$G$</span>, and <span class="math-container">$(u_i,v_j)$</span> is an arc in <span class="math-container">$G$</span> if and only if <span class="math-container">$(v_i,v_j)$</span> is an arc in <span class="math-container">$D$</span> or if <span class="math-container">$i=j$</span>. Then <span class="math-container">$G$</span> has precisely one perfect matching if and only if <span class="math-container">$D$</span> is acyclic.</p>
<p>That is, if <span class="math-container">$S$</span> is a DFVS of <span class="math-container">$D$</span> then deleting both copies of <span class="math-container">$S$</span> in <span class="math-container">$G$</span> yields a graph with a unique perfect matching, and if <span class="math-container">$M$</span> is a matching in <span class="math-container">$G$</span> with acyclic residual graph then deleting in <span class="math-container">$D$</span> every vertex that does not have both copies in <span class="math-container">$V(M)$</span> yields a DFVS for <span class="math-container">$G$</span>.</p>
<p>Since it is UGC-hard to find a constant-factor approximation for DFVS (reference: Wikipedia), finding a maximum-cardinality matching <span class="math-container">$M$</span> of your type is at least UGC-hard.</p>

CC BY-SA 4.0
2024-06-05T11:26:19.067Z
2024-06-05T11:26:19.067Z
Magnus Wahlström
<p>A more direct answer: this problem is NP-hard.</p>
<p>Reduce from Independent set:
<span class="math-container">$G = (V,E)$</span> an undirected graph with <span class="math-container">$V = \{v_1, \ldots, v_n\}$</span>.
Build the bipartite graph <span class="math-container">$B$</span> whose vertices are <span class="math-container">$v_1, \ldots, v_n, v'_1, \ldots, v'_n$</span>.
Each <span class="math-container">$v_i$</span> is connected to <span class="math-container">$v_i'$</span> by an edge with weight 1 and for all <span class="math-container">$i \neq j$</span>, <span class="math-container">$v_i$</span> is connected to <span class="math-container">$v'_j$</span> by an edge of weight 0 if and only if <span class="math-container">$\{v_i, v_j\} \in E$</span> (otherwise they are not connected).
The second set of edges ensures that we never select both <span class="math-container">$\{v_i, v_i'\}$</span> and <span class="math-container">$\{v_j, v_j'\}$</span> when <span class="math-container">$v_i, v_j$</span> are neighbours in <span class="math-container">$G$</span>, as this would create a cycle <span class="math-container">$v_1-v_i'-v_j-v_j'-v_i$</span>.</p>
<p>It is then straightforward to prove that a matching of weight <span class="math-container">$k$</span> in <span class="math-container">$B$</span> comes down to finding an independent set with <span class="math-container">$k$</span> elements in <span class="math-container">$G$</span>.</p>
<p>The problem of checking if there is a matching satisfying your requirements and of weight larger than a given <span class="math-container">$k$</span> is thus NP-hard. As a consequence, there is no polynomial-time algorithm for your problem unless P=NP.</p>

CC BY-SA 4.0
2024-06-12T14:46:51.783Z
2024-06-12T14:46:51.783Z
Corto
<p>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:</p>
<ul>
<li>all edges that are <em>not</em> part of the matching, directed from left to right;</li>
<li>all edges that <em>are</em> part of the matching, directed from right to left.</li>
</ul>
<p>For example, consider the graph with left vertices <span class="math-container">${a,b,c}$</span> and right vertices <span class="math-container">${A,B,C}$</span>, where the edges and weights are</p>
<ul>
<li><span class="math-container">$(a,B): 6$</span></li>
<li><span class="math-container">$(a,C): 10$</span></li>
<li><span class="math-container">$(b,A): 15$</span></li>
<li><span class="math-container">$(b,C): 10$</span></li>
<li><span class="math-container">$(c,A): 15$</span></li>
<li><span class="math-container">$(c,B): 6.$</span></li>
</ul>
<p><a href="https://i.sstatic.net/5hDutxHO.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/5hDutxHO.png" alt="Diagram of the example" /></a></p>
<p>One possible optimal matching is <span class="math-container">$(a,C)$</span> and <span class="math-container">$(b,A)$</span> with value <span class="math-container">$25$</span>. The residual graph (with these edges reversed, in red) is illustrated above. Augmenting this matching with <span class="math-container">$(c,B)$</span> is not possible since reversing the direction of the <span class="math-container">$(c,B)$</span> edge would create a cycle <span class="math-container">$a\rightarrow B\rightarrow c\rightarrow A\rightarrow b\rightarrow C\rightarrow a$</span> in the residual graph.</p>
<p>Is there an algorithm for finding such a matching?</p>

CC BY-SA 4.0
2024-06-03T20:44:05.127Z
@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.
user168715
<matching><bipartite-graphs>
Weighted bipartite matching with no-cycle constraint
user168715
# Weighted bipartite matching with no-cycle constraint

(Asked by: username_0 on 2024-06-03)

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](https://i.sstatic.net/5hDutxHO.png)](https://i.sstatic.net/5hDutxHO.png)

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?

**Tags:** matching, bipartite-graphs
> **Comments:**
> **username_0**: @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.  

---

## 2 answers

### Answer by username_1 on 2024-06-05. Score: 4

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.


---

### Answer by username_2 on 2024-06-12. Score: 1

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.


---

