2009 | OriginalPaper | Buchkapitel
Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms
verfasst von : Peter Damaschke
Erschienen in: Parameterized and Exact Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.