A novel branching strategy for parameterized graph modification problems

DOI10.1007/978-3-642-17461-2_27zbMATH Open1310.68191DBLPconf/cocoa/NastosG10arXiv1006.3020OpenAlexW2762561540WikidataQ56475006 ScholiaQ56475006MaRDI QIDQ3066469FDOQ3066469

Authors: James Nastos, Yong Gao 

Publication date: 10 January 2011

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

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].

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

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

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)

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
• Title not available (Why is that?)

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)