<p>The <strong>new version</strong> of the problem is indeed NP-hard.</p>

<p>Reduction from set cover: Subsets are $S_1, S_2, ..., S_m$ and the universe is $U = \{ a_1, a_2, ..., a_n \}$. Construct a node-weighted directed graph $(N,S,c)$ as follows:</p>

<ul>
<li>Nodes are $N = \{ a_1, a_2, ..., a_n, S_1, S_2, ..., S_m, S&#39;_1, S&#39;_2, ..., S&#39;_m \}$.</li>
<li>Edges are: $(a_j,S_i)$ iff $a_j \in S_i$, and $(S_i,S&#39;_i)$ for all $i$.</li>
<li>Weights are: $w(a_j) = M$ for all $j$, and $w(S_i) = 1$ and $w(S&#39;_i) = 0$ for all $i$.</li>
</ul>

<p>Now if there is a set cover $X$ of size at most $k$, we can get the benefit of at least $nM + m - k$ as follows:</p>

<ul>
<li>For each $a_j$ pick one set $S_i \in X$ in the cover with $a_j \in S_i$, and choose the edge $(a_j,S_i)$; we get the benefit of $M$ from $a_j$.</li>
<li>For each $S_i \notin X$ we choose the edge $(S_i, S&#39;_i)$; we get the benefit of $1$ from $S_i$.</li>
</ul>

<p>Conversely, if we can get the benefit of at least $nM + m - k$, then we have at most $k$ nodes in $\{S_1, S_2, ..., S_m\}$ and all of the nodes in $U$ must have outgoing edges; this gives a set cover of size at most $k$.</p>

CC BY-SA 3.0
2012-03-10T19:10:40.330Z
thanks, seems right except a typo, the benefit from $S_i$ is 1 instead of M
sma
CC BY-SA 3.0
2012-03-10T10:46:04.360Z
2012-03-10T20:02:14.563Z
2012-03-10T20:02:14.563Z
Jukka Suomela
<p>(I am assuming that $N^+$ is some finite set, and I will use the shorthand notation $N = N^+$.)</p>

<p>Let us interpret each $i \in N$ as a <em>node</em> and each $(i,j) \in N$ as a <em>directed edge</em> from $i$ to $j$; now $(N,S)$ is the complete bipartite graph.</p>

<p>The task is to choose a subset $X \subseteq S$ of edges. If we choose an edge $(i,j)$, we get the "benefit" $c(i)$. The constraints are:</p>

<ul>
<li><p>For each node $j$ we can take at most one outgoing edge.</p></li>
<li><p>For each node $j$ we can take only incoming edges or outgoing edges, not both.</p></li>
</ul>

<p>Put otherwise, we are only allowed to choose edges that form disjoint stars (with the edges directed from the leaf nodes towards the center). You get a benefit $c(j)$ for each leaf $j$, and zero benefit for the center.</p>

<p>But now the problem becomes trivial: just find a node $k$ that minimise $c(k)$, and choose all edge $(j,k)$ with $j \ne k$.</p>

CC BY-SA 3.0
2012-03-10T03:01:50.643Z
Based on your answer, I realize that I misstated my question. S is meant to be some subset of the "complete" set instead of the "complete" set. I correct my problem statement. Please take a second look. Thanks
sma
CC BY-SA 3.0
2012-03-10T00:09:22.150Z
2012-03-10T00:09:22.150Z
Jukka Suomela
<p>Set S, which is an <em>non-empty finite subset</em> of $\{ (i,j) : i, j \in N \land i \neq j \}$, is given. E.g. $S=\{(1,3), (2,3), (1,4), (2,4), (3,1), (3,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 $$</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-09T21:43:46.667Z
Yes, I noticed, that's why I deleted my comment, sorry for the confusion.
aelguindy
CC BY-SA 3.0
2012-03-09T22:52:18.170Z
What is N+?  If it means the set of positive integers (which is sometimes written as N+), then S is an infinite set, and the objective function is not well-defined.
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-09T22:56:07.150Z
By the way, it will be helpful if you edit the question to emphasize that the problem is not the maximum weight matching because of the order of subscripts.  An example showing the difference would be great.  (Do not assume that everyone pays attention to subscripts, and do not assume that everyone reads comments.)
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-10T01:58:51.177Z
@Tsuyoshi Ito, I take your advice. Thanks for the comment.
sma
CC BY-SA 3.0
2012-03-10T03:12:36.507Z
Can I interpret the problem as selecting some subset of edges from a directed graph such that no two edges meet tail-to-tail nor head-to tail (but head-to-head is allowed)?
mhum
CC BY-SA 3.0
2012-03-10T03:20:22.323Z
@mhum yes, though I'd refer your head as tail and tail as head. But, essentially, the same.
sma
CC BY-SA 3.0
2012-03-15T17:40:54.273Z
It is not a good practice to change the question significantly after it is answered.  It is better to ask a different question as a separate question which links to this one.
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-15T17:53:34.927Z
@Tsuyoshi Ito, thanks again for your advice.
sma
<cc.complexity-theory><graph-algorithms><np-hardness><optimization><linear-programming>
Is the following optimization problem NP-hard?
sma
# Is the following optimization problem NP-hard?

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

Set S, which is an *non-empty finite subset* of $\{ (i,j) : i, j \in N \land i \neq j \}$, is given. E.g. $S=\{(1,3), (2,3), (1,4), (2,4), (3,1), (3,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 $$

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

**Tags:** cc.complexity-theory, graph-algorithms, np-hardness, optimization, linear-programming

> **Comments:**
> **username_1**: Yes, I noticed, that's why I deleted my comment, sorry for the confusion.  
> **username_2**: What is N+?  If it means the set of positive integers (which is sometimes written as N+), then S is an infinite set, and the objective function is not well-defined.  
> **username_2**: By the way, it will be helpful if you edit the question to emphasize that the problem is not the maximum weight matching because of the order of subscripts.  An example showing the difference would be great.  (Do not assume that everyone pays attention to subscripts, and do not assume that everyone reads comments.)  
> **username_0**: @username_2, I take your advice. Thanks for the comment.  
> **username_3**: Can I interpret the problem as selecting some subset of edges from a directed graph such that no two edges meet tail-to-tail nor head-to tail (but head-to-head is allowed)?  
> **username_0**: @username_3 yes, though I'd refer your head as tail and tail as head. But, essentially, the same.  
> **username_2**: It is not a good practice to change the question significantly after it is answered.  It is better to ask a different question as a separate question which links to this one.  
> **username_0**: @username_2, thanks again for your advice.  

---

## 2 answers

### Answer by username_4 on 2012-03-10. Score: 8 | Accepted answer

The **new version** of the problem is indeed NP-hard.

Reduction from set cover: Subsets are $S\_1, S\_2, ..., S\_m$ and the universe is $U = \{ a\_1, a\_2, ..., a\_n \}$. Construct a node-weighted directed graph $(N,S,c)$ as follows:

* Nodes are $N = \{ a\_1, a\_2, ..., a\_n, S\_1, S\_2, ..., S\_m, S'\_1, S'\_2, ..., S'\_m \}$.
* Edges are: $(a\_j,S\_i)$ iff $a\_j \in S\_i$, and $(S\_i,S'\_i)$ for all $i$.
* Weights are: $w(a\_j) = M$ for all $j$, and $w(S\_i) = 1$ and $w(S'\_i) = 0$ for all $i$.

Now if there is a set cover $X$ of size at most $k$, we can get the benefit of at least $nM + m - k$ as follows:

* For each $a\_j$ pick one set $S\_i \in X$ in the cover with $a\_j \in S\_i$, and choose the edge $(a\_j,S\_i)$; we get the benefit of $M$ from $a\_j$.
* For each $S\_i \notin X$ we choose the edge $(S\_i, S'\_i)$; we get the benefit of $1$ from $S\_i$.

Conversely, if we can get the benefit of at least $nM + m - k$, then we have at most $k$ nodes in $\{S\_1, S\_2, ..., S\_m\}$ and all of the nodes in $U$ must have outgoing edges; this gives a set cover of size at most $k$.

> **Comments:**
> **username_0**: thanks, seems right except a typo, the benefit from $S_i$ is 1 instead of M  

---

### Answer by username_4 on 2012-03-10. Score: 4

(I am assuming that $N^+$ is some finite set, and I will use the shorthand notation $N = N^+$.)

Let us interpret each $i \in N$ as a *node* and each $(i,j) \in N$ as a *directed edge* from $i$ to $j$; now $(N,S)$ is the complete bipartite graph.

The task is to choose a subset $X \subseteq S$ of edges. If we choose an edge $(i,j)$, we get the "benefit" $c(i)$. The constraints are:

* For each node $j$ we can take at most one outgoing edge.
* For each node $j$ we can take only incoming edges or outgoing edges, not both.

Put otherwise, we are only allowed to choose edges that form disjoint stars (with the edges directed from the leaf nodes towards the center). You get a benefit $c(j)$ for each leaf $j$, and zero benefit for the center.

But now the problem becomes trivial: just find a node $k$ that minimise $c(k)$, and choose all edge $(j,k)$ with $j \ne k$.

> **Comments:**
> **username_0**: Based on your answer, I realize that I misstated my question. S is meant to be some subset of the "complete" set instead of the "complete" set. I correct my problem statement. Please take a second look. Thanks  

---

