On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT

Abstract

${\rm H{\small ITTING}~S{\small ET}}$ is a classic problem in combinatorial optimization. Its input consists of a set system $\mathcal F$ over a finite universe $U$ and an integer $t$; the question is whether there is a set of $t$ elements that intersects every set in $\mathcal F$. The ${\rm H{\small ITTING}~S{\small ET}}$ problem parameterized by the size of the solution is a well-known W[2]-complete problem in parameterized complexity theory. In this paper we investigate the complexity of ${\rm H{\small ITTING}~S{\small ET}}$ under various structural parameterizations of the input. Our starting point is the folklore result that ${\rm H{\small ITTING}~S{\small ET}}$ is polynomial-time solvable if there is a tree $T$ on vertex set $U$ such that the sets in $\mathcal F$ induce connected subtrees of $T$. We consider the case that there is a treelike graph with vertex set $U$ such that the sets in $\mathcal F$ induce connected subgraphs; the parameter of the problem is a measure of how treelike the graph is. Our main positive result is an algorithm that, given a graph $G$ with cyclomatic number $k$, a collection $\mathcal P$ of simple paths in $G$, and an integer $t$, determines in time $2^{5k} (|G| +|\mathcal P|)^{\mathcal O(1)}$ whether there is a vertex set of size $t$ that hits all paths in $\mathcal P$. It is based on a connection to the 2-SAT problem in multiple valued logic. For other parameterizations we derive W[1]-hardness and para-NP-completeness results.