0
$\begingroup$

Assume we have a set of $n$ objects $X=\{x_1,x_2,\ldots,x_n\}$, where each object $x_i$ has a penalty $p_i$. Additionally, we have a set of incompatibility constraints $C=\{(x_i,x_j),\ldots\}$, where a tuple $(x_i,x_j)$ says that object $x_i$ is incompatible with object $x_j$. The problem is to find a subset $Y$ of $k<n$ compatible objects that minimize the sum of penalties, i.e. $\min_{Y} \sum_{x_i \in Y} p_i$. The objects in $Y$ need to be compatible, i.e. $\forall x_i,x_j \in Y: (x_i,x_j) \not\in C$.

Let me make an example. Assume we have 4 objects $X=\{x_1,\ldots,x_4\}$ with penalties $p_1 = 2,\ p_2 = 0.1,\ p_3=3,\ p_4=100$. Furthermore the following incompatibilities are given: $C=\{(x_1,x_2),\ (x_2,x_3),\ (x_3,x_4)\}$. The $k=2$ compatible objects that minimize the function are $Y = \{x_1,x_3\}$ with a total penalty of $5$. Object $x_2$ with the least penalty is not part of the solution, because the only compatible object is $x_4$ with a penalty $p_4=100$.

I have two questions:

  • Is this problem already known under some name or a variation of a known problem?
  • Is there an efficient (polynomial time) algorithm to solve it?
$\endgroup$
1
$\begingroup$

First of all you have to find if there exist independent sets of size $k$ and then select the one with the minimum penalty. We have maximum weighted independent problem (size of independent set is unconstrained), but I am not aware of any optimization problem which select exactly $k$-sized independent set and minimizes/maximizes the total weight.

The decision version of the optimization problem that you describe will be: Does there exist an independent set of size $k$ and penalty less than or equal to $P$.

We can reduce standard independent set problem to this problem by specifying the penalty of each vertex as 1 and $P = k$. Thus the decision version of the described optimization problem is NP-complete.

So there won't be polynomial time algorithm for the problem unless $P = NP$.

$\endgroup$
1
$\begingroup$

Well, the graph is obvious, isn't it? Independent set

$\endgroup$

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.