<p>This is easy to solve in polynomial time.</p>

<p>To see this, it may be easiest to interpret $S$ as a preorder $\le$ on $N$:</p>

<ul>
<li>$i \le j$ iff $(i,j) \in S$ or $i = j$.</li>
</ul>

<p>Then we define the equivalence relation $\sim$:</p>

<ul>
<li>$i \sim j$ iff $i \le j$ and $j \le i$.</li>
</ul>

<p>Now let $W$ consist of all equivalence classes of $\sim$; for each $i \in N$ let $[i] \in W$ be its equivalence class. Put otherwise, $[i]$ consists of all $j \in N$ such that $(j,i) \in S$ and $(i,j) \in S$. Now we can define the natural partial order $\le&#39;$ on $W$:</p>

<ul>
<li>$[i] \le&#39; [j]$ iff $i \le j$ for each $i,j \in N$.</li>
</ul>

<p>We say that $[i] \in W$ is <em>maximal</em> if $[i] \le&#39; [j]$ implies $[i] = [j]$. We have the following property that is easy to verify:</p>

<ul>
<li>If $[i]$ is maximal, we cannot get the benefit $c(j)$ for all $j \in [i]$.</li>
</ul>

<p>Hence in any solution, for every maximal class $[i]$, we have to choose at least one node $j \in [i]$ such that we do not get the benefit of $c(j)$.</p>

<p>We now construct a solution as follows: For each maximal class $[i]$, choose a node $j \in [i]$ that minimises $c(j)$; we say that $j$ is a <em>sink node</em>. Now assume that $k \in N$ is not a sink node. There are too cases:</p>

<ul>
<li><p>$k \in [i]$, where $[i]$ is maximal. Now we can simply choose the edge $(k,j) \in S$, where $j \in [i]$ is a sink node, and collect the benefit of $c(k)$.</p></li>
<li><p>$k \in [i]$, where $[i]$ is not maximal. Then there is a maximal set $[\ell]$ with $[i] \le [\ell]$. Let $j \in [\ell]$ be the sink node, choose the edge $(k,j) \in S$, and collect the benefit of $c(k)$.</p></li>
</ul>

<p>That is, we can get the benefit of $c(k)$ for all nodes $k \in N$ that are not sink nodes; the solution is optimal.</p>

CC BY-SA 3.0
2012-03-15T18:14:03.497Z
2012-03-15T18:14:03.497Z
Jukka Suomela
<p>This problem is a following up question on  <a href="https://cstheory.stackexchange.com/questions/10615/is-the-following-optimization-problem-np-hard">this one</a>. The only difference is the newly added constraint in the bold font.</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 <strong><em>transitive closure</em></strong>, 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 $$</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.complexity-theory><np-hardness>
Is the following optimization problem (a variant to a previous problem) NP-hard?
sma
# Is the following optimization problem (a variant to a previous problem) NP-hard?

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

This problem is a following up question on [this one](https://cstheory.stackexchange.com/questions/10615/is-the-following-optimization-problem-np-hard). The only difference is the newly added constraint in the bold font.

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

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

---

## 1 answers

### Answer by username_1 on 2012-03-15. Score: 9 | Accepted answer

This is easy to solve in polynomial time.

To see this, it may be easiest to interpret $S$ as a preorder $\le$ on $N$:

* $i \le j$ iff $(i,j) \in S$ or $i = j$.

Then we define the equivalence relation $\sim$:

* $i \sim j$ iff $i \le j$ and $j \le i$.

Now let $W$ consist of all equivalence classes of $\sim$; for each $i \in N$ let $[i] \in W$ be its equivalence class. Put otherwise, $[i]$ consists of all $j \in N$ such that $(j,i) \in S$ and $(i,j) \in S$. Now we can define the natural partial order $\le'$ on $W$:

* $[i] \le' [j]$ iff $i \le j$ for each $i,j \in N$.

We say that $[i] \in W$ is *maximal* if $[i] \le' [j]$ implies $[i] = [j]$. We have the following property that is easy to verify:

* If $[i]$ is maximal, we cannot get the benefit $c(j)$ for all $j \in [i]$.

Hence in any solution, for every maximal class $[i]$, we have to choose at least one node $j \in [i]$ such that we do not get the benefit of $c(j)$.

We now construct a solution as follows: For each maximal class $[i]$, choose a node $j \in [i]$ that minimises $c(j)$; we say that $j$ is a *sink node*. Now assume that $k \in N$ is not a sink node. There are too cases:

* $k \in [i]$, where $[i]$ is maximal. Now we can simply choose the edge $(k,j) \in S$, where $j \in [i]$ is a sink node, and collect the benefit of $c(k)$.
* $k \in [i]$, where $[i]$ is not maximal. Then there is a maximal set $[\ell]$ with $[i] \le [\ell]$. Let $j \in [\ell]$ be the sink node, choose the edge $(k,j) \in S$, and collect the benefit of $c(k)$.

That is, we can get the benefit of $c(k)$ for all nodes $k \in N$ that are not sink nodes; the solution is optimal.


---

