19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details
PDF | XML

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

More