0
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Highheath
    Jul 19 at 9:33
  • $\begingroup$ 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. $\endgroup$
    – Highheath
    Jul 19 at 9:38
  • $\begingroup$ 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$. $\endgroup$
    – Itamargo
    Jul 19 at 13:35
  • $\begingroup$ 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. $\endgroup$
    – Highheath
    Jul 19 at 13:58
  • $\begingroup$ Thank you, maybe there is a way to show that the problem can't have a kernelization algorithm? $\endgroup$
    – Itamargo
    Jul 19 at 14:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.