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

CC BY-SA 3.0
2013-12-26T08:41:25.403Z
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
CC BY-SA 3.0
2013-12-26T10:26:20.390Z
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
CC BY-SA 3.0
2013-12-26T04:31:26.700Z
2013-12-26T04:31:26.700Z
Bangye
<p>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.</p>

CC BY-SA 3.0
2013-12-23T22:06:59.137Z
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
CC BY-SA 3.0
2013-12-24T10:36:28.583Z
Basically yes (except if P=NP, which is unlikely).
domotorp
CC BY-SA 3.0
2013-12-24T10:44:15.593Z
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
CC BY-SA 3.0
2013-12-24T18:20:25.010Z
Yes, it would. Also, if there is one, it would imply P=NP.
domotorp
CC BY-SA 3.0
2013-12-24T20:54:44.037Z
Let's denote then the problem as Problem A. Is something wrong in the following? 1. Problem A is NP-hard. 2. There is no polynomial solution to Problem A, since checking PMCT which is both necessary and sufficient condition for a solution to Problem A is exponential in the number of vertices. 3. Therefore, $P \ne NP$.
MJK
CC BY-SA 3.0
2013-12-25T05:19:35.260Z
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.
domotorp
CC BY-SA 3.0
2014-01-01T22:16:52.870Z
I am trying to do the reduction, but is seems non-trivial. Suppose that I have a graph with the $X$-nodes $x_1,x_2,...x_p$ and the $Y$-nodes $y_1,y_2,...y_q$ where $p \le q$. My first thought was to formulate a 3DM problem with $q$ disjoint sets: $\left( {\left\{ {{y_1}} \right\},\left\{ {{y_2}} \right\},...,\left\{ {{y_q}} \right\}} \right)$, and to connect the points $y_i$ and $y_j$ if they are connected to the same $x_k$. However, since $N$ can be smaller than $q$, I will not necessarily cross all the $y_i$ for a given $x_k$.
MJK
CC BY-SA 3.0
2014-01-02T11:45:40.740Z
Reduction works the other way; you must construct a graph from a 3DM.
domotorp
CC BY-SA 3.0
2014-01-05T13:21:02.657Z
It seems to me that my main problem was with the case $N<M$. In this case, the reduction, if exists, is probably more complicated (e.g., there are $\left( {\begin{array}{*{20}{c}}
  M \\ 
  N 
\end{array}} \right)$ subsets for each $X$-node). Will it still be NP-hard when $N<M$?
MJK
CC BY-SA 3.0
2014-01-05T20:11:02.553Z
yes, just add some dummies to Y
domotorp
CC BY-SA 3.0
2014-01-06T14:56:20.383Z
I thought about this. This way I can choose $M$-size sets where a dummy nodes will serve as the corresponding $X$-node (after reduction). However, I don't see how to ensure that each $X$-node will be of degree $N$.
MJK
CC BY-SA 3.0
2013-12-23T21:25:31.953Z
2013-12-23T21:25:31.953Z
domotorp
<p>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$.</p>

<p>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$).  </p>

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

CC BY-SA 3.0
2013-12-19T08:15:06.093Z
What do you mean by "removing edges"?
Yixin Cao
CC BY-SA 3.0
2013-12-19T08:47:12.500Z
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
CC BY-SA 3.0
2013-12-23T21:25:56.433Z
@D.W.: Thanks for your comment, I reformulated the algorithm.
MJK
<graph-theory><graph-algorithms>
Remove edges from bipartite graph subject to degree restrictions
MJK
# Remove edges from bipartite graph subject to degree restrictions

(Asked by: username_0 on 2013-12-18)

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

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: What do you mean by "removing edges"?  
> **username_0**: 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.  
> **username_0**: @D.W.: Thanks for your comment, I reformulated the algorithm.  

---

## 2 answers

### Answer by username_4 on 2013-12-23. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_4**: Basically yes (except if P=NP, which is unlikely).  
> **username_0**: 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$?  
> **username_4**: Yes, it would. Also, if there is one, it would imply P=NP.  
> **username_0**: Let's denote then the problem as Problem A. Is something wrong in the following? 1. Problem A is NP-hard. 2. There is no polynomial solution to Problem A, since checking PMCT which is both necessary and sufficient condition for a solution to Problem A is exponential in the number of vertices. 3. Therefore, $P \ne NP$.  
> **username_4**: 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.  
> **username_0**: I am trying to do the reduction, but is seems non-trivial. Suppose that I have a graph with the $X$-nodes $x_1,x_2,...x_p$ and the $Y$-nodes $y_1,y_2,...y_q$ where $p \le q$. My first thought was to formulate a 3DM problem with $q$ disjoint sets: $\left( {\left\{ {{y_1}} \right\},\left\{ {{y_2}} \right\},...,\left\{ {{y_q}} \right\}} \right)$, and to connect the points $y_i$ and $y_j$ if they are connected to the same $x_k$. However, since $N$ can be smaller than $q$, I will not necessarily cross all the $y_i$ for a given $x_k$.  
> **username_4**: Reduction works the other way; you must construct a graph from a 3DM.  
> **username_0**: It seems to me that my main problem was with the case $N<M$. In this case, the reduction, if exists, is probably more complicated (e.g., there are $\left( {\begin{array}{*{20}{c}}   M \\    N  \end{array}} \right)$ subsets for each $X$-node). Will it still be NP-hard when $N<M$?  
> **username_4**: yes, just add some dummies to Y  
> **username_0**: I thought about this. This way I can choose $M$-size sets where a dummy nodes will serve as the corresponding $X$-node (after reduction). However, I don't see how to ensure that each $X$-node will be of degree $N$.  

---

### Answer by username_2 on 2013-12-26. Score: 1

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

> **Comments:**
> **username_0**: 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?  
> **username_3**: 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.  

---

