1
$\begingroup$

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.

$\endgroup$
  • 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$ – Juan Bermejo Vega Mar 26 '12 at 12:40
  • 1
    $\begingroup$ No $x_{ik}+x_{jk} \le 1$? (More than one selected edge can enter a node?) $\endgroup$ – Jeffε Mar 26 '12 at 13:12
  • $\begingroup$ @Juan Bermejo Vega i'm trying to modeling some graph problem $\endgroup$ – sma Mar 26 '12 at 14:28
  • 3
    $\begingroup$ mention the motivation so that others may benefit. $\endgroup$ – singhsumit Mar 26 '12 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$ – Sasho Nikolov Mar 26 '12 at 17:27
2
$\begingroup$

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$

$\endgroup$
  • $\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 May 5 '15 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 May 6 '15 at 1:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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