Oliver Bachtler

• Given a universe \(U\) and a collection \(\mathcal{S}\) of subsets of \(U\), a hitting set is a set \(A\subseteq U\) such that \(A\cap S\neq. \emptyset\) for all \(S\in\mathcal{S}\). The hitting set problem is a well known NP-complete problem that asks to find a minimum hitting set for a given instance \((U,S)\). If the universe \(U\) is the set of nodes of a graph and a set \(S\in\mathcal{S}\) corresponds to the set of nodes on a path of the graph with \(|S|=k\), we call this problem a \(k\)-path cover. The aim of this thesis is to regard these special cases of the hitting set problem in detail. To this end the first part formally introduces the hitting set and path cover problems and summarises some known results. Next the so called primal-dual method, and how it can be used to approximate hitting set problems in general, is described. It is subsequently applied to the path cover problems on paths, trees, and general graphs and the resulting approximation guarantees are determined. Afterwards the complexity of these problems is analysed and they are either shown to be NP-hard or a polynomial time algorithm is presented. The final part covers a few possible restrictions that are sufficient to make NP-hard instances on trees solvable in polynomial time. It turns out that, not too surprisingly, \(k\)-path covers on general graphs are hard and the primal-dual method gives a \(k\)-approximation for these. While there are instances for trees where an approximation factor of \(k\) is reached as well, these problems can even be solved optimally in several cases, especially when allowing a few additional restrictions. The case of paths leads to an approximation guarantee of two (or even slightly better). However, these problems can be solved to optimality in linear time.