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

zbMATH Keywords

parameterized complexity; threshold graphs; edge editing

Mathematics Subject Classification ID

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

Unnamed Item, Central Positions in Social Networks, Paths to Trees and Cacti, Faster and enhanced inclusion-minimal cograph completion, Vertex deletion on split graphs: beyond 4-hitting set, On the Parameterized Approximability of Contraction to Classes of Chordal Graphs, A survey of parameterized algorithms and the complexity of edge modification, Rank reduction of oriented graphs by vertex and edge deletions, On the effectiveness of the incremental approach to minimal chordal edge modification, A polynomial kernel for trivially perfect editing, Paths to trees and cacti, On the threshold of intractability, Algorithms for automatic ranking of participants and tasks in an anonymized contest, Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results, Completion to chordal distance-hereditary graphs: a quartic vertex-kernel, Fast Quasi-Threshold Editing

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