An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth

Abstract

Given a graph $G=(V,E)$ and a positive integer $t\ge 2$, the task in the vertex cover $P_t$ ($VC{P}_t$) problem is to find a minimum subset of vertices $F\subseteq V$ such that every path of order $t$ in $G$ contains at least one vertex from $F$. The $VC{P}_t$ problem is NP-complete for any integer $t\ge 2$ and has many applications in real world. Recently, the authors presented a dynamic programming algorithm running in time $4^p\cdot n^{O(1)}$ for the $VC{P}_3$ problem on $n$-vertex graphs with treewidth $p$. In this paper, we propose an improvement of it and improved the time-complexity to $3^p\cdot n^{O(1)}$. The connected vertex cover $P_3$ ($CVC{P}_3$) problem is the connected variation of the $VC{P}_3$ problem where $G[F]$ is required to be connected. Using the Cut\&Count technique, we give a randomized algorithm with runtime $4^p\cdot n^{O(1)}$ for the $CVC{P}_3$ problem on $n$-vertex graphs with treewidth $p$.

arXiv admin note: text overlap with arXiv:1103.0534 by other authors

References in corpus (1)

• Minimum k-path vertex cover

Cited by in corpus (2)

• Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
• Hitting minors on bounded treewidth graphs. III. Lower bounds