2026-07-23T00:26:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10587 2024-03-06T10:46:12Z ddc:004 open_access

Path Contraction Faster Than 2^n Agrawal, Akanksha Fomin, Fedor V. Lokshtanov, Daniel Saurabh, Saket Tale, Prafullkumar path contraction exact exponential time algorithms graph algorithms enumerating connected sets 3-disjoint connected subgraphs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Akanksha Agrawal and Fedor V. Fomin and Daniel Lokshtanov and Saket Saurabh and Prafullkumar Tale 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.11 urn:nbn:de:0030-drops-105874 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.11 eng https://creativecommons.org/licenses/by/3.0/legalcode