Parameterized complexity of fair deletion problems

DOI10.1016/j.dam.2019.06.001zbMath1437.05227arXiv1605.07959OpenAlexW2405126695WikidataQ127672198 ScholiaQ127672198MaRDI QIDQ2174554

Tomáš Toufar, Tomáš Masařík

Publication date: 21 April 2020

Published in: Discrete Applied Mathematics, Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

vertex coverparameterized complexitytree-depthneighborhood diversitymetatheoremsfair problems

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

Parameterized Complexity of Fair Feedback Vertex Set Problem, Parameterized complexity of fair feedback vertex set problem, Parameterized complexity of fair deletion problems, An approval-based model for single-step liquid democracy, Integer programming in parameterized complexity: five miniatures, Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity, Extended MSO model checking via small vertex integrity, Computing \(L(p, 1)\)-labeling with combined parameters, Integer Programming in Parameterized Complexity: Three Miniatures., Unnamed Item, Local linear set on graphs with bounded twin cover number

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Sparsity. Graphs, structures, and algorithms
• On the complexity of some colorful problems parameterized by treewidth
• Monadic second-order evaluations on tree-decomposable graphs
• Elements of finite model theory.
• On the parameterized complexity of multiple-interval graph problems
• Which problems have strongly exponential complexity?
• Algorithmic meta-theorems for restrictions of treewidth
• On the NP-hardness of edge-deletion and -contraction problems
• Linear time solvable optimization problems on graphs of bounded clique-width
• Parameterized complexity of fair deletion problems
• Nonserial dynamic programming
• On the Complexity of Some Colorful Problems Parameterized by Treewidth
• What Makes Equitable Connected Partition Easy
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Node-Deletion NP-Complete Problems
• Edge-Deletion Problems
• Fair edge deletion problems
• Node-and edge-deletion NP-complete problems
• Model Checking Lower Bounds for Simple Graphs