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.

  • 5
    $\begingroup$ 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. $\endgroup$ Commented Mar 26, 2012 at 12:40
  • 1
    $\begingroup$ No $x_{ik}+x_{jk} \le 1$? (More than one selected edge can enter a node?) $\endgroup$
    – Jeffε
    Commented Mar 26, 2012 at 13:12
  • $\begingroup$ @Juan Bermejo Vega i'm trying to modeling some graph problem $\endgroup$
    – sma
    Commented Mar 26, 2012 at 14:28
  • 3
    $\begingroup$ mention the motivation so that others may benefit. $\endgroup$
    – singhsumit
    Commented Mar 26, 2012 at 16:34
  • 3
    $\begingroup$ defining a graph problem and saying you're interested in it because you're trying to model a graph problem is hardly useful. $\endgroup$ Commented Mar 26, 2012 at 17:27

1 Answer 1


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$

  • $\begingroup$ 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) $\endgroup$
    – sma
    Commented May 5, 2015 at 16:51
  • $\begingroup$ 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)? $\endgroup$
    – Neal Young
    Commented May 6, 2015 at 1:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.