skip to main content

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

Fernau, Henning ; Fomin, Fedor V ; Philip, Geevarghese ; Saurabh, Saket

Theoretical Computer Science, 02 February 2015, Vol.565, pp.1-15 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por
  • Título:
    On the parameterized complexity of vertex cover and edge cover with connectivity constraints
  • Autor: Fernau, Henning ; Fomin, Fedor V ; Philip, Geevarghese ; Saurabh, Saket
  • Assuntos: Parameterized Complexity ; Connectivity Problems ; Kernel Lower Bounds ; Vertex Cover ; Edge Cover ; Computer Science ; Mathematics
  • É parte de: Theoretical Computer Science, 02 February 2015, Vol.565, pp.1-15
  • Descrição: To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.tcs.2014.10.035 Byline: Henning Fernau, Fedor V. Fomin, Geevarghese Philip, Saket Saurabh 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) 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 * both problems remain fixed-parameter tractable with these restrictions, with running times of the form O.sup.a(c.sup.k) for some constant c0 in each case, where the O.sup.a notation hides polynomial factors; * for each fixed t[greater than or equal to]2, t-Total Vertex Cover has no polynomial kernel unless CoNP[subset]NP/poly; * for each fixed t[greater than or equal to]2, t-Total Edge Cover has a linear vertex kernel of size t+1/tk. These results significantly improve earlier work on these problems. We illustrate the utility of the technique used to solve t-Total Vertex Cover, by applying it to derive an O.sup.a(c.sup.k)-time FPT algorithm for the t-Total Edge Dominating Set problem. Our no-poly-kernel result for t-Total Vertex Cover, and the known NP-hardness result for t-Total Edge Cover, are in stark contrast to the fact that Vertex Cover has a 2k vertex kernel, and that Edge Cover is solvable in polynomial time. This illustrates how even the slightest connectivity requirement results in a drastic change in the tractability of problems -- the curse of connectivity! Author Affiliation: (a) Universitat Trier FB 4, Abteilung Informatik, 54286 Trier, Germany (b) Department of Informatics, University of Bergen, 5020 Bergen, Norway (c) The Institute of Mathematical Sciences, Chennai 600 113, India (d) Max-Planck-Institut fur Informatik, 66123 Saarbrucken, Germany Article History: Received 21 October 2013; Revised 30 September 2014; Accepted 21 October 2014 Article Note: (footnote) [star] A preliminary version of this paper appeared in the proceedings of COCOON 2010 [1]. In addition to the detailed proofs which were omitted in that version, the current article also includes an FPT algorithm for the t-Total Edge Dominating Set problem which was not discussed in the shorter version.
  • Idioma: Inglês

Buscando em bases de dados remotas. Favor aguardar.