Document Open Access Logo

Path Contraction Faster Than 2^n

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

PDF
Thumbnail PDF

File

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

Document Identifiers

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.

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

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.

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

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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact