Hitting set

The hitting set problem is an NP-complete problem in set theory.For a given list of sets, a "hitting set" is a set of elements so that each set in the given list is 'touched' by the hitting set.In the hitting set problem, the task is to find a small hitting set.

Hitting sets are a natural generalization of vertex covers to hypergraphs, and hitting sets are dual to set covers.

Definition

An instance of the hitting set problem consists of:
* a hypergraph $mathcal\; H\; =\; (X,E)$, that is, $X$ is a finite set of vertices and $E=\{E\_1,\; E\_2,\; dots,\; E\_n\}$ is a set of hyperedges $E\_i$, that is, subsets of $X$, and
* a positive integer $k\; le\; |X|$The problem is to determine whether there is a hitting set of size "k", that is, a subset "H" of "X" such that:$|H|\; le\; k$ and, for all $i\; in\; \{1,2,dots,n\}$, it holds $(H\; cap\; E\_i)\; e\; varnothing.$

Tractability

The hitting set problem is NP-complete since it is a generalization of the NP-complete vertex cover problem. If you restrict the hyperedges $E\_i$ to have size exactly two, the set system describes a simple undirected graph $G=(X,E)$ whose vertex covers are exactly the hitting sets.

Fixed-Parameter Tractability

For the hitting set problem, different parameterizations make sense.cite book
author = Flum, J.
coauthors = Grohe, M.
year = 2006
title = Parameterized Complexity Theory
publisher = Springer
url = http://www.springer.com/east/home/generic/search/results?SGWID=5-40109-22-141358322-0
isbn = 978-3-540-29952-3]

The hitting set problem is $W\; [2]$-complete for the parameter $k$, that is, it is unlikely that there is an algorithm that runs in time $f(k)\; n^\{mathcal\; O(1)\}$.

The hitting set problem is fixed-parameter tractable for the parameter $k+d$, where $d$ is the size of the largest set $|E\_i|$. More specifically, there is an algorithm for hitting set that runs in time $d^k\; n^\{mathcal\; O(1)\}$.

Approximability

...

Dual Problem

The Hitting Set Problem is dual to Set Cover.An instance of set cover can be viewed as an arbitrary bipartite graph, with sets represented by vertices on the left, the universe represented by vertices on the right, and edges representing the inclusion of elements in sets. The task is then to find a minimum cardinality subset of left-vertices which covers all of the right-vertices. In the Hitting set problem, the objective is to cover the left-vertices using a minimum subset of the right vertices. Converting from one problem to the other is therefore achieved by interchanging the two sets of vertices.

References