Skip to main content
4 votes
Accepted

Complexity of maximum k-edge-colorable subgraph of a bipartite graph

A bipartite multigraph is $k$-edge colorable iff the maximum degree of any vertex is at most $k$. So we are asking for a subgraph $H=(V,F)$ of a given bipartite graph $G=(V,E)$ such that $\delta_H(v) \...
Chandra Chekuri's user avatar
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
2 votes

Constrained Bipartite Matching

This problem captures the maximum independent set problem, which is NP-hard, as follows. Suppose we wish to decide if a graph $H = (V_H, E_H)$ has an independent set of size $\ge k$. We construct $G = ...
Laakeri's user avatar
  • 1,786
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
  • 136
1 vote

Complexity and Algorithm for specific Vertex Separator Problem

I understand that the question is about the time bound, not about the correctness of the reduction. The claim does not sound obvious (although a bound of $\mathcal{O}(n^3n^2k)$ can be shown with a ...
Vinicius dos Santos's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible