How can I prove the following problem is NP complete?

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.

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.

• 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. – Iam Spano Apr 26 at 12:15
• 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). – Nathaniel Apr 26 at 12:34
• Ah right, didn't think about that but true, thank you! – Iam Spano Apr 26 at 12:45