<p><strong>Lemma.</strong> <em>The problem is NP-hard</em>.</p>

<p><em>Proof.</em> The proof is by reduction from Set Cover with sets of size at most 3 (which itself is NP-hard by an easy reduction from 3D-matching).  Given a collection of sets, each of size at most 3, and an integer $k$, the reduction outputs an instance of your problem where the set $S$ contains the edges of the following DAG: For each element $x$, create an <em>element-vertex</em> $v(x)$.  For each set $s$, create a <em>set-vertex</em> $v(s)$.  Create a <em>root</em> vertex $r$.  Add edges from every vertex (except the root) to the root.  For each set $s$ and element $x\in s$, add edge $(v(x), v(s))$.  All edges have weight 1, and $M\ge 3$ is the number of sets minus $k$.</p>

<p>To show that the reduction is correct, we show that there is a set cover of size $k$ if and only if there is a solution to your problem of cost $M+n$, where $n$ is the number of elements.</p>

<p><em>(only if)</em>. Assume there is a set cover of size $k$.  For the instance output by the reduction, consider a solution with the following edges.  From each element-vertex $v(x)$, take the edge to some $v(s)$ such that $x\in s$ and $s$ is in the set cover.  (Note that each $v(s)$ has at most $3\le M$ edges into it.) From each set-vertex $v(s)$ where $s$ is <em>not</em> in the cover, take an edge from $v(s)$ to the root.  In this solution, the root has $M$ chosen edges into it, and each element-vertex has an edge leaving it, so the total number of edges in the solution is $M+n$.</p>

<p><em>(if).</em> Conversely, suppose the instance output by the reduction has a solution with $M+n$ edges.  Among these edges (by the ILP constraints), the root has at most $M$ (incoming) edges.  Likewise, the solution has at most one edge out of each of the $n$ element-vertices.  Since the solution has $M+n$ edges, and every edge either enters the root or leaves an element vertex, it follows that the solution has exactly $M$ edges entering the root, and exactly one edge leaving each element-vertex, and that no edge in the solution does both, that is, no edge goes from an element-vertex to the root.</p>

<p>It follows that the solution consists of exactly $M$ edges from set-vertices to the root, and exactly $n$ edges from element-vertices, which (by the ILP constraints) must go to the set-vertices that don't have edges to the root in the solution.  There are $k$ of those set-vertices.  Hence, there is a set cover of size $k$. $~~\Box$</p>

CC BY-SA 3.0
2015-05-05T16:51:41.300Z
in your proof there is a bound on $M$, i.e. $M\ge 3$. This number 3 comes from "sets of size at most 3". Does 3 matter here? Can we replace it with any number? (Since there is no constraint on M in the original problem)
sma
CC BY-SA 3.0
2015-05-06T01:08:29.223Z
Using sets of size 3 is not essential.  You could do a reduction from general set cover, but it would be slightly more complicated.  Do you ask because you interested in the case when $M$ is $O(1)$ (i.e., a fixed constant, instead of given in each problem instance)?
Neal Young
CC BY-SA 4.0
2015-05-05T05:56:12.123Z
2018-08-27T13:34:25.493Z
2018-08-27T13:34:25.493Z
Neal Young
<p>This problem is a following up question on  <a href="https://cstheory.stackexchange.com/questions/10727/is-the-following-optimization-problem-a-variant-to-a-previous-problem-np-hard">this one</a>. The only difference is the addition of $3^{rd}$ constraint "$\sum_{i} x_{ij} \le M$", where M is a constant number. This constraint essentially states that each "node" can only take M incoming edges at most.</p>

<p>Set S, which is an non-empty finite subset of $\{ (i,j) : i, j \in N \land i \neq j \}$ and is also a transitive closure, is given. E.g. $S=\{(1,2), (2,3), (1,3), (2,4), (1,4)\}$. For each element $(i,j)$, we have weight $w_{ij}=c(i)&gt;0$, where $c$ is some benefit function, and a binary decision variable $x_{ij}$. The optimization problem is defined as follows:</p>

<p>$$\text{maximize} \sum_{(i,j)\in S} w_{ij}x_{ij} $$
$$\text{s.t.} x_{ij}+x_{ik} \le 1 $$
$$x_{ij}+x_{jk} \le 1 $$
$$\sum_{i} x_{ij} \le M$$</p>

<p>Note this problem is not the <em>Maximum Weighted  Matching</em> problem as edges that share the same end point are allowed. </p>

CC BY-SA 3.0
2012-03-26T12:40:13.000Z
May I ask the motivation of these problems? If you rephrase the problem any-time you get an answer (this is already the third variation), at least tell us why you care.
Juan Bermejo Vega
CC BY-SA 3.0
2012-03-26T13:12:59.807Z
No $x_{ik}+x_{jk} \le 1$?  (More than one selected edge can enter a node?)
Jeffε
CC BY-SA 3.0
2012-03-26T14:28:21.557Z
@Juan Bermejo Vega i'm trying to modeling some graph problem
sma
CC BY-SA 3.0
2012-03-26T16:34:49.120Z
mention the motivation so that others may benefit.
singhsumit
CC BY-SA 3.0
2012-03-26T17:27:08.243Z
defining a graph problem and saying you're interested in it because you're trying to model a graph problem is hardly useful.
Sasho Nikolov
CC BY-SA 3.0
2012-03-27T19:59:12.007Z
@singhsumit are you guys asking motivation examples?There are many and here is one. You can consider each node X is a programmer and each edge X->Y indicates that X joins the project led by Y. The benefit of X is the contribution of X to any project. Each programmer can only participate in one project and each project have a upper bound on the number of members(thus, the 3rd constraint in this version). Many other scenarios can fit into the framework, say ride-sharing, team competition.
sma
CC BY-SA 3.0
2012-03-27T19:59:31.150Z
@Sasho Nikolov pls see the above comment
sma
<cc.complexity-theory><np-hardness>
Is the following optimization problem (another variant to a previous problem) NP-hard?
sma
# Is the following optimization problem (another variant to a previous problem) NP-hard?

(Asked by: username_0 on 2012-03-26)

This problem is a following up question on [this one](https://cstheory.stackexchange.com/questions/10727/is-the-following-optimization-problem-a-variant-to-a-previous-problem-np-hard). The only difference is the addition of $3^{rd}$ constraint "$\sum\_{i} x\_{ij} \le M$", where M is a constant number. This constraint essentially states that each "node" can only take M incoming edges at most.

Set S, which is an non-empty finite subset of $\{ (i,j) : i, j \in N \land i \neq j \}$ and is also a transitive closure, is given. E.g. $S=\{(1,2), (2,3), (1,3), (2,4), (1,4)\}$. For each element $(i,j)$, we have weight $w\_{ij}=c(i)>0$, where $c$ is some benefit function, and a binary decision variable $x\_{ij}$. The optimization problem is defined as follows:

$$\text{maximize} \sum\_{(i,j)\in S} w\_{ij}x\_{ij} $$
$$\text{s.t.} x\_{ij}+x\_{ik} \le 1 $$
$$x\_{ij}+x\_{jk} \le 1 $$
$$\sum\_{i} x\_{ij} \le M$$

Note this problem is not the *Maximum Weighted Matching* problem as edges that share the same end point are allowed.

**Tags:** cc.complexity-theory, np-hardness

> **Comments:**
> **username_1**: May I ask the motivation of these problems? If you rephrase the problem any-time you get an answer (this is already the third variation), at least tell us why you care.  
> **username_2**: No $x_{ik}+x_{jk} \le 1$?  (More than one selected edge can enter a node?)  
> **username_0**: @username_1 i'm trying to modeling some graph problem  
> **username_3**: mention the motivation so that others may benefit.  
> **username_4**: defining a graph problem and saying you're interested in it because you're trying to model a graph problem is hardly useful.  
> **username_0**: @username_3 are you guys asking motivation examples?There are many and here is one. You can consider each node X is a programmer and each edge X->Y indicates that X joins the project led by Y. The benefit of X is the contribution of X to any project. Each programmer can only participate in one project and each project have a upper bound on the number of members(thus, the 3rd constraint in this version). Many other scenarios can fit into the framework, say ride-sharing, team competition.  
> **username_0**: @username_4 pls see the above comment  

---

## 1 answers

### Answer by username_5 on 2015-05-05. Score: 2 | Accepted answer

**Lemma.** *The problem is NP-hard*.

*Proof.* The proof is by reduction from Set Cover with sets of size at most 3 (which itself is NP-hard by an easy reduction from 3D-matching). Given a collection of sets, each of size at most 3, and an integer $k$, the reduction outputs an instance of your problem where the set $S$ contains the edges of the following DAG: For each element $x$, create an *element-vertex* $v(x)$. For each set $s$, create a *set-vertex* $v(s)$. Create a *root* vertex $r$. Add edges from every vertex (except the root) to the root. For each set $s$ and element $x\in s$, add edge $(v(x), v(s))$. All edges have weight 1, and $M\ge 3$ is the number of sets minus $k$.

To show that the reduction is correct, we show that there is a set cover of size $k$ if and only if there is a solution to your problem of cost $M+n$, where $n$ is the number of elements.

*(only if)*. Assume there is a set cover of size $k$. For the instance output by the reduction, consider a solution with the following edges. From each element-vertex $v(x)$, take the edge to some $v(s)$ such that $x\in s$ and $s$ is in the set cover. (Note that each $v(s)$ has at most $3\le M$ edges into it.) From each set-vertex $v(s)$ where $s$ is *not* in the cover, take an edge from $v(s)$ to the root. In this solution, the root has $M$ chosen edges into it, and each element-vertex has an edge leaving it, so the total number of edges in the solution is $M+n$.

*(if).* Conversely, suppose the instance output by the reduction has a solution with $M+n$ edges. Among these edges (by the ILP constraints), the root has at most $M$ (incoming) edges. Likewise, the solution has at most one edge out of each of the $n$ element-vertices. Since the solution has $M+n$ edges, and every edge either enters the root or leaves an element vertex, it follows that the solution has exactly $M$ edges entering the root, and exactly one edge leaving each element-vertex, and that no edge in the solution does both, that is, no edge goes from an element-vertex to the root.

It follows that the solution consists of exactly $M$ edges from set-vertices to the root, and exactly $n$ edges from element-vertices, which (by the ILP constraints) must go to the set-vertices that don't have edges to the root in the solution. There are $k$ of those set-vertices. Hence, there is a set cover of size $k$. $~~\Box$

> **Comments:**
> **username_0**: in your proof there is a bound on $M$, i.e. $M\ge 3$. This number 3 comes from "sets of size at most 3". Does 3 matter here? Can we replace it with any number? (Since there is no constraint on M in the original problem)  
> **username_5**: Using sets of size 3 is not essential.  You could do a reduction from general set cover, but it would be slightly more complicated.  Do you ask because you interested in the case when $M$ is $O(1)$ (i.e., a fixed constant, instead of given in each problem instance)?  

---

