Paper Info
Title
Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms
Abstract
Many algorithms for FPT graph problems are search tree algorithms with sophisticated local branching rules. But it has also been noticed that using the global structure of input graphs complements the the search tree paradigm. Here we prove some new results based on the global structure of bounded-degree graphs after branching away the high-degree vertices. Some techniques and structural results are generic and should find more applications. First, we decompose a graph by "separating" branchings into cheaper or smaller components wich are then processed separately. Using this idea we accelerate the O *(1.3803 k ) time algorithm for counting the vertex covers of size k (Mölle, Richter, and Rossmanith, 2006) to O *(1.3740 k ). Next we characterize the graphs where no edge is in three conflict triples, i.e., triples of vertices with exactly two edges. This theorem may find interest in graph theory, and it yields an O *(1.47 k ) time algorithm for Cluster Deletion, improving upon the previous O *(1.53 k ) (Gramm, Guo, Hüffner, Niedermeier, 2004). Cluster Deletion is the problem of deleting k edges to destroy all conflict triples and get a disjoint union of cliques. For graphs where every edge is in O(1) conflict triples we show a nice dichotomy: The graph or its complement has degree O(1). This opens the possibility for future improvements via the above decomposition technique.
Year
DOI
Venue
2009
10.1007/978-3-642-11269-0_8
IWPEC
Keywords
Field
DocType
bounded-degree techniques accelerate,deleting k edge,previous o,global structure,size k,bounded-degree graph,degree o,time algorithm,parameterized graph algorithms,conflict triple,fpt graph problem,cluster deletion,vertex cover,vertex degree,clustering
Discrete mathematics,Combinatorics,Line graph,Interval graph,Cycle graph,Independent set,Cograph,Pathwidth,Mathematics,Complement graph,Graph coloring
Conference
Volume
ISSN
Citations 
5917
0302-9743
8
PageRank 
References 
Authors
0.56
15
1
Name
Order
Citations
PageRank
Peter Damaschke147156.99