Is the following optimization problem NP-hard?

Question

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.

Answer 1

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

Answer 2

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