# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

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

##### MPS-Authors

There are no MPG-Authors available

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Fernau, H., Fomin, F. V., Philip, G., & Saurabh, S. (2010). The Curse of Connectivity:
t-Total Vertex (Edge) Cover. In M. T. Thai, & S. Sahni (*Computing
and Combinatorics* (pp. 34-43). Berlin: Springer. doi:10.1007/978-3-642-14031-0.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0019-DC0B-B

##### Abstract

We investigate the effect of certain natural connectivity constraints
on the parameterized complexity of two fundamental graph covering
problems, namely Vertex Cover and 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
\beginitemize}
\item both problems remain fixed-parameter tractable with these restrictions,
with running times of the form \Oh^{*}≤ft(c^{k}\right) for some
constant c>0 in each case;
\item for every t≥2,t-Total Vertex Cover has no polynomial kernel unless
the
Polynomial Hierarchy collapses to the third level;
\item for every t≥2, t-Total Edge Cover has a linear vertex kernel of
size \frac{t+1}{t}k.
\end{itemize