2
$\begingroup$

I have a bipartite graph $G$ with two sets of vertices $X$ and $Y$, where the degree of each vertex in $X$ is exactly $M$.

I now must remove some of the edges to ensure that, after removal, no vertex in $Y$ will have a degree larger than $1$. I want to choose a way to remove the edges so that as many vertices in $X$ have degree at least $N$ (where $N$ is given to me, $N \le M$).

How can I find the maximum number of vertices in $X$ whose degree will be at least $N$ after removal, subject to the restriction that after removal no vertex in $Y$ should have degree larger than $1$?

$\endgroup$
  • $\begingroup$ What do you mean by "removing edges"? $\endgroup$ – Yixin Cao Dec 19 '13 at 8:15
  • $\begingroup$ Each vertex in X is connected to M vertices in Y. You thus have |X|M edges. You can decide which edges should be removed such that you will end up with as many vertices with degree at least N as possible, such that there is no vertex in Y with degree 2 or more. $\endgroup$ – MJK Dec 19 '13 at 8:47
  • $\begingroup$ @D.W.: Thanks for your comment, I reformulated the algorithm. $\endgroup$ – MJK Dec 23 '13 at 21:25
6
$\begingroup$

This problem is NP-hard as 3DM (3-dimensional matching problem) reduces to it. Just pick M=N=3, Y to be the points of the underlying base set, and X to be the triples on them.

$\endgroup$
  • $\begingroup$ Thanks. I also understand that 3DM as a decision problem is NP-complete. My background in the field of complexity theory is somewhat limited, but if PMCT is both necessary and sufficient condition, doesn't it imply that it is not possible to find a polynomial solution for this problem? Doesn't it imply in turn that it is not possible to find a polynomial solution to any equivalent problem? $\endgroup$ – MJK Dec 23 '13 at 22:06
  • $\begingroup$ Basically yes (except if P=NP, which is unlikely). $\endgroup$ – domotorp Dec 24 '13 at 10:36
  • $\begingroup$ But if there is no polynomial solution to my problem, which is equivalent to all NP-complete problems, doesn't it imply that $P \ne NP$? $\endgroup$ – MJK Dec 24 '13 at 10:44
  • $\begingroup$ Yes, it would. Also, if there is one, it would imply P=NP. $\endgroup$ – domotorp Dec 24 '13 at 18:20
  • 1
    $\begingroup$ Yes, the problem is in 2. There might be a more efficient way to check PMCT than checking it for all subgraphs. E.g., for the original marriage theorem you could also give an exp size necessary and sufficient condition but there we know that a polynomial solution exists. $\endgroup$ – domotorp Dec 25 '13 at 5:19
1
$\begingroup$

When N<3, you may have polynomial time algorithms. For N=1, it is equivalent to the bipartite maximum matching problem.

$\endgroup$
  • 1
    $\begingroup$ I was aware of the case $N=1$ (finding an $X$-saturating match), but I didn't know that it can be extended to $N=2$. Can you give the algorithm for $N=2$? I assume that you agree that for $N>2$ this problem is NP-hard? $\endgroup$ – MJK Dec 26 '13 at 8:41
  • 2
    $\begingroup$ I think you can reduce the $N=2$ case to a variant of non-bipartite matching. Create a multigraph with vertices $X$, and include an edge between $x_1$ and $x_2$ labeled by $y$, if there exists a length two path $x_1 - y - x_2$ in the original bipartite graph. Now the problem is to find the maximum matching in this multigraph, where the size of the matching is measured by the number of distinct edge labels. I suspect algorithms based on the matching polytope (e.g. Edmonds' algorithm) can be adapted to solve this problem. $\endgroup$ – Sasho Nikolov Dec 26 '13 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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