Parameterized complexity of dominating set variants in almost cluster and split graphs

DOI10.1016/J.JCSS.2025.103631MaRDI QIDQ7007129zbMATH OpenFDO

Authors Dishant Goyal, Ashwin Jacob, Kaushtubh Kumar, Diptapriyo Majumdar, Venkatesh Raman

Publication date 26 March 2025

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCSS.2025.103631

zbMATH Keywords

domination problemsdynamic programmingparameterized complexityset cover with partitionstructural parameterization

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• \textsc{Split Vertex Deletion} meets \textsc{Vertex Cover}: new fixed-parameter and exact exponential-time algorithms
• A fast branching algorithm for cluster vertex deletion
• Approximation hardness of dominating set problems in bounded degree graphs
• Approximation hardness of edge dominating set problems
• Exact algorithms for dominating set
• Exact exponential algorithms.
• Faster algorithms on branch and clique decompositions
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Grouped domination parameterized by vertex cover, twin cover, and beyond
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 5032352 (Why is no real title available?)
• Infeasibility of instance compression and succinct PCPs for NP
• Kernel bounds for disjoint cycles and disjoint paths
• Kernelization lower bounds through colors and IDs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Maximum minimal vertex cover parameterized by vertex cover
• On problems as hard as CNF-SAT
• On the complexity of k-SAT
• On the max min vertex cover problem
• Parameterized algorithms
• Parameterized algorithms for locating-dominating sets
• Parameterized and Exact Computation
• Parameterized approximation of dominating set problems
• Parameterized complexity of vertex colouring
• Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
• Polynomial-time data reduction for dominating set
• Reflections on multivariate algorithmics and problem parameterization
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• Structural parameterizations of dominating set variants
• The parameterized complexity of dominating set and friends revisited for structured graphs
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Upper bounds to the clique width of graphs
• Which problems have strongly exponential complexity?

Cited in

(1)

• On the parameterized complexity of cosecure domination

This page was built for publication: Parameterized complexity of dominating set variants in almost cluster and split graphs

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