# Proving that a problem is not FPT using reduction

In the Inclusive Vertex Cover problem, For a given graph $$G=(V,E)$$, each vertex $$u\in V(G)$$ has weight $$u_{w} \in \mathbb{N}$$ and value $$u_{v}\in \mathbb{N}$$. The value and weight of a set cover $$S$$ are defined as the sum of weight, value of the vertex in the cover, and its neighbors. Note that a vertex might be counted more than once if it has two neighbors in the cover.

More precisely:

$$W = \sum_{v\in V(G)}(\sum_{x \in N[v]}x_{w})$$

$$V = \sum_{v\in V(G)}(\sum_{x \in N[v]}x_{v})$$

The problem is: Given an instance $$(G,k,W^{*},V^{*})$$ is there a vertex cover $$S$$ with size of at most $$k$$ s.t $$W \le W^{*}$$ and $$V \ge V^{*}$$.

I need to prove that this specific problem can't have an FPT algorithm with a run time complexity of $$f(k)n^{O(1)}$$.

The way of doing that is by showing that for a fixed $$k$$, we can solve some NP-hard problems.

The problem definition is almost identical to the knapsack problem.

I am looking for a reduction from an NP problem to the Inclusive Vertex Cover for a fixed $$k$$.

I tried taking an instance for the knapsack problem and:

• Defining different stars for every possible group, but the number of groups is exponential
• Isolated vertices can't work since we don't know the number of vertices on the cover
• Use more complicated graphs with a predetermined number of items, but it always leads to an exponential number of vertices in the graph

There is a connection to this question and some other questions that were posted on this subject, but I followed this guide that was recommended on how to ask a good homework question. However, I altered the question a bit since it's much easier to look at the similarity of the IVC problem to the knapsack for me.

Any suggestions? Hints? Ideas?

Edit:

A polynomial reduction from knapsack to the IVC problem with fixed $$k$$ is not possible since the polynomial algorithm the solves IVC for fixed $$k$$ is known and polynomial (trivially $$O(n^{c})$$. Is there another way to show that a problem is not an FPT? Is there a way to show that a kernel cannot exist since any kernelization algorithm can't reduce the input size of the problem? Any suggestion?

• It seems pretty clear to me that this IVC problem is not NP-hard for fixed $k$. This is because there is a simple algorithm that runs in time $n^{O(k)}$. Note that this is not FPT time, but still polynomial when $k$ is fixed. Therefore it seems like a fruitless task to try and prove a reduction from an NP-hard problem to this one with $k$ fixed. Jul 19 at 9:33
• Have you looked into W-hard problems? Dominating Set looks like a very similar problem to this one, and it is known to be $W[2]$-hard, which makes people think it does not have an FPT-time algorithm. Jul 19 at 9:38
• Yes, I am familiar with W-hard problems. But I don't think that this strategy will work here. I am looking for a reduction from an NP-hard problem to IVC problem with fixed $k$. Jul 19 at 13:35
• As I said, there exists a simple algorithm that runs in polynomial time for every fixed $k$. I am therefore absolutely certain that you won't find such a reduction, as it would imply P=NP. Jul 19 at 13:58
• Thank you, maybe there is a way to show that the problem can't have a kernelization algorithm? Jul 19 at 14:55