Zongwen Bai ; Jianhua Tu ; Yongtang Shi - 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 - https://doi.org/10.23638/DMTCS-21-4-17
An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth

Authors: Zongwen Bai ; Jianhua Tu ; Yongtang Shi

    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$.


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

    Share

    Consultation statistics

    This page has been seen 844 times.
    This article's PDF has been downloaded 178 times.