# 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)>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.

• Yes, I noticed, that's why I deleted my comment, sorry for the confusion. – aelguindy Mar 9 '12 at 21:43
• What is N+? If it means the set of positive integers (which is sometimes written as N+), then S is an infinite set, and the objective function is not well-defined. – Tsuyoshi Ito Mar 9 '12 at 22:52
• By the way, it will be helpful if you edit the question to emphasize that the problem is not the maximum weight matching because of the order of subscripts. An example showing the difference would be great. (Do not assume that everyone pays attention to subscripts, and do not assume that everyone reads comments.) – Tsuyoshi Ito Mar 9 '12 at 22:56
• Can I interpret the problem as selecting some subset of edges from a directed graph such that no two edges meet tail-to-tail nor head-to tail (but head-to-head is allowed)? – mhum Mar 10 '12 at 3:12
• It is not a good practice to change the question significantly after it is answered. It is better to ask a different question as a separate question which links to this one. – Tsuyoshi Ito Mar 15 '12 at 17:40

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

• thanks, seems right except a typo, the benefit from $S_i$ is 1 instead of M – sma Mar 10 '12 at 19:10

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

• Based on your answer, I realize that I misstated my question. S is meant to be some subset of the "complete" set instead of the "complete" set. I correct my problem statement. Please take a second look. Thanks – sma Mar 10 '12 at 3:01