Polynomial-time Algorithms for the 3-Path Vertex Cover Problem
TU Bergakademie Freiberg, Freiberg, Germany
The minimum 3-path vertex cover problem, introduced by Bresar et al., is an extension of the well-known minimum vertex cover problem. It asks for a vertex set S subset of V (G) of minimum cardinality such that G-S contains only independent vertices and edges. The talk will be divided into two parts. In the rst one we will present a polynomial-time algorithm which computes two disjoint sets T1; T2 such that: a) for any 3-path vertex cover S' in G[T2], union of S' and T1 is a 3-path vertex cover, b) there exists a minimum 3-path vertex cover in G which contains T1, c)|T2|<=6*\psi_3(G[T2]). In the second part of the talk we will consider reductions of the minimum 3-path vertex cover problem to the minimum vertex cover problem. Using these reductions we get polynomial-time algorithms to solve the problem in special graph classes and a new upper bound on \psi_3(G).