#StackBounty: #complexity-theory #np-complete #reductions #np-hard #polynomial-time-reductions Reduction to a parameterized problem

Bounty: 50

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_vin 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 $Xsubseteq V$ with: $$|X| leq k,quad sum_{vin X} P(v)geq hat{P},quad sum_{vin X} W(v)leq hat{W}$$ where
$$P(v) = sum_{sin {v}cup N(v)} p_s $$
$$W(v) = sum_{sin {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 $ncdot 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 reduction?

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


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.