Is the following optimization problem NP-hard? 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)&gt;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.
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&#39;_1, S&#39;_2, ..., S&#39;_m \}$.
Edges are: $(a_j,S_i)$ iff $a_j \in S_i$, and $(S_i,S&#39;_i)$ for all $i$.
Weights are: $w(a_j) = M$ for all $j$, and $w(S_i) = 1$ and $w(S&#39;_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&#39;_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$.