5
$\begingroup$

I would like to know more about the W[t]-containment of partial covering problems. Especially, I am interested in the question whether Partial Set Cover (Problem Definition at the end of the question) with respect to the size of a solution $k$ is in W[2].

Because Set Cover is the special case of Partial Set Cover with $p=|\mathcal U|$, we conclude that Partial Set Cover wrt $k$ is W[2]-hard. It remains open whether Partial Set Cover is also contained in W[2]. A natural way to prove this would be to reduce from Partial Vertex Cover to Weighted Circuit Satisfiability. But in my reduction, I struggle in how to "count" the number of covered items.

For Partial Vertex Cover a surprising thing happens. While Vertex cover is FPT wrt $k$, Partial Vertex Cover is W[1]-complete wrt $k$. Guo, Niedermaier and Wernicke: Parameterized complexity of vertex cover variants https://link.springer.com/content/pdf/10.1007/s00224-007-1309-3.pdf

Guo, Niedermaier and Wernicke did not reduce to Weighted Circuit Satisfiability in order to show W[1]-containment. However, I would still like how such a reduction could look like because also here we need to "count" the number of covered edges.

Thanks for your attention.

Problem Definitions

Partial Set Cover is defined as follows. Given a universe $\mathcal U$, a family of sets $\mathcal F$ over $\mathcal U$ and two integers $k$ and $p$. It is asked whether there are sets $F_1,\dots,F_k\in\mathcal F$ such that the union $\bigcup_{i=1}^k F_i \subseteq \mathcal U$ contains at least $p$ items.

Partial Vertex Cover is defined as follows. Given an undirected graph $G=(V,E)$ and two integers $k$ and $p$. It is asked whether there is a set of vertices $X$ such that at least $p$ edges are incident with at least one vertex of $X$.

$\endgroup$

0

Your Answer

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