Two fixed-parameter algorithms for Vertex Covering by Paths on Trees

Vertex Covering by Paths on Trees with applications in machine translation is the task to cover all vertices of a tree T=(V,E) by choosing a minimum-weight subset of given paths in the tree. The problem is NP-hard and has recently been solved by an exact algorithm running in O(C4⋅2|V|) time, where C denotes the maximum number of paths covering a tree vertex. We improve this running time to O(C2⋅C⋅|V|). On the route to this, we introduce the problem Tree-like Weighted Hitting Set which might be of independent interest. In addition, for the unweighted case of Vertex Covering by Paths on Trees, we present an exact algorithm using a search tree of size O(k2⋅k!), where k denotes the number of chosen covering paths. Finally, we briefly discuss the existence of a size-O(k2) problem kernel.