Document Open Access Logo

On the Parameterized Approximability of Contraction to Classes of Chordal Graphs

Authors Spoorthy Gunda, Pallavi Jain, Daniel Lokshtanov, Saket Saurabh, Prafullkumar Tale

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.51.pdf
  • Filesize: 0.71 MB
  • 19 pages

Document Identifiers

Author Details

Spoorthy Gunda
  • Simon Fraser University, Burnaby, Canada
Pallavi Jain
  • Indian Institute of Technology Jodhpur, India
Daniel Lokshtanov
  • University of California, Santa Barbara, CA, USA
Saket Saurabh
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
  • University of Bergen, Norway
Prafullkumar Tale
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany

Funding

  • Saurabh, Saket: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 819416), and Swarnajayanti Fellowship (No DST/SJF/MSA01/2017-18).
  • Tale, Prafullkumar: This research is a part of a project that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme under grant agreement SYSTEMATICGRAPH (No. 725978). Most part of this project was completed when the author was a Senior Research Fellow at The Institute of Mathematical Sciences, HBNI, Chennai, India.

Cite AsGet BibTex

Spoorthy Gunda, Pallavi Jain, Daniel Lokshtanov, Saket Saurabh, and Prafullkumar Tale. On the Parameterized Approximability of Contraction to Classes of Chordal Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 51:1-51:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.51

Abstract

A graph operation that contracts edges is one of the fundamental operations in the theory of graph minors. Parameterized Complexity of editing to a family of graphs by contracting k edges has recently gained substantial scientific attention, and several new results have been obtained. Some important families of graphs, namely the subfamilies of chordal graphs, in the context of edge contractions, have proven to be significantly difficult than one might expect. In this paper, we study the F-Contraction problem, where F is a subfamily of chordal graphs, in the realm of parameterized approximation. Formally, given a graph G and an integer k, F-Contraction asks whether there exists X ⊆ E(G) such that G/X ∈ F and |X| ≤ k. Here, G/X is the graph obtained from G by contracting edges in X. We obtain the following results for the F-Contraction problem. - Clique Contraction is known to be FPT. However, unless NP ⊆ coNP/poly, it does not admit a polynomial kernel. We show that it admits a polynomial-size approximate kernelization scheme (PSAKS). That is, it admits a (1 + ε)-approximate kernel with {O}(k^{f(ε)}) vertices for every ε > 0. - Split Contraction is known to be W[1]-Hard. We deconstruct this intractability result in two ways. Firstly, we give a (2+ε)-approximate polynomial kernel for Split Contraction (which also implies a factor (2+ε)-FPT-approximation algorithm for Split Contraction). Furthermore, we show that, assuming Gap-ETH, there is no (5/4-δ)-FPT-approximation algorithm for Split Contraction. Here, ε, δ > 0 are fixed constants. - Chordal Contraction is known to be W[2]-Hard. We complement this result by observing that the existing W[2]-hardness reduction can be adapted to show that, assuming FPT ≠ W[1], there is no F(k)-FPT-approximation algorithm for Chordal Contraction. Here, F(k) is an arbitrary function depending on k alone. We say that an algorithm is an h(k)-FPT-approximation algorithm for the F-Contraction problem, if it runs in FPT time, and on any input (G, k) such that there exists X ⊆ E(G) satisfying G/X ∈ F and |X| ≤ k, it outputs an edge set Y of size at most h(k) ⋅ k for which G/Y is in F. We find it extremely interesting that three closely related problems have different behavior with respect to FPT-approximation.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Graph Contraction
  • FPT-Approximation
  • Inapproximability
  • Lossy Kernels

Metrics

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

Related Versions

References

  1. Akanksha Agarwal, Saket Saurabh, and Prafullkumar Tale. On the parameterized complexity of contraction to generalization of trees. Theory of Computing Systems, pages 1-28, 2017. Google Scholar
  2. Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Split contraction: The untold story. In STACS, pages 5:1-5:14, 2017. URL: https://doi.org/10.4230/LIPIcs.STACS.2017.5.
  3. Takao Asano and Tomio Hirata. Edge-contraction problems. Journal of Computer and System Sciences, 26(2):197-208, 1983. Google Scholar
  4. Reuven Bar-Yehuda and Shimon Even. A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 2(2):198-203, 1981. Google Scholar
  5. Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, and Michal Pilipczuk. A subexponential parameterized algorithm for proper interval completion. SIAM Journal on Discrete Mathematics, 29(4):1961-1987, 2015. Google Scholar
  6. Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, and Michal Pilipczuk. Subexponential parameterized algorithm for interval completion. ACM Transactions on Algorithms, 14(3):35:1-35:62, 2018. Google Scholar
  7. Leizhen Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters, 58(4):171-176, 1996. Google Scholar
  8. Leizhen Cai and Chengwei Guo. Contracting few edges to remove forbidden induced subgraphs. In IPEC, pages 97-109, 2013. Google Scholar
  9. Yixin Cao. Linear recognition of almost interval graphs. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1096-1115, Arlington, Virginia, 2016. ACM-SIAM. Google Scholar
  10. Yixin Cao. Unit interval editing is fixed-parameter tractable. Information and Computation, 253:109-126, 2017. Google Scholar
  11. Yixin Cao and Dániel Marx. Interval deletion is fixed-parameter tractable. ACM Transactions on Algorithms, 11(3):21:1-21:35, 2015. Google Scholar
  12. Yixin Cao and Dániel Marx. Chordal editing is fixed-parameter tractable. Algorithmica, 75(1):118-137, 2016. Google Scholar
  13. Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan. From Gap-ETH to FPT-inapproximability: Clique, dominating set, and more. In FOCS, pages 743-754, 2017. URL: https://doi.org/10.1109/FOCS.2017.74.
  14. Marek Cygan, Fedor V. Fomin, ℒukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer International Publishing, Switzerland, 2015. Google Scholar
  15. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer-Verlag Berlin Heidelberg, Germany, 2012. Google Scholar
  16. Rod G. Downey and Michael R. Fellows. Fundamentals of Parameterized complexity. Springer-Verlag, London, 2013. Google Scholar
  17. Pål Grønås Drange, Markus Sortland Dregi, Daniel Lokshtanov, and Blair D. Sullivan. On the threshold of intractability. In Algorithms - 23rd Annual European Symposium (ESA), pages 411-423, Germany, 2015. Springer-Verlag Berlin Heidelberg. Google Scholar
  18. Pål Grønås Drange, Fedor V. Fomin, Michal Pilipczuk, and Yngve Villanger. Exploring the subexponential complexity of completion problems. ACM Transactions on Computation Theory, 7(4):14:1-14:38, 2015. Google Scholar
  19. Pål Grønås Drange and Michal Pilipczuk. A polynomial kernel for trivially perfect editing. Algorithmica, 80:3481-3524, 2018. Google Scholar
  20. Pavel Dvorák, Andreas Emil Feldmann, Dusan Knop, Tomás Masarík, Tomas Toufar, and Pavel Veselý. Parameterized approximation schemes for steiner trees with small number of steiner vertices. In STACS, pages 26:1-26:15, 2018. Google Scholar
  21. Eduard Eiben, Danny Hermelin, and M. S. Ramanujan. Lossy kernels for hitting subgraphs. In MFCS, pages 67:1-67:14, 2017. URL: https://doi.org/10.4230/LIPIcs.MFCS.2017.67.
  22. Eduard Eiben, Mithilesh Kumar, Amer E Mouawad, Fahad Panolan, and Sebastian Siebertz. Lossy kernels for connected dominating set on sparse graphs. SIAM Journal on Discrete Mathematics, 33(3):1743-1771, 2019. Google Scholar
  23. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag Berlin Heidelberg, Germany, 2006. Google Scholar
  24. Fedor V Fomin, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, and Yngve Villanger. Tight bounds for parameterized complexity of cluster editing with a small number of clusters. Journal of Computer and System Sciences, 80(7):1430-1447, 2014. Google Scholar
  25. Fedor V Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: theory of parameterized preprocessing. Cambridge University Press, 2019. Google Scholar
  26. Fedor V Fomin and Yngve Villanger. Subexponential parameterized algorithm for minimum fill-in. SIAM Journal on Computing, 42(6):2197-2216, 2013. Google Scholar
  27. Esha Ghosh, Sudeshna Kolay, Mrinal Kumar, Pranabendu Misra, Fahad Panolan, Ashutosh Rai, and M. S. Ramanujan. Faster parameterized algorithms for deletion to split graphs. Algorithmica, 71(4):989-1006, 2015. Google Scholar
  28. Petr A. Golovach, Pim van 't Hof, and Daniel Paulusma. Obtaining planarity by contracting few edges. Theoretical Computer Science, 476:38-46, 2013. Google Scholar
  29. Martin Charles Golumbic. Algorithmic graph theory and perfect graphs, volume 57. Elsevier, Academic Press, 2004. Google Scholar
  30. Sylvain Guillemot and Dániel Marx. A faster FPT algorithm for bipartite contraction. Information Processing Letters, 113(22-24):906-912, 2013. Google Scholar
  31. Spoorthy Gunda, Pallavi Jain, Daniel Lokshtanov, Saket Saurabh, and Prafullkumar Tale. On the parameterized approximability of contraction to classes of chordal graphs, 2020. URL: http://arxiv.org/abs/2006.10364.
  32. Chengwei Guo and Leizhen Cai. Obtaining split graphs by edge contraction. Theoretical Computer Science, 607:60-67, 2015. Google Scholar
  33. Pinar Heggernes, Pim van 't Hof, Benjamin Lévêque, Daniel Lokshtanov, and Christophe Paul. Contracting graphs to paths and trees. Algorithmica, 68(1):109-132, 2014. Google Scholar
  34. Pinar Heggernes, Pim van 't Hof, Daniel Lokshtanov, and Christophe Paul. Obtaining a bipartite graph by contracting few edges. SIAM Journal on Discrete Mathematics, 27(4):2143-2156, 2013. Google Scholar
  35. Karthik C. S., Bundit Laekhanukit, and Pasin Manurangsi. On the parameterized complexity of approximating dominating set. In STOC, pages 1283-1296. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188896.
  36. R Krithika, Diptapriyo Majumdar, and Venkatesh Raman. Revisiting connected vertex cover: Fpt algorithms and lossy kernels. Theory of Computing Systems, 62(8):1690-1714, 2018. Google Scholar
  37. R Krithika, Pranabendu Misra, Ashutosh Rai, and Prafullkumar Tale. Lossy kernels for graph contraction problems. In FSTTCS, pages 23:1-23:14, 2016. Google Scholar
  38. Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. On the hardness of eliminating small induced subgraphs by contracting edges. In IPEC, pages 243-254, 2013. Google Scholar
  39. Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Geevarghese Philip, and Saket Saurabh. A (2 + ε)-factor approximation algorithm for split vertex deletion. In 47th International Colloquium on Automata, Languages and Programming, ICALP 2020, volume 168 of LIPIcs, page to appear, 2020. Google Scholar
  40. Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Lossy kernelization. In STOC, pages 224-237, 2017. Google Scholar
  41. Pasin Manurangsi. A note on max k-vertex cover: Faster FPT-AS, smaller approximate kernel and improved approximation. In SOSA, 2019. Google Scholar
  42. Rolf Niedermeier. Invitation to fixed-parameter algorithms. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, Oxford, 2006. Google Scholar
  43. M. S. Ramanujan. An approximate kernel for connected feedback vertex set. In 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 77:1-77:14, 2019. Google Scholar
  44. Sebastian Siebertz. Lossy kernels for connected distance-r domination on nowhere dense graph classes. arXiv preprint, 2017. URL: http://arxiv.org/abs/1707.09819.
  45. René van Bevern, Till Fluschnik, and Oxana Yu Tsidulko. On (1+ ε)-approximate problem kernels for the rural postman problem. arXiv preprint, 2018. URL: http://arxiv.org/abs/1812.10131.
  46. Toshimasa Watanabe, Tadashi Ae, and Akira Nakamura. On the removal of forbidden graphs by edge-deletion or by edge-contraction. Discrete Applied Mathematics, 3(2):151-153, 1981. Google Scholar
  47. Toshimasa Watanabe, Tadashi Ae, and Akira Nakamura. On the NP-hardness of edge-deletion and-contraction problems. Discrete Applied Mathematics, 6(1):63-78, 1983. 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