# Remove edges from bipartite graph subject to degree restrictions

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$?

• What do you mean by "removing edges"? Dec 19, 2013 at 8:15
• 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.
– MJK
Dec 19, 2013 at 8:47
• @D.W.: Thanks for your comment, I reformulated the algorithm.
– MJK
Dec 23, 2013 at 21:25

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.

• 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?
– MJK
Dec 23, 2013 at 22:06
• Basically yes (except if P=NP, which is unlikely). Dec 24, 2013 at 10:36
• 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$?
– MJK
Dec 24, 2013 at 10:44
• Yes, it would. Also, if there is one, it would imply P=NP. Dec 24, 2013 at 18:20
• 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. Dec 25, 2013 at 5:19

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

• 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?
– MJK
Dec 26, 2013 at 8:41
• 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. Dec 26, 2013 at 10:26