{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:38:40Z","timestamp":1753889920018,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","issue":"Discrete Algorithms","license":[{"start":{"date-parts":[[2019,11,4]],"date-time":"2019-11-04T00:00:00Z","timestamp":1572825600000},"content-version":"am","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"},{"start":{"date-parts":[[2019,11,4]],"date-time":"2019-11-04T00:00:00Z","timestamp":1572825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"},{"start":{"date-parts":[[2019,11,4]],"date-time":"2019-11-04T00:00:00Z","timestamp":1572825600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>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\\&amp;amp;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$.<\/jats:p><jats:p>Comment: arXiv admin note: text overlap with arXiv:1103.0534 by other authors<\/jats:p>","DOI":"10.23638\/dmtcs-21-4-17","type":"journal-article","created":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T16:35:49Z","timestamp":1743698149000},"source":"Crossref","is-referenced-by-count":0,"title":["An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth"],"prefix":"10.23638","volume":"vol. 21 no. 4","author":[{"given":"Zongwen","family":"Bai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianhua","family":"Tu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yongtang","family":"Shi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2019,11,4]]},"container-title":["Discrete Mathematics &amp; Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/arxiv.org\/pdf\/1603.09448v6","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/arxiv.org\/pdf\/1603.09448v6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T16:35:49Z","timestamp":1743698149000},"score":1,"resource":{"primary":{"URL":"http:\/\/dmtcs.episciences.org\/1425"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,4]]},"references-count":0,"journal-issue":{"issue":"Discrete Algorithms","published-online":{"date-parts":[[2019,11,4]]}},"URL":"https:\/\/doi.org\/10.23638\/dmtcs-21-4-17","relation":{"has-preprint":[{"id-type":"arxiv","id":"1603.09448v5","asserted-by":"subject"},{"id-type":"arxiv","id":"1603.09448v4","asserted-by":"subject"},{"id-type":"arxiv","id":"1603.09448v2","asserted-by":"subject"},{"id-type":"arxiv","id":"1603.09448v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"1603.09448","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1603.09448","asserted-by":"subject"}]},"ISSN":["1365-8050"],"issn-type":[{"type":"electronic","value":"1365-8050"}],"subject":[],"published":{"date-parts":[[2019,11,4]]},"article-number":"1425"}}