19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Contracting graphs to paths and trees
Presented by Dr. Pim VAN 'T HOF
Type: Oral presentation
Track: Algorithmic Graph Theory
Content
The problems Path-Contractibility and Tree-Contractibility take as input an undirected graph G and an integer k, and ask whether we can obtain a path or a tree, respectively, by contracting at most k edges of G. Both problems are NP-complete, and fixed parameter tractibility follows from Courcelle's Theorem. We present algorithms with running time c^k n^{O(1)} with small constants c<5 for both problems. 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 is a subset of NP/poly. Interestingly, Feedback Vertex Set, which can be seen as the vertex deletion variant of Tree-Contractibility, is known to have a kernel with O(k^2) vertices.
Place
Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled
Primary authors
- Prof. Pinar HEGGERNES University of Bergen
- Dr. Pim VAN 'T HOF University of Bergen
- Dr. Christophe PAUL CNRS, LIRMM, Universite Montpellier 2
- Dr. Benjamin LEVEQUE CNRS, LIRMM, Universite Montpellier 2