Document Open Access Logo

Path Contraction Faster Than 2^n

Authors Akanksha Agrawal, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Prafullkumar Tale

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2019.11.pdf
  • Filesize: 5.56 MB
  • 13 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • path contraction
  • exact exponential time algorithms
  • graph algorithms
  • enumerating connected sets
  • 3-disjoint connected subgraphs

Metrics

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

Abstract

A graph G is contractible to a graph H if there is a set X subseteq E(G), such that G/X is isomorphic to H. Here, G/X is the graph obtained from G by contracting all the edges in X. For a family of graphs F, the F-Contraction problem takes as input a graph G on n vertices, and the objective is to output the largest integer t, such that G is contractible to a graph H in F, where |V(H)|=t. When F is the family of paths, then the corresponding F-Contraction problem is called Path Contraction. The problem Path Contraction admits a simple algorithm running in time 2^n * n^{O(1)}. In spite of the deceptive simplicity of the problem, beating the 2^n * n^{O(1)} bound for Path Contraction seems quite challenging. In this paper, we design an exact exponential time algorithm for Path Contraction that runs in time 1.99987^n * n^{O(1)}. We also define a problem called 3-Disjoint Connected Subgraphs, and design an algorithm for it that runs in time 1.88^n * n^{O(1)}. The above algorithm is used as a sub-routine in our algorithm for Path Contraction.

Cite As Get BibTex

Akanksha Agrawal, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Prafullkumar Tale. Path Contraction Faster Than 2^n. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.11

Author Details

Akanksha Agrawal
  • Ben-Gurion University of the Negev, Beersheba, Israel
Fedor V. Fomin
  • University of Bergen, Bergen, Norway
Daniel Lokshtanov
  • University of California Santa Barbara, Santa Barbara, California
Saket Saurabh
  • Institute of Mathematical Sciences, HBNI and UMI ReLaX Chennai, India
  • University of Bergen, Bergen, Norway
Prafullkumar Tale
  • Institute of Mathematical Sciences, HBNI, Chennai, India

Funding

  • Agrawal, Akanksha: During some part of the work, the author was supported by ERC Consolidator Grant SYSTEMATIC-GRAPH (No. 725978).
  • Saurabh, Saket: This work is supported by the European Research Council (ERC) via grant LOPPRE, reference no. 819416.

References

  1. Takao Asano and Tomio Hirata. Edge-Contraction Problems. Journal of Computer and System Sciences, 26(2):197-208, 1983. Google Scholar
  2. Andreas Björklund. Determinant Sums for Undirected Hamiltonicity. SIAM J. Comput., 43(1):280-299, 2014. Google Scholar
  3. Andries Evert Brouwer and Hendrik Jan Veldman. Contractibility and NP-completeness. Journal of Graph Theory, 11(1):71-79, 1987. Google Scholar
  4. Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström. On Problems as Hard as CNF-SAT. ACM Trans. Algorithms, 12(3):41:1-41:24, 2016. Google Scholar
  5. Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, and Jakub Onufry Wojtaszczyk. Solving the 2-disjoint connected subgraphs problem faster than 2ⁿ. Algorithmica, 70(2):195-207, 2014. Google Scholar
  6. Konrad K Dabrowski and Daniël Paulusma. Contracting bipartite graphs to paths and cycles. Information Processing Letters, 127:37-42, 2017. Google Scholar
  7. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  8. Jiří Fiala, Marcin Kamiński, and Daniël Paulusma. A note on contracting claw-free graphs. Discrete Mathematics and Theoretical Computer Science, 15(2):223-232, 2013. Google Scholar
  9. Fedor V. Fomin and Yngve Villanger. Treewidth computation and extremal combinatorics. Combinatorica, 32(3):289-308, 2012. Google Scholar
  10. Pinar Heggernes, Pim van 't Hof, Benjamin Lévêque, and Christophe Paul. Contracting chordal graphs and bipartite graphs to paths and trees. Discrete Applied Mathematics, 164:444-449, 2014. Google Scholar
  11. Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. Google Scholar
  12. 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
  13. Walter Kern and Daniel Paulusma. Contracting to a Longest Path in H-Free Graphs. arXiv preprint, 2018. URL: http://arxiv.org/abs/1810.01542.
  14. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal. ACM Trans. Algorithms, 14(2):13:1-13:30, 2018. Google Scholar
  15. Robert Endre Tarjan and Anthony E. Trojanowski. Finding a Maximum Independent Set. SIAM J. Comput., 6(3):537-546, 1977. Google Scholar
  16. Jan Arne Telle and Yngve Villanger. Connecting terminals and 2-disjoint connected subgraphs. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 418-428. Springer, 2013. Google Scholar
  17. Pim van't Hof, Daniël Paulusma, and Gerhard J Woeginger. Partitioning graphs into connected parts. Theoretical Computer Science, 410(47-49):4834-4843, 2009. Google Scholar
  18. 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
  19. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact