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

This problem is a following up question on this one. The only difference is the addition of $3^{rd}$ constraint "$\sum_{i} x_{ij} \le M$", where M is a constant number. This constraint essentially states that each "node" can only take M incoming edges at most.

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$$ $$\sum_{i} x_{ij} \le M$$

Note this problem is not the Maximum Weighted Matching problem as edges that share the same end point are allowed.

• May I ask the motivation of these problems? If you rephrase the problem any-time you get an answer (this is already the third variation), at least tell us why you care. – Juan Bermejo Vega Mar 26 '12 at 12:40
• No $x_{ik}+x_{jk} \le 1$? (More than one selected edge can enter a node?) – Jeffε Mar 26 '12 at 13:12
• @Juan Bermejo Vega i'm trying to modeling some graph problem – sma Mar 26 '12 at 14:28
• mention the motivation so that others may benefit. – singhsumit Mar 26 '12 at 16:34
• defining a graph problem and saying you're interested in it because you're trying to model a graph problem is hardly useful. – Sasho Nikolov Mar 26 '12 at 17:27

Lemma. The problem is NP-hard.

Proof. The proof is by reduction from Set Cover with sets of size at most 3 (which itself is NP-hard by an easy reduction from 3D-matching). Given a collection of sets, each of size at most 3, and an integer $k$, the reduction outputs an instance of your problem where the set $S$ contains the edges of the following DAG: For each element $x$, create an element-vertex $v(x)$. For each set $s$, create a set-vertex $v(s)$. Create a root vertex $r$. Add edges from every vertex (except the root) to the root. For each set $s$ and element $x\in s$, add edge $(v(x), v(s))$. All edges have weight 1, and $M\ge 3$ is the number of sets minus $k$.

To show that the reduction is correct, we show that there is a set cover of size $k$ if and only if there is a solution to your problem of cost $M+n$, where $n$ is the number of elements.

(only if). Assume there is a set cover of size $k$. For the instance output by the reduction, consider a solution with the following edges. From each element-vertex $v(x)$, take the edge to some $v(s)$ such that $x\in s$ and $s$ is in the set cover. (Note that each $v(s)$ has at most $3\le M$ edges into it.) From each set-vertex $v(s)$ where $s$ is not in the cover, take an edge from $v(s)$ to the root. In this solution, the root has $M$ chosen edges into it, and each element-vertex has an edge leaving it, so the total number of edges in the solution is $M+n$.

(if). Conversely, suppose the instance output by the reduction has a solution with $M+n$ edges. Among these edges (by the ILP constraints), the root has at most $M$ (incoming) edges. Likewise, the solution has at most one edge out of each of the $n$ element-vertices. Since the solution has $M+n$ edges, and every edge either enters the root or leaves an element vertex, it follows that the solution has exactly $M$ edges entering the root, and exactly one edge leaving each element-vertex, and that no edge in the solution does both, that is, no edge goes from an element-vertex to the root.

It follows that the solution consists of exactly $M$ edges from set-vertices to the root, and exactly $n$ edges from element-vertices, which (by the ILP constraints) must go to the set-vertices that don't have edges to the root in the solution. There are $k$ of those set-vertices. Hence, there is a set cover of size $k$. $~~\Box$

• in your proof there is a bound on $M$, i.e. $M\ge 3$. This number 3 comes from "sets of size at most 3". Does 3 matter here? Can we replace it with any number? (Since there is no constraint on M in the original problem) – sma May 5 '15 at 16:51
• Using sets of size 3 is not essential. You could do a reduction from general set cover, but it would be slightly more complicated. Do you ask because you interested in the case when $M$ is $O(1)$ (i.e., a fixed constant, instead of given in each problem instance)? – Neal Young May 6 '15 at 1:08