Document Open Access Logo

Hardness of Approximation for H-Free Edge Modification Problems: Towards a Dichotomy

Authors Tatiana Belova, Ivan Bliznets

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.24.pdf
  • Filesize: 0.71 MB
  • 15 pages

Document Identifiers

Author Details

Tatiana Belova
  • St. Petersburg Department of Steklov Mathematical Institute of the RAS, Russia
Ivan Bliznets
  • St. Petersburg Department of Steklov Mathematical Institute of the RAS, Russia

Funding

The research is supported by Russian Science Foundation (project 18-71-10042).

Cite AsGet BibTex

Tatiana Belova and Ivan Bliznets. Hardness of Approximation for H-Free Edge Modification Problems: Towards a Dichotomy. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ISAAC.2022.24

Abstract

For a fixed graph H, the H-free Edge Deletion/Completion/Editing problem asks to delete/add/edit the minimum possible number of edges in G to get a graph that does not contain an induced subgraph isomorphic to the graph H. In this work, we investigate H-free Edge Deletion/Completion/Editing problems in terms of the hardness of their approximation. We formulate a conjecture according to which all the graphs with at least five vertices can be classified into several groups of graphs with specific structural properties depending on the hardness of approximation for the corresponding H-free Edge Deletion/Completion/Editing problems. Also, we make significant progress in proving that conjecture by showing that it is sufficient to resolve it only for a finite set of graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • Parameterized complexity
  • Hardness of approximation
  • Edge modification problems

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. NR Aravind, RB Sandeep, and Naveen Sivadasan. Dichotomy results on the hardness of h-free edge modification problems. SIAM Journal on Discrete Mathematics, 31(1):542-561, 2017. Google Scholar
  2. Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukáš Mach, and Michał Pilipczuk. Lower bounds for the parameterized complexity of minimum fill-in and other completion problems. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1132-1151. SIAM, 2016. Google Scholar
  3. Ivan Bliznets, Marek Cygan, Paweł Komosa, and Michał Pilipczuk. Hardness of approximation for h-free edge modification problems. ACM Transactions on Computation Theory (TOCT), 10(2):1-32, 2018. Google Scholar
  4. Ivan Bliznets, Marek Cygan, Paweł Komosa, Michał Pilipczuk, and Lukáš Mach. Lower bounds for the parameterized complexity of minimum fill-in and other completion problems. ACM Transactions on Algorithms (TALG), 16(2):1-31, 2020. Google Scholar
  5. Ivan Bliznets, Fedor V Fomin, Marcin Pilipczuk, and Michał Pilipczuk. Subexponential parameterized algorithm for interval completion. ACM Transactions on Algorithms (TALG), 14(3):1-62, 2018. Google Scholar
  6. Leizhen Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters, 58(4):171-176, 1996. Google Scholar
  7. Leizhen Cai and Yufei Cai. Incompressibility of h-free edge modification problems. Algorithmica, 71(3):731-757, 2015. Google Scholar
  8. Yufei Cai. Polynomial kernelisation of H-free edge modification problems. PhD thesis, Chinese University of Hong Kong, 2012. Google Scholar
  9. Christophe Crespelle, Pål Grønås Drange, Fedor V Fomin, and Petr A Golovach. A survey of parameterized algorithms and the complexity of edge modification. arXiv preprint, 2020. URL: http://arxiv.org/abs/2001.06867.
  10. R. Diestel. Graph Theory. Electronic library of mathematics. Springer, 2006. Google Scholar
  11. Pål Grønås Drange. Parameterized graph modification algorithms. PhD thesis, The University of Bergen, 2015. Google Scholar
  12. Ehab S El-Mallah and Charles J Colbourn. The complexity of some edge deletion problems. IEEE transactions on circuits and systems, 35(3):354-362, 1988. Google Scholar
  13. Fedor V Fomin, Petr A Golovach, and Dimitrios M Thilikos. On the parameterized complexity of graph modification to first-order logic properties. Theory of Computing Systems, 64(2):251-271, 2020. Google Scholar
  14. Archontia C Giannopoulou, Daniel Lokshtanov, Saket Saurabh, and Ondrej Suchy. Tree deletion set has a polynomial kernel but no opt^o(1) approximation. SIAM Journal on Discrete Mathematics, 30(3):1371-1384, 2016. Google Scholar
  15. Sylvain Guillemot, Frédéric Havet, Christophe Paul, and Anthony Perez. On the (non-) existence of polynomial kernels for p l-free edge modification problems. Algorithmica, 65(4):900-926, 2013. Google Scholar
  16. Haim Kaplan, Ron Shamir, and Robert E Tarjan. Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM Journal on Computing, 28(5):1906-1922, 1999. Google Scholar
  17. Sanjeev Khanna, Madhu Sudan, Luca Trevisan, and David P Williamson. The approximability of constraint satisfaction problems. SIAM Journal on Computing, 30(6):1863-1920, 2001. Google Scholar
  18. Stefan Kratsch and Magnus Wahlström. Two edge modification problems without polynomial kernels. In International Workshop on Parameterized and Exact Computation, pages 264-275. Springer, 2009. Google Scholar
  19. John M Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is np-complete. Journal of Computer and System Sciences, 20(2):219-230, 1980. Google Scholar
  20. Dániel Marx and RB Sandeep. Incompressibility of h-free edge modification problems: Towards a dichotomy. Journal of Computer and System Sciences, 125:25-58, 2022. Google Scholar
  21. Mihalis Yannakakis. Edge-deletion problems. SIAM Journal on Computing, 10(2):297-309, 1981. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact