A single exponential-time FPT algorithm for cactus contraction

TALE, PRAFULLKUMAR; Misra , Pranabendu; Krithika, R.

DR Home
→
PUBLICATIONS & PATENTS
→
JOURNAL ARTICLES
→
View Item

dc.contributor.author	Krithika, R.	en_US
dc.contributor.author	Misra , Pranabendu	en_US
dc.contributor.author	TALE, PRAFULLKUMAR	en_US
dc.date.accessioned	2023-04-19T06:48:09Z
dc.date.available	2023-04-19T06:48:09Z
dc.date.issued	2023-04	en_US
dc.identifier.citation	Theoretical Computer Science, 954, 113803.	en_US
dc.identifier.issn	0304-3975	en_US
dc.identifier.issn	1879-2294	en_US
dc.identifier.uri	https://doi.org/10.1016/j.tcs.2023.113803	en_US
dc.identifier.uri	http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/7715
dc.description.abstract	For a collection F of graphs, the F-CONTRACTION problem takes a graph G and an integer k as input and decides if G can be modified to some graph in F using at most k edge contractions. The F-CONTRACTION problem is NP-Complete for several graph classes F. Heggernes et al. (2014) [4] initiated the study of F-CONTRACTION in the realm of parameterized complexity. They showed that it is FPT if F is the set of all trees or the set of all paths. In this paper, we study F-CONTRACTION where F is the set of all cactus graphs and show that we can solve it in 2O(k) center dot \|V(G)\|O(1) time.	en_US
dc.language.iso	en	en_US
dc.publisher	Elsevier B.V.	en_US
dc.subject	Fixed parameter tractable algorithms	en_US
dc.subject	Graph contraction	en_US
dc.subject	Cactus graphs	en_US
dc.subject	2023-APR-WEEK1	en_US
dc.subject	TOC-APR-2023	en_US
dc.subject	2023	en_US
dc.title	A single exponential-time FPT algorithm for cactus contraction	en_US
dc.type	Article	en_US
dc.contributor.department	Dept. of Mathematics	en_US
dc.identifier.sourcetitle	Theoretical Computer Science	en_US
dc.publication.originofpublisher	Foreign	en_US