6
$\begingroup$

I have this problem, which I haven't seen before in the literature: given a bipartite graph and a natural number $k$, can we select at least $k$ of the edges such that each left-hand vertex is incident to exactly two or exactly zero selected edges, and each right-hand vertex is incident to at most one selected edge?

Obviously if replace "two" with one we have the matching problem, which can be solved in polynomial time. I've tried in vain to solve my problem using network flow or matching, and am also stumped when I try to reduce from NP-complete problems.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ @Marzio Thanks a lot for the idea. I don't think this method always works though. For example, suppose $|L|=1$, $|R|=100$, and there is an edge from the unique vertex in $L$ to each vertex in $R$. If I'm not mistaken, the maximum matching in $G'$ has 50 edges. $\endgroup$
    – James Trimble
    Feb 19, 2016 at 19:53
  • $\begingroup$ You're right, it's trickier; I delete the comment and think a little bit more about it ... $\endgroup$
    – Marzio De Biasi
    Feb 19, 2016 at 19:56
  • $\begingroup$ Perhaps this variation works; let $G= (L \cup R, E)$ be the given bipartite graph ($L, R$ are the Left and Right sets). Build a flow graph $G' = (V',E')$ in this way: for each pair $v_i, v_j \in R$ add a node $v'_{i,j}$; for each $u_h \in L$ add a node $u'_h$ and if $ (u_h,v_1)...(u_h,v_s) \in E$ add edges $e'_{h,i,j} = (u'_h,v'_{i,j}) \in E'\; 1 \leq i < j \leq s$. Finally add a source $s'$ connected to the $u'_h$ and connect each $v'_{i,j}$ to a common sink $t'$. Every edge of $E'$ has capacity $1$; calculate the max-flow from $s'$ to $t'$. $\endgroup$
    – Marzio De Biasi
    Feb 19, 2016 at 20:56
  • 2
    $\begingroup$ related: cstheory.stackexchange.com/q/31882/15637 $\endgroup$
    – Thomas Kalinowski
    Feb 19, 2016 at 22:18
  • $\begingroup$ @MarzioDeBiasi Thanks for the suggestion. I think this doesn't work if $|L|=|R|$ and there is an edge from each vertex in $L$ to each vertex in $R$. In this case, there are enough $v'_{i,j}$ vertices that we can have a flow of $k$ from $s'$ to $t'$. $\endgroup$
    – James Trimble
    Feb 20, 2016 at 10:50

1 Answer 1

Reset to default
9
$\begingroup$

The answer here seems to imply there is a more general result. For this particular case, here is a self contained way to reduce the problem to maximum weight perfect matching. Assume $k$ is even.

Given $G=(L\cup R, E)$, we construct a new graph $G'=(V',E')$ as follows, let $|R|=n$.

  1. Add vertices in $R$ to $V'$.
  2. For each vertex $v \in L$, add vertices $v_1,v_2$ to $V'$.
  3. Add vertices $t_1,\ldots,t_{n-k}$ to $V'$.
  4. Add edge $v_1v_2$ to $E'$ for each $v\in L$. It has weight $0$.
  5. Add edge $v_iu$ to $E'$ for each $vu\in E$,$u\in R,v\in L,i\in \{1,2\}$. It has weight $1$.
  6. Add edge $ut_i$ for each $u\in R$ and $1\leq i\leq n-k$. It has weight $0$.

Claim: The maximum weight perfect matching in $G'$ has value $k$ iff the "two or zero" matching has a solution of at least $k$ edges.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Perfect! Thanks very much. Even better, this looks like it will work if we want to find a maximum weighted "two or zero" matching. $\endgroup$
    – James Trimble
    Feb 20, 2016 at 10:52
  • 2
    $\begingroup$ @JamesTrimble no problem. I'm curious about how this problem come up. $\endgroup$
    – Chao Xu
    Feb 20, 2016 at 17:51
  • 2
    $\begingroup$ It's related to a project for a client that, unfortunately, I can't write in detail about here. The theoretical problem is just for fun. I was discussing it with friends and we worked out that "one or zero" matching is in P (since it's just matching) and "three or zero" matching is NP-complete (by a simple reduction from 3D matching, with an element in $R$ created for each vertex in the 3D matching problem, and an element in $L$ created for each hyperedge). We got stuck at "two or zero"! $\endgroup$
    – James Trimble
    Feb 22, 2016 at 17:55

Your Answer

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

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