# Fixed Parameter Tractable for Special Vertex Cover using ILP

The problem I'm trying to solve reads as follows:

Given a graph $$G=(V,E)$$ ,a parameter $$k$$ and two values $$U^\star, P^\star \in \mathbb N$$, where every vertex $$v\in V$$ has a utility and a pollution $$u_v,p_v \in \mathbb N$$, we define $$U(v)=\sum_{w\in N(v)} u_w$$ and $$P(v)=\sum_{w\in N(v)} p_w$$. The goal is to find a vertex cover $$X$$ of $$G$$ of size at most $$k$$ such that $$U(X)=\sum_{v\in X} \geq U^\star$$ and similarly for $$P(X)=\sum_{v\in X} \leq P^\star$$.

I’m trying to obtain a FPT for this problem(i.e. an algorithm with running time bounded by $$f(k)*n^{O(1)}$$ for some function $$f$$) , and my idea was to use Integer Linear programming, and a $$O^\star(p^{O(p)})$$ time algorithm for ILP where $$p$$ is the number of variables. So what I want to do is to define an ILP for this problem with a number of variables bounded by a function of the parameter $$k$$. In order to to do that I thought of the following idea:

Find any vertex cover, $$S$$ , of $$G$$, and then notice that the $$U,P$$ values of a given vertex are determined solely by its neighborhood, and since every vertex has all its neighbors in a vertex cover we could come up with $$2^{|S|}$$ possible values for $$U(v),P(v)$$ for all $$v\in V$$(the number of subsets of $$S$$, $$U(v), P(v)$$ being $$\sum_{w\in N(v)} u_w,\sum_{w\in N(v)} p_w$$ respectively).

However, while all that said is true, it is true for every vertex cover, and that would mean I would have to compute every possible vertex cover of $$G$$ which is not efficient, and even if it was at that point I could've just gone ahead and check for each cover if it satisfies the constraints on $$U^\star,V^\star$$ which makes the entire idea probably wrong.

So I think I'm stuck here, any ideas on how to go on from this point would be appreciated.

• What's the context where you encountered this task? We require you to credit the original source of all copied material: cs.stackexchange.com/help/referencing
– D.W.
Commented Jul 6, 2021 at 8:44