Jakub Zygadło
Schedae Informaticae, Volume 29, First View 2020, pp. 9 - 21
https://doi.org/10.4467/20838476SI.20.001.14380
We consider a version of the k-path vertex cover problem that asks for the minimum weight subset C of vertices of a graph G such that every path on k vertices in G has at least one vertex in common with C. We present two dynamic algorithms solving this problem on interval graphs. The first one works on general interval graphs but is in practice limited to small values of k.
The second algorithm computes minimum weight vertex cover for arbitrary k on proper interval graph G = (V,E) in time O(|V|^2|E|).
Jakub Zygadło
Schedae Informaticae, Volume 24, 2015, pp. 239 - 251
https://doi.org/10.4467/20838476SI.16.020.4361A subset S of vertices of a graph G = (V,E) is called a k-path vertex cover if every path on k vertices in G contains at least one vertex from S. Denote by Ψk (G) the minimum cardinality of a k-path vertex cover in G and form a sequence Ψ (G) = (Ψ1(G), Ψ2 (G), . . . , Ψ|V|(G)), called the path sequence of G. In this paper we prove necessary and sufficient conditions for two integers to appear on fixed positions in Ψ(G). A complete list of all possible path sequences (with multiplicities) for small connected graphs is also given.