7
$\begingroup$

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!

$\endgroup$
1
1
+50
$\begingroup$

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$.

$\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.