dc.contributor.author | Agrawal, Akanksha | |
dc.contributor.author | Fomin, Fedor | |
dc.contributor.author | Lokshtanov, Daniel | |
dc.contributor.author | Saurabh, Saket | |
dc.contributor.author | Tale, Prafullkumar | |
dc.date.accessioned | 2021-05-18T11:30:42Z | |
dc.date.available | 2021-05-18T11:30:42Z | |
dc.date.created | 2021-01-12T16:00:51Z | |
dc.date.issued | 2020 | |
dc.Published | SIAM Journal on Discrete Mathematics. 2020, 34 1302-1325. | |
dc.identifier.issn | 0895-4801 | |
dc.identifier.uri | https://hdl.handle.net/11250/2755454 | |
dc.description.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 $\cal F$, the $\mathcal{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 {\cal F}$, where $|V(H)|=t$. When $\cal F$ is the family of paths, then the corresponding $\mathcal{F}$-Contraction problem is called Path Contraction. The problem Path Contraction admits a simple algorithm running in time $2^{n}\cdot n^{{\mathcal{O}}(1)}$. In spite of the deceptive simplicity of the problem, beating the $2^{n}\cdot n^{{\mathcal{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}\cdot n^{{\mathcal 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\cdot n^{{\mathcal O}(1)}$. The above algorithm is used as a subroutine in our algorithm for Path Contraction. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | SIAM | en_US |
dc.title | Path contraction faster than $2^n$ | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright 2020 Society for Industrial and Applied Mathematics | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 1 | |
dc.identifier.doi | 10.1137/19M1259638 | |
dc.identifier.cristin | 1870029 | |
dc.source.journal | SIAM Journal on Discrete Mathematics | en_US |
dc.source.40 | 34 | |
dc.source.pagenumber | 1302-1325 | en_US |
dc.relation.project | Norges forskningsråd: 263317 | en_US |
dc.identifier.citation | SIAM Journal on Discrete Mathematics. 2020, 34(2), 1302–1325 | en_US |
dc.source.volume | 34 | en_US |
dc.source.issue | 2 | en_US |