The Curse of Connectivity: t-Total Vertex (Edge) Cover.

We investigate the effect of certain natural connectivity constraints on the parameterized complexity of two fundamental graph covering problems, namely k-Vertex Cover and k-Edge Cover. Specifically, we impose the additional requirement that each connected component of a solution have at least t vertices (resp. edges from the solution), and call the problem t-total vertex cover (resp. t-total edge cover). We show that both problems remain fixed-parameter tractable with these restrictions, with running times of the form ]> for some constant c > 0 in each case; for every t ≥ 2, t-total vertex cover has no polynomial kernel unless the Polynomial Hierarchy collapses to the third level; for every t ≥ 2, t-total edge cover has a linear vertex kernel of size ]> . [ABSTRACT FROM AUTHOR]