An improved algorithm for the vertex cover P₃ problem on graphs of bounded treewidth

Abstract: Given a graph

G = (V, E)

and a positive integer

t g e q 2

, the task in the vertex cover

P_{t}

(

V C P_{t}

) problem is to find a minimum subset of vertices

F s u b s e t e q V

such that every path of order

t

in

G

contains at least one vertex from

F

. The

V C P_{t}

problem is NP-complete for any integer

t g e q 2

and has many applications in real world. Recently, the authors presented a dynamic programming algorithm running in time

4^{p} c d o t n^{O (1)}

for the

V C 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} c d o t n^{O (1)}

. The connected vertex cover

P_{3}

(

C V C P_{3}

) problem is the connected variation of the

V C 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} c d o t n^{O (1)}

for the

C V C P_{3}

problem on

n

-vertex graphs with treewidth

p

.

Recommendations

Cited in

(16)

This page was built for publication: An improved algorithm for the vertex cover \(P_3\) problem on graphs of bounded treewidth