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

DOI10.1137/1.9781611974331.ch79zbMath1410.68281arXiv1508.05282MaRDI QIDQ4575659

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

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

68Q25: Analysis of algorithms and problem complexity

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