Exploring the subexponential complexity of completion problems
DOI10.1145/2799640zbMATH Open1347.68180OpenAlexW2243582562WikidataQ60488388 ScholiaQ60488388MaRDI QIDQ2828210FDOQ2828210
Authors: Pål Grønås Drange, Fedor V. Fomin, Michał Pilipczuk, Yngve Villanger 
Publication date: 24 October 2016
Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2799640
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Tight bounds for parameterized complexity of cluster editing with a small number of clusters
- Title not available (Why is that?)
- Graph Classes: A Survey
- Cluster editing with locally bounded modifications
- A partial k-arboretum of graphs with bounded treewidth
- Which problems have strongly exponential complexity?
- Threshold graphs and related topics
- Linear recognition of pseudo-split graphs
- Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
- Quasi-threshold graphs
- Computing the Minimum Fill-In is NP-Complete
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
- Fast FAST
- NP-completeness results for edge modification problems
- Subexponential parameterized algorithm for minimum fill-in
- Interval Completion Is Fixed Parameter Tractable
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
- Edge-Deletion Problems
- A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
- Faster parameterized algorithms for deletion to split graphs
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- Incompressibility of \(H\)-free edge modification problems
- Two edge modification problems without polynomial kernels
- A subexponential parameterized algorithm for proper interval completion
Cited In (11)
- On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
- Approximation and kernelization for chordal vertex deletion
- Rank reduction of oriented graphs by vertex and edge deletions
- A survey of parameterized algorithms and the complexity of edge modification
- Exploring subexponential parameterized complexity of completion problems
- Dichotomy results on the hardness of \(H\)-free edge modification problems
- Polynomial kernelization for removing induced claws and diamonds
- A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
- Title not available (Why is that?)
- Diameter estimates for graph associahedra
- (Sub)linear kernels for edge modification problems toward structured graph classes
This page was built for publication: Exploring the subexponential complexity of completion problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2828210)
