Structural parameterizations with modulator oblivion

DOI10.4230/LIPICS.IPEC.2020.19MaRDI QIDQ6089666FDOQ6089666

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

Publication date: 13 November 2023

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

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)

Cites Work

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

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)