# 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"? – Yixin Cao Dec 19 '13 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 '13 at 8:47
• @D.W.: Thanks for your comment, I reformulated the algorithm. – MJK Dec 23 '13 at 21:25

• 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 '13 at 10:44
• 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 '13 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. – Sasho Nikolov Dec 26 '13 at 10:26