Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00413
On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2SAT
Vol. 21, no. 2, pp. 219243, 2017. Regular paper.
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 wellknown 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 polynomialtime 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 2SAT problem in multiple valued logic. For other parameterizations we derive W[1]hardness and paraNPcompleteness results.

Submitted: June 2016.
Reviewed: October 2016.
Revised: November 2016.
Accepted: December 2016.
Final: January 2017.
Published: January 2017.
Communicated by
William S. Evans

Journal Supporters
