Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion}
DOI10.1007/s00224-016-9716-yzbMath1378.68057arXiv1504.05515OpenAlexW2964188443MaRDI QIDQ2408559
Julien Baste, Ignasi Sau, Sulamita Klein, Luérbio Faria
Publication date: 12 October 2017
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1504.05515
parameterized complexitygraph modification problemFPT-algorithmiterative compressionsingle-exponential algorithm
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Finding odd cycle transversals.
- Improved upper bounds for vertex cover
- The node-deletion problem for hereditary properties is NP-complete
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Which problems have strongly exponential complexity?
- Algorithmic graph theory and perfect graphs
- Partitions of graphs into one or two independent sets and cliques
- \textsc{Split Vertex Deletion} meets \textsc{Vertex Cover}: new fixed-parameter and exact exponential-time algorithms
- Faster parameterized algorithms for deletion to split graphs
- Parametrized complexity theory.
- Finding small separators in linear time via treewidth reduction
- Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
- List Partitions
- Parameterized Algorithms for (r,l)-Partization
- Compression via Matroids
- Faster Parameterized Algorithms Using Linear Programming
- Parameterized Algorithms
This page was built for publication: Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion}
