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.

  • $\begingroup$ 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 $\endgroup$
    – D.W.
    Commented Jul 6, 2021 at 8:44


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.