On the threshold of intractability
DOI10.1016/j.jcss.2021.09.003zbMath1478.68104arXiv1505.00612WikidataQ57439271 ScholiaQ57439271MaRDI QIDQ2051847
Daniel Lokshtanov, Blair D. Sullivan, Pål Grønås Drange, Markus Fanebust Dregi, Markus Sortland Dregi
Publication date: 25 November 2021
Published in: Journal of Computer and System Sciences, Algorithms - ESA 2015 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1505.00612
68Q25: Analysis of algorithms and problem complexity
68W40: Analysis of algorithms
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q27: Parameterized complexity, tractability and kernelization
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Complexity and parameterized algorithms for cograph editing
- Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
- Approximating the Minimum Chain Completion problem
- The splittance of a graph
- Fixed-parameter tractability of graph modification problems for hereditary properties
- A polynomial kernel for trivially perfect editing
- Cluster graph modification problems
- Algorithmic graph theory and perfect graphs
- Threshold graphs and related topics
- On the threshold of intractability
- Edge deletion problems: branching facilitated by modular decomposition
- Faster parameterized algorithms for deletion to split graphs
- Parametrized complexity theory.
- NP-completeness results for edge modification problems
- Exploring the Subexponential Complexity of Completion Problems
- Chordal Editing is Fixed-Parameter Tractable
- Untangling the Hairballs of Multi-Centered, Small-World Online Social Media Networks
- The Cluster Editing Problem: Implementations and Experiments
- Fast FAST
- Computing the Minimum Fill-In is NP-Complete
- Graph Classes: A Survey
- Computing Phylogenetic Roots with Bounded Degrees and Errors
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
- Subexponential Parameterized Algorithm for Minimum Fill-In
- Complexity classification of some edge modification problems