# Reduction to a parameterized problem

I'm trying the following question from my homework:

We're given a graph $$G$$ and parameters $$k,\hat{P}, \hat{W}\in \mathbb{N}$$. Additionally, each $$v \in V(G)$$ has a profit and weight: $$p_v, w_v\in \mathbb{N}$$.

Suppose you're given an $$f(k) \cdot n^{O(1)}$$-time algorithm $$\mathcal{A}$$ which finds whether there is a vertex cover $$X\subseteq V$$ with: $$|X| \leq k,\quad \sum_{v\in X} P(v)\geq \hat{P},\quad \sum_{v\in X} W(v)\leq \hat{W}$$ where $$P(v) = \sum_{s\in \{v\}\cup N(v)} p_s$$ $$W(v) = \sum_{s\in \{v\}\cup N(v)} w_s$$

The task is to find a polynomial-time algorithm that solves Knapsack (the decision version) using $$\mathcal{A}$$.

My attempts - given n items with profits and weights, $$p_i, w_i$$:

1. Define a graph $$G$$ with 0 edges, where each vertex corresponds to an item. Now run $$\mathcal{A}$$ on $$G$$ with $$k=n$$. Clearly, the problem here is that the running time would be $$f(n) \cdot n^{O(1)}$$ - depends of $$f$$ whether the time is polynomial.
2. In this attempt we'll try to run $$\mathcal{A}$$ multiple times. Define a graph $$G$$, where each vertex corresponds to an item. Now we'll consider every possible option for edges between $$v_1$$ to the other vertices and for each option we run $$\mathcal{A}$$ with these graphs and $$k=1$$. Now do the same for all possible edges between $$v_2$$ and all other vertices, and so on. This will take $$n\cdot 2^{n-1}\cdot f(1)\cdot n^{O(1)} = 2^{n-1}\cdot f(1)\cdot n^{O(1)}$$ - again, not polynomial.

Is it even possible to come up with a polynomial-time algorithm using $$\mathcal{A}$$?

Any idea (even if not an exact solution) would be very appreciated!

• – D.W.
Jul 12 at 20:39

Showing such an algorithm exists would prove $$P = NP$$.

We show that an algorithm $$\mathcal{A}$$ does indeed exist. An algorithm to decide vertex cover in $$O(2^kkn)$$ is known. We can modify it for the extended vertex cover from the question:

Ext-Vertex-Cover(G, k) {
S = new k-sized stack
return Ext-Vertex-Cover-Rec(G, k, S)
}

Ext-Vertex-Cover-Rec(G, k, S) {
if (G contains no edges) return (check if S fulfills sum constraints)
if (G contains ≥ kn edges) return false

let (u, v) be any edge of G
push u onto S
a = Ext-Vertex-Cover-Rec(G - {u}, k-1, S)
pop S
push v onto S
b = Ext-Vertex-Cover-Rec(G - {v}, k-1, S)
pop S
return a or b
}


Push and pop is $$O(1)$$. Checking the sum constraints takes additional $$O(kn)$$ per invocation, keeping overall run-time at $$O(2^kkn)$$. Thus, for $$f(k) = 2^kk$$ this is a suitable algorithm $$\mathcal{A}$$.

Then, since knapsack is NP-complete, finding a polynomial-time algorithm for knapsack using $$\mathcal{A}$$ would imply $$P = NP$$.