A novel branching strategy for parameterized graph modification problems

DOI10.1007/978-3-642-17461-2_27MaRDI QIDQ3066469zbMATH OpenOpenAlexDBLPWikidataFDO

Authors James Nastos, Yong Gao

Publication date 10 January 2011

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1006.3020

zbMATH Keywords

fixed-parameter tractabilitycographsgraph modificationedge-deletionquasi-threshold graphsbounded search treetrivially perfect graphs

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: Many fixed-parameter tractable algorithms using a bounded search tree have been repeatedly improved, often by describing a larger number of branching rules involving an increasingly complex case analysis. We introduce a novel and general search strategy that branches on the forbidden subgraphs of a graph class relaxation. By using the class of $P_4$-sparse graphs as the relaxed graph class, we obtain efficient bounded search tree algorithms for several parameterized deletion problems. We give the first non-trivial bounded search tree algorithms for the cograph edge-deletion problem and the trivially perfect edge-deletion problems. For the cograph vertex deletion problem, a refined analysis of the runtime of our simple bounded search algorithm gives a faster exponential factor than those algorithms designed with the help of complicated case distinctions and non-trivial running time analysis [21] and computer-aided branching rules [11].

Recommendations

• Bounded search tree algorithms for parametrized cograph deletion: efficient branching rules by exploiting structures of special graph classes
• An effective branching strategy for some parameterized edge modification problems with multiple forbidden induced subgraphs
• An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs
• Edge deletion problems: branching facilitated by modular decomposition
• Bounded-degree techniques accelerate some parameterized graph algorithms

Cited in

(9)

• The cluster deletion problem for cographs
• Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics
• Bounded search tree algorithms for parametrized cograph deletion: efficient branching rules by exploiting structures of special graph classes
• Edge deletion problems: branching facilitated by modular decomposition
• An effective branching strategy for some parameterized edge modification problems with multiple forbidden induced subgraphs
• An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs
• Automated generation of search tree algorithms for graph modification problems
• Complexity and parameterized algorithms for cograph editing
• scientific article; zbMATH DE number 1054664 (Why is no real title available?)

This page was built for publication: A novel branching strategy for parameterized graph modification problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3066469)