On the vertex cover $$P_3$$ P 3 problem parameterized by treewidth

Consider a graph G. A subset of vertices, F, is called a vertex cover $$P_t$$ P t ( $$VCP_t$$ V C P t ) set if every path of order t contains at least one vertex in F. Finding a minimum $$VCP_t$$ V C P t set in a graph is is NP-hard for any integer $$t\ge 2$$ t ≥ 2 and is called the $$MVCP_3$$ M V C P 3 problem. In this paper, we study the parameterized algorithms for the $$MVCP_3$$ M V C P 3 problem when the underlying graph G is parameterized by the treewidth. Given an n-vertex graph together with its tree decomposition of width at most p, we present an algorithm running in time $$4^{p}\cdot n^{O(1)}$$ 4 p · n O ( 1 ) for the $$MVCP_3$$ M V C P 3 problem. Moreover, we show that for the $$MVCP_3$$ M V C P 3 problem on planar graphs, there is a subexponential parameterized algorithm running in time $$2^{O(\sqrt{k})}\cdot n^{O(1)}$$ 2 O ( k ) · n O ( 1 ) where k is the size of the optimal solution.