#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!!!

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