2
$\begingroup$

The problem:

I have a list $\displaystyle S=\{s_{1} ,s_{2} ,\dotsc ,s_{n}\}$ places. Each unordered pair of places has cost and gain: $\displaystyle c\{s_{i} ,s_{j}\} \in \mathbb{N}$, $\displaystyle g\{s_{i} ,s_{j}\} \in \mathbb{N}$. Also the pairs are only for $\displaystyle i\neq j$.

I have two numbers: $ $$\displaystyle b\in \mathbb{N}$, $\displaystyle p\in \mathbb{N}$.

The problem is to check wether it exist a combination of pairs such that:

$\displaystyle c_{1} +c_{2} +\dotsc +c_{m} \leqslant b$ and $\displaystyle g_{1} +g_{2} +\dotsc +g_{m} \geqslant p$. Where of course $\displaystyle c_{i} ,g_{i}$ are cost and gain of a used pair $s_i$.

To show it is NP-complete I have to show a Karp reduction.


There are some problems we've studies and so that I can use:

Clique, Composite, SAT - Satisfiability problem, 3SAT, CSAT, IS - Independent Set, VC - Vertex, Cover, DHC - Directed Hamilton Cycle, HC - Hamilton Cycle, DS - Dominating Set, SSS - Subset, Set, 3COL, Partition, Bin-Packing.

Since it's talking about a sum I thought of using Subset-sum. If I set $\displaystyle p=b=k$, and I set $\displaystyle c_{i} =g_{i}$ for each $\displaystyle i$, then it really is just a sum question, to find a combination of elements of sum $\displaystyle k$.

But what it's complicating it for me is that if I have $\displaystyle n$ elements, I will have $\displaystyle \frac{n^{2} -n}{2}$ pairs, and so these many different costs. How can I rewrite the $\displaystyle n$ elements of partition, into some $\displaystyle k$ elements here such that there are $\displaystyle \frac{k^{2} -k}{2} =n$ pairs?

I've thought maybe I can only assign the cost to the first $\displaystyle n$ elements, and then all the rest to $\displaystyle 0$, but then cost and gain must be natural numbers.

Any advice?

$\endgroup$
3
3
$\begingroup$

I think there is an easy reduction from Knapsack.

Knapsack:

  • Input: a list of couples (value, weight) $\{(v_1, w_1), …, (v_n,w_n)\}$, a maximum weight $W$, a target value $V$
  • Question: is there a subset $S \subset [\![1, n]\!]$ such that $\sum\limits_{i\in S} v_i \geq V$ and $\sum\limits_{i\in S} w_i \leq W$

Now given an input of knapsack, let's construct an input of your problem: add a $n+1$-th element, and consider:

  • $\forall (i, j) \in [\![1, n]\!]$ with $i\neq j$, we set $c\{i, j\} = \infty$ and $c\{i, n+1\} = w_i$
  • $\forall (i, j) \in [\![1, n]\!]$ with $i\neq j$, we set $g\{i, j\} = 0$ and $g\{i, n+1\} = v_i$
  • set $b = W$ and $p = V$

Then this instance has a solution of your problem if and only if the input of knapsack has a solution. Since knapsack is $NP$-complete, this proves the $NP$-hardness of your problem.

$\endgroup$
3
  • $\begingroup$ Hi, we haven't studied Knapsack so I can't use it. But I have seen NP reductions from SSS or Partition to Knapsack. The problem is in this case I can't assign a cost of $0$ or infinity, since it should be a natural number. $\endgroup$ – Iam Spano Apr 26 at 12:15
  • $\begingroup$ You can just set $c\{i, j\} = W + 1$, since we only want to prevent selecting wrong pairs. As for $g\{i,j\}$ with $i,j\leq n$, their values don't matter since we won't be selecting these pairs (because of the cost). $\endgroup$ – Nathaniel Apr 26 at 12:34
  • $\begingroup$ Ah right, didn't think about that but true, thank you! $\endgroup$ – Iam Spano Apr 26 at 12:45

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.