On the Parameterized Complexity of Clique Elimination Distance

DOI10.4230/LIPICS.IPEC.2020.1MaRDI QIDQ6068235zbMATH OpenOpenAlexFDO

Authors Akanksha Agrawal, M. S. Ramanujan

Publication date 13 November 2023

Full work available at URL https://doi.org/10.4230/LIPIcs.IPEC.2020.1

zbMATH Keywords

cluster graphselimination distancekernelization

Mathematics Subject Classification ID

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

Recommendations

• A fixed-parameter tractable algorithm for elimination distance to bounded degree graphs
• On the parameterized complexity of \(s\)-club cluster deletion problems
• Block elimination distance
• Cluster deletion revisited
• How to eliminate a graph

Cites work

• A faster parameterized algorithm for treedepth
• Algorithm Theory - SWAT 2004
• Approximation and kernelization for chordal vertex deletion
• Combining treewidth and backdoors for CSP
• Elimination Distance to Bounded Degree on Planar Graphs
• Elimination distances, blocking sets, and kernels for Vertex Cover
• Finding odd cycle transversals.
• Fixed-parameter tractable distances to sparse graph classes
• Graph isomorphism parameterized by elimination distance to bounded degree
• How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
• Improved bounds for the excluded-minor approximation of treedepth
• Kernelization using structural parameters on sparse graph classes
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Meta-kernelization using Well-structured Modulators
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Multiplying matrices faster than coppersmith-winograd
• On generating all maximal independent sets
• On tractable parameterizations of graph isomorphism
• Parameterized algorithms
• Parameterized and Exact Computation
• Solving d-SAT via Backdoors to Small Treewidth
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Treewidth. Computations and approximations

Cited in

(10)

• Distance from triviality 2.0: hybrid parameterizations
• FPT algorithms to compute the elimination distance to bipartite graphs and more
• scientific article; zbMATH DE number 7650068 (Why is no real title available?)
• Block elimination distance
• Block elimination distance
• Backdoor DNFs
• Elimination distance to bounded degree on planar graphs preprint
• Faster parameterized algorithms for modification problems to minor-closed classes
• Approximately interpolating between uniformly and non-uniformly polynomial kernels
• Elimination distance to dominated clusters

This page was built for publication: On the Parameterized Complexity of Clique Elimination Distance

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