Document Open Access Logo

Split Contraction: The Untold Story

Authors Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi

PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.5.pdf
  • Filesize: 0.63 MB
  • 14 pages

Document Identifiers

Author Details

Akanksha Agrawal
Daniel Lokshtanov
Saket Saurabh
Meirav Zehavi

Cite As Get BibTex

Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Split Contraction: The Untold Story. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.STACS.2017.5

Abstract

The edit operation that contracts edges, which is a fundamental operation in the theory of graph minors, has recently gained substantial scientific attention from the viewpoint of Parameterized Complexity. In this paper, we examine an important family of graphs, namely the family of split graphs, which in the context of edge contractions, is proven to be significantly less obedient than one might expect. Formally, given a graph G and an integer k, the Split Contraction problem asks whether there exists a subset X of edges of G such that G/X is a split graph and X has at most k elements. Here, G/X is the graph obtained from G by contracting edges in X. It was previously claimed that the Split Contraction problem is fixed-parameter tractable. However, we show that, despite its deceptive simplicity, it is W[1]-hard. Our main result establishes the following conditional lower bound: under the Exponential Time Hypothesis, the Split Contraction problem cannot be solved in time 2^(o(l^2)) * poly(n) where l is the vertex cover number of the input graph. We also verify that this lower bound is essentially tight. To the best of our knowledge, this is the first tight lower bound of the form 2^(o(l^2)) * poly(n) for problems parameterized by the vertex cover number of the input graph. In particular, our approach to obtain this lower bound borrows the notion of harmonious coloring from Graph Theory, and might be of independent interest.

Subject Classification

Keywords
  • Split Graph
  • Parameterized Complexity
  • Edge Contraction

Metrics

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

References

  1. Takao Asano and Tomio Hirata. Edge-contraction problems. Journal of Computer and System Sciences, 26(2):197-208, 1983. Google Scholar
  2. Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukas Mach, and Michal Pilipczuk. Lower bounds for the parameterized complexity of minimum fill-in and other completion problems. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1132-1151, 2016. Google Scholar
  3. Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, and Michal Pilipczuk. A subexponential parameterized algorithm for proper interval completion. In European Symposium on Algorithms (ESA), pages 173-184, 2014. Google Scholar
  4. Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, and Michal Pilipczuk. A subexponential parameterized algorithm for interval completion. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1116-1131, 2016. Google Scholar
  5. Leizhen Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters, 58(4):171-176, 1996. Google Scholar
  6. Leizhen Cai and Chengwei Guo. Contracting few edges to remove forbidden induced subgraphs. In International Workshop on Parameterized and Exact Computation (IPEC), pages 97-109, 2013. Google Scholar
  7. Yixin Cao. Unit interval editing is fixed-parameter tractable. In International Colloquium on Automata, Languages and Programming (ICALP), pages 306-317, 2015. Google Scholar
  8. Yixin Cao. Linear recognition of almost interval graphs. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1096-1115, 2016. Google Scholar
  9. Yixin Cao and Dániel Marx. Chordal editing is fixed-parameter tractable. In Symposium on Theoretical Aspects of Computer Science (STACS), pages 214-225, 2014. Google Scholar
  10. Yixin Cao and Dániel Marx. Interval deletion is fixed-parameter tractable. ACM Transactions on Algorithms (TALG), 11(3):21, 2015. Google Scholar
  11. Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, and Arkadiusz Socala. Tight bounds for graph homomorphism and subgraph isomorphism. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1643-1649, 2016. Google Scholar
  12. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  13. Marek Cygan, Marcin Pilipczuk, and Michal Pilipczuk. Known algorithms for edge clique cover are probably optimal. SIAM Journal on Computing, 45(1):67-83, 2016. Google Scholar
  14. Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness II: On completeness for W[1]. Theoretical Computer Science, 141(1&2):109-131, 1995. Google Scholar
  15. Pål Grønås Drange and Michal Pilipczuk. A polynomial kernel for trivially perfect editing. In European Symposium on Algorithms (ESA), pages 424-436, 2015. Google Scholar
  16. Pål Grønås Drange, Markus S. Dregi, Daniel Lokshtanov, and Blair D. Sullivan. On the threshold of intractability. In European Symposium on Algorithms (ESA), pages 411-423, 2015. Google Scholar
  17. Pål Grønås Drange, Fedor V. Fomin, Michal Pilipczuk, and Yngve Villanger. Exploring subexponential parameterized complexity of completion problems. In Symposium on Theoretical Aspects of Computer Science (STACS), pages 288-299, 2014. Google Scholar
  18. Keith Edwards. The harmonious chromatic number and the achromatic number. Surveys in Combinatorics, pages 13-48, 1997. Google Scholar
  19. 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
  20. Fedor V. Fomin and Yngve Villanger. Subexponential parameterized algorithm for minimum fill-in. SIAM Journal on Computing, 42(6):2197-2216, 2013. Google Scholar
  21. 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
  22. 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
  23. Sylvain Guillemot and Dániel Marx. A faster FPT algorithm for bipartite contraction. Information Processing Letters, 113(22-24):906-912, 2013. Google Scholar
  24. Chengwei Guo and Leizhen Cai. Obtaining split graphs by edge contraction. Theoretical Computer Science, 607:60-67, 2015. Google Scholar
  25. 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
  26. 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
  27. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  28. Christian Komusiewicz. Tight running time lower bounds for vertex deletion problems. arXiv preprint arXiv:1511.05449, 2015. Google Scholar
  29. Sin-Min Lee and John Mitchem. An upper bound for the harmonious chromatic number. Journal of Graph Theory, 11(4):565-567, 1987. Google Scholar
  30. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Slightly superexponential parameterized problems. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 760-776, 2011. Google Scholar
  31. Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. On the hardness of eliminating small induced subgraphs by contracting edges. In International Workshop on Parameterized and Exact Computation (IPEC), pages 243-254, 2013. Google Scholar
  32. Dániel Marx and Valia Mitsou. Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth. In International Colloquium on Automata, Languages and Programming (ICALP), pages 28:1-28:15, 2016. Google Scholar
  33. Colin McDiarimid and Luo Xinhua. Upper bounds for harmonious coloring. Journal of Graph Theory, 15(6):629-636, 1991. Google Scholar
  34. 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
  35. 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 About DROPS Imprint Privacy Contact