TY - GEN

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

AU - Nishimura, Naomi

AU - Ragde, Prabhakar

AU - Thilikos, Dimitrios M.

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2001.

PY - 2001

Y1 - 2001

N2 - 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. Our classes are of the form Wk(G), graphs that can be formed by augmenting graphs in G by adding at most k vertices (and incident edges). If G is the class of edgeless graphs, Wk(G) is the class of graphs with a vertex cover of size at most k. We describe a recognition algorithm for Wk(G) running in time O((g + k)|V (G)| + (fk)k), where g and f are modest constants depending on the class G, 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. If G is the class of graphs with maximum degree bounded by D (not closed under minors), we can still recognize graphs in Wk(G) in time O(|V (G)|(D + k) + k(D + k)k+3). Our results are obtained by considering minor-closed classes G 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.

AB - 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. Our classes are of the form Wk(G), graphs that can be formed by augmenting graphs in G by adding at most k vertices (and incident edges). If G is the class of edgeless graphs, Wk(G) is the class of graphs with a vertex cover of size at most k. We describe a recognition algorithm for Wk(G) running in time O((g + k)|V (G)| + (fk)k), where g and f are modest constants depending on the class G, 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. If G is the class of graphs with maximum degree bounded by D (not closed under minors), we can still recognize graphs in Wk(G) in time O(|V (G)|(D + k) + k(D + k)k+3). Our results are obtained by considering minor-closed classes G 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.

UR - http://www.scopus.com/inward/record.url?scp=84958050629&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958050629&partnerID=8YFLogxK

U2 - 10.1007/3-540-44634-6_8

DO - 10.1007/3-540-44634-6_8

M3 - Conference contribution

AN - SCOPUS:84958050629

SN - 3540424237

SN - 9783540424239

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 75

EP - 86

BT - Algorithms and Data Structures - 7th International Workshop, WADS 2001, Proceedings

A2 - Dehne, Frank

A2 - Sack, Jorg-Rudiger

A2 - Tamassia, Roberto

PB - Springer Verlag

T2 - 7th International Workshop on Algorithms and Data Structures, WADS 2001

Y2 - 8 August 2001 through 10 August 2001

ER -