Is the following optimization problem (a variant to a previous problem) NP-hard?
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&#39;$ on $W$:


$[i] \le&#39; [j]$ iff $i \le j$ for each $i,j \in N$.


We say that $[i] \in W$ is maximal if $[i] \le&#39; [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.