Algorithms for the Weighted $k$-Path Vertex Cover Problem for Trees and Cacti
Rastislav Krivoš Belluš
P. J. Šafárik University in Košice, Slovakia
PDF
Minisymposium: VERTEX COLOURINGS AND FORBIDDEN SUBGRAPHS
Content: $k$-Path Vertex Cover Problem is NP-hard for several classes of graphs. We have focused on the weighted version of this problem. We will analyze complexity of exact algorithms for finding minimum $k$-Path Vertex Cover for trees and cacti graphs using dynamic programming and with parametrized complexity depending on its girth.