Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover

Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review

Abstract

Our goal in this paper is the development of fast algorithms for recognizing general classes of graphs. We seek algorithms whose complexity can be expressed as a linear function of the graph size plus an exponential function of k, a natural parameter describing the class. In particular, we consider the class Wk(G), where for each graph G in Wk(G), the removal of a set of at most k vertices from G results in a graph in the base graph class G. (If G is the class of edgeless graphs, Wk(G) is the class of graphs with bounded vertex cover.) When G is a minor-closed class such that each graph in G has bounded maximum degree, and all obstructions of G (minor-minimal graphs outside G) are connected, we obtain an O((g+k)|V(G)|+(fk)k) recognition algorithm for Wk(G), where g and f are constants (modest and quantified) depending on the class G. If G is the class of graphs with maximum degree bounded by D (not closed under minors), we can still obtain a running time of O(|V(G)|(D+k)+k(D+k)k+3) for recognition of graphs in Wk(G). Our results are obtained by considering bounded-degree minor-closed classes for which all obstructions are connected graphs, and showing that the size of any obstruction for Wk(G) is O(tk7+t7k2), where t is a bound on the size of obstructions for G. A trivial corollary of this result is an upper bound of (k+1)(k+2) on the number of vertices in any obstruction of the class of graphs with vertex cover of size at most k. These results are of independent graph-theoretic interest.

Original languageEnglish (US)
Pages (from-to)229-245
Number of pages17
JournalDiscrete Applied Mathematics
Volume152
Issue number1-3
DOIs
StatePublished - Nov 1 2005

Keywords

  • FPT algorithms
  • Graph minors
  • Parameterized complexity

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover'. Together they form a unique fingerprint.

Cite this