Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems

DOI10.1137/1.9781611974331.ch79zbMath1410.68281arXiv1508.05282OpenAlexW2228247117WikidataQ130971035 ScholiaQ130971035MaRDI QIDQ4575659

Paweł Komosa, Lukáš Mach, Michał Pilipczuk, Marek Cygan, Ivan A. Bliznets

Publication date: 16 July 2018

Published in: ACM Transactions on Algorithms, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1508.05282

zbMATH Keywords

graph-completion problems

Mathematics Subject Classification ID

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) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (7)

Completion to chordal distance-hereditary graphs: a quartic vertex-kernel ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Algorithms for automatic ranking of participants and tasks in an anonymized contest ⋮ Rank reduction of oriented graphs by vertex and edge deletions ⋮ Minimum fill-in: inapproximability and almost tight lower bounds ⋮ Unnamed Item ⋮ (Sub)linear kernels for edge modification problems toward structured graph classes

This page was built for publication: Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems