Structural parameterizations with modulator oblivion

DOI10.4230/LIPICS.IPEC.2020.19MaRDI QIDQ6089666zbMATH OpenFDO

Authors Ashwin Jacob, Fahad Panolan, Venkatesh Raman, Vibha Sahlot

Publication date 13 November 2023

zbMATH Keywords

parameterized complexitytree decompositionchordal graphstrong exponential time hypothesis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Structural parameterizations with modulator oblivion
• Chordal deletion is fixed-parameter tractable
• Chordal Deletion Is Fixed-Parameter Tractable
• Approximation and kernelization for chordal vertex deletion

Cites work

• scientific article; zbMATH DE number 1839471 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A \(c^k n\) 5-approximation algorithm for treewidth
• A simple linear time algorithm for cograph recognition
• Algorithm Theory - SWAT 2004
• Algorithmic graph theory and perfect graphs
• Approximation and kernelization for chordal vertex deletion
• Backdoors to satisfaction
• Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques
• Chordal editing is fixed-parameter tractable
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Dominating Sets in Chordal Graphs
• Efficient graph representations
• Erdős-Pósa property of chordless cycles and its applications
• Faster parameterized algorithms using linear programming
• Functional analysis
• Fundamentals of parameterized complexity
• Graph minors. XIII: The disjoint paths problem
• Graph theory
• Large Induced Subgraphs via Triangulations and CMSO
• On problems as hard as CNF-SAT
• Parameterized algorithms
• Parameterized complexity of vertex deletion into perfect graph classes
• Parameterized single-exponential time polynomial space algorithm for Steiner tree
• Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
• Polynomial kernels for vertex cover parameterized by small degree modulators
• Robust algorithms for restricted domains
• Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
• The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number
• The complexity of generalized clique covering
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Unit disk graph recognition is NP-hard
• Unit disk graphs
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter

Cited in

(3)

• Kernelization for feedback vertex set via elimination distance to a forest
• Structural parameterizations with modulator oblivion
• ArbiLoMod, a Simulation Technique Designed for Arbitrary Local Modifications

This page was built for publication: Structural parameterizations with modulator oblivion

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