Skip to main content

New answers tagged

1 vote

Weighted bipartite matching with no-cycle constraint

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, \...
Corto's user avatar
  • 101
4 votes

Weighted bipartite matching with no-cycle constraint

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-...
Magnus Wahlström's user avatar

Top 50 recent answers are included