On the threshold of intractability

DOI10.1016/j.jcss.2021.09.003zbMath1478.68104arXiv1505.00612OpenAlexW4206458185WikidataQ57439271 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 complexitythreshold graphsedge editing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (16)

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

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

This page was built for publication: On the threshold of intractability