# Is the following optimization problem (a variant to a previous problem) NP-hard?

This problem is a following up question on this one. 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.

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.