On the parameterized complexity of vertex cover and edge cover with connectivity constraints

摘要

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) for a fixed positive integer t, and call the problem t-TOTAL VERTEX COVER (resp. t-TOTAL EDGE COVER). In both cases the parameter k is the size of the solution. We show that