Bai, Zongwen and Tu, Jianhua and Shi, Yongtang - An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth

dmtcs:1425 - Discrete Mathematics & Theoretical Computer Science, November 4, 2019, vol. 21 no. 4
An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth

Authors: Bai, Zongwen and Tu, Jianhua and Shi, Yongtang

Given a graph $G=(V,E)$ and a positive integer $t\geq2$, the task in the vertex cover $P_t$ ($VCP_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 $VCP_t$ problem is NP-complete for any integer $t\geq2$ 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 $VCP_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$ ($CVCP_3$) problem is the connected variation of the $VCP_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 $CVCP_3$ problem on $n$-vertex graphs with treewidth $p$.


Source : oai:arXiv.org:1603.09448
Volume: vol. 21 no. 4
Section: Discrete Algorithms
Published on: November 4, 2019
Submitted on: July 30, 2017
Keywords: Mathematics - Combinatorics,Computer Science - Data Structures and Algorithms


Share