Contracting graphs to paths and trees

DOI10.1007/978-3-642-28050-4_5zbMATH Open1310.68229arXiv1104.3677OpenAlexW2174231092MaRDI QIDQ2441588

Author name not available (Why is that?)

Publication date: 25 March 2014

Published in: (Search for Journal in Brave)

Abstract: Vertex deletion and edge deletion problems play a central role in Parameterized Complexity. Examples include classical problems like Feedback Vertex Set, Odd Cycle Transversal, and Chordal Deletion. Interestingly, the study of edge contraction problems of this type from a parameterized perspective has so far been left largely unexplored. We consider two basic edge contraction problems, which we call Path-Contractibility and Tree-Contractibility. Both problems take an undirected graph $G$ and an integer $k$ as input, and the task is to determine whether we can obtain a path or an acyclic graph, respectively, by contracting at most $k$ edges of $G$. Our main contribution is an algorithm with running time $4^{k+O(lo{g}^{2}k)}+n^{O(1)}$ for Path-Contractibility and an algorithm with running time $4.88^k{n}^{O(1)}$ for Tree-Contractibility, based on a novel application of the color coding technique of Alon, Yuster and Zwick. Furthermore, we show that Path-Contractibility has a kernel with at most $5k+3$ vertices, while Tree-Contractibility does not have a polynomial kernel unless coNP $subseteq$ NP/poly. We find the latter result surprising, because of the strong connection between Tree-Contractibility and Feedback Vertex Set, which is known to have a vertex kernel with size $O(k^2)$.

Full work available at URL: https://arxiv.org/abs/1104.3677

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Contracting graphs to paths and trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2441588)