Vertex cover in hypergraphs

In graph theory, a vertex cover in a hypergraph is a set of vertices, such that every hyperedge of the hypergraph contains at least one vertex of that set. It is an extension of the notion of vertex cover in a graph.^[1]^{: 466–470}^[2]

An equivalent term is a hitting set: given a collection of sets, a set which intersects all sets in the collection in at least one element is called a hitting set. The equivalence can be seen by mapping the sets in the collection onto hyperedges.

Another equivalent term, used more in a combinatorial context, is transversal. However, some definitions of transversal require that every hyperedge of the hypergraph contains precisely one vertex from the set.

Definition

Recall that a hypergraph $H$ is a pair $(V, E)$ , where $V$ is a set of vertices and $E$ is a set of subsets of $V$ called hyperedges. Each hyperedge may contain one or more vertices.

A vertex-cover (aka hitting set or transversal) in $H$ is set $T \subseteq V$ such that, for all hyperedges $e \in E$ , it holds that $T \cap e \neq \emptyset$ .

The vertex-cover number (aka transversal number) of a hypergraph $H$ is the smallest size of a vertex cover in $H$ . It is often denoted by $τ (H)$ .^[1]^: 466

For example, if $H$ is this 3-uniform hypergraph:

{ {1,2,3}, {1,4,5}, {4,5,6}, {2,3,6} }

then $H$ has admits several vertex-covers of size 2, for example:

{1, 6}

However, no subset of size 1 hits all the hyperedges of $H$ . Hence the vertex-cover number of $H$ is 2.

Note that we get back the case of vertex covers for simple graphs if the maximum size of the hyperedges is 2.

Algorithms

The computational problems minimum hitting set and hitting set are defined as in the case of graphs.

If the maximum size of a hyperedge is restricted to $d$ , then the problem of finding a minimum $d$ -hitting set permits a $d$ -approximation algorithm. Assuming the unique games conjecture, this is the best constant-factor algorithm that is possible and otherwise there is the possibility of improving the approximation to $d - 1$ .^[3]

For the hitting set problem, different parametrizations make sense.^[4] The hitting set problem is $W [2]$ -complete for the parameter $OPT$ , that is, it is unlikely that there is an algorithm that runs in time $f (OPT) n O (1)$ where $OPT$ is the cardinality of the smallest hitting set. The hitting set problem is fixed-parameter tractable for the parameter $OPT + d$ , where $d$ is the size of the largest edge of the hypergraph. More specifically, there is an algorithm for hitting set that runs in time $d OPT n O (1)$ .

Hitting set and set cover

The hitting set problem is equivalent to the set cover problem: An instance of set cover can be viewed as an arbitrary bipartite graph, with sets represented by vertices on the left, elements of 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.

Applications

An example of a practical application involving the hitting set problem arises in efficient dynamic detection of race condition.^[5]^[6] In this case, each time global memory is written, the current thread and set of locks held by that thread are stored. Under lockset-based detection, if later another thread writes to that location and there is not a race, it must be because it holds at least one lock in common with each of the previous writes. Thus the size of the hitting set represents the minimum lock set size to be race-free. This is useful in eliminating redundant write events, since large lock sets are considered unlikely in practice.

Fractional vertex cover

A fractional vertex-cover is a function assigning a weight in $[0,1]$ to each vertex in $V$ , such that for every hyperedge $e$ in $E$ , the sum of fractions of vertices in $e$ is at least 1. A vertex cover is a special case of a fractional vertex cover in which all weights are either 0 or 1. The size of a fractional vertex-cover is the sum of fractions of all vertices.

The fractional vertex-cover number of a hypergraph $H$ is the smallest size of a fractional vertex-cover in $H$ . It is often denoted by $τ *(H)$ .

Since a vertex-cover is a special case of a fractional vertex-cover, for every hypergraph $H$ :

fractional-vertex-cover-number( $H$ ) ≤ vertex-cover-number ( $H$ );

In symbols:

$\tau ^{*}(H)\leq \tau (H).$

The fractional-vertex-cover-number of a hypergraph is, in general, smaller than its vertex-cover-number. A theorem of László Lovász provides an upper bound on the ratio between them:^[7]

If each vertex is contained in at most $d$ hyperedges (i.e., the degree of the hypergraph is at most $d$ ), then
${\frac {\tau (H)}{\tau ^{*}(H)}}\leq 1+\ln(d).$

Transversals in finite projective planes

A finite projective plane is a hypergraph in which every two hyperedges intersect. Every finite projective plane is $r$ -uniform for some integer $r$ . Denote by $H r$ the $r$ -uniform projective plane. The following projective planes are known to exist:

$H 2$ : it is simply a triangle graph.
$H 3$ : it is the Fano plane.
$H p +1$ exists whenever $p$ is the power of a prime number.

When $H r$ exists, it has the following properties:^[8]

It has $r 2 - r + 1$ vertices and $r 2 - r + 1$ hyperedges.
It is $r$ -uniform - each hyperedge contains exactly $r$ vertices.
It is $r$ -regular - each vertex is contained in exactly $r$ hyperedges.
$τ (H r) = r$ : the $r$ vertices in each hyperedge $e$ are a vertex-cover of $H r$ (since every other hyperedge intersects $e$ ).
The only transversals of size $r$ are the hyperedges; all other transversals have size at least $r + 2$ .
$τ*(Hr) = ν*(H) = r – 1 + .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠1/r⁠$ .
$ν (H r) = 1$ : every matching in $H r$ contains at most a single hyperedge.

Minimal transversals

A vertex-cover (transversal) $T$ is called minimal if no proper subset of $T$ is a transversal.

The transversal hypergraph of $H$ is the hypergraph $(X, F)$ whose hyperedge set $F$ consists of all minimal-transversals of $H$ .

Computing the transversal hypergraph has applications in combinatorial optimization, in game theory, and in several fields of computer science such as machine learning, indexing of databases, the satisfiability problem, data mining, and computer program optimization.

References

^ ^a ^b Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549
^ Berge, Claude (1973). Graphs and Hypergraphs. Amsterdam: North-Holland.
^ Khot, Subhash; Regev, Oded (2008). "Vertex cover might be hard to approximate to within 2−ε". Journal of Computer and System Sciences. 74 (3): 335–349. doi:10.1016/j.jcss.2007.06.019.
^ Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer. ISBN 978-3-540-29952-3. Retrieved 2010-03-05.
^ O'Callahan, Robert; Choi, Jong-Deok (2003). "Hybrid dynamic data race detection". ACM SIGPLAN Notices. 38 (10): 167–178. doi:10.1145/966049.781528.
^ O'Callahan, Robert; Choi, Jong-Deok (2003). "Hybrid dynamic data race detection". Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming. pp. 167–178. doi:10.1145/781498.781528. ISBN 1-58113-588-2.
^ L. Lovász (1975). "On the ratio of optimal integral and fractional covers". Discrete Mathematics. 13 (4): 383–390. doi:10.1016/0012-365X(75)90058-8. ISSN 0012-365X. Zbl 0323.05127. Wikidata Q56391140.
^ Füredi, Zoltán (1981-06-01). "Maximum degree and fractional matchings in uniform hypergraphs". Combinatorica. 1 (2): 155–162. doi:10.1007/BF02579271. ISSN 1439-6912. S2CID 10530732.

[lp2-1] Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549

[2] Berge, Claude (1973). Graphs and Hypergraphs. Amsterdam: North-Holland.

[kr08-3] Khot, Subhash; Regev, Oded (2008). "Vertex cover might be hard to approximate to within 2−ε". Journal of Computer and System Sciences. 74 (3): 335–349. doi:10.1016/j.jcss.2007.06.019.

[4] Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer. ISBN 978-3-540-29952-3. Retrieved 2010-03-05.

[5] O'Callahan, Robert; Choi, Jong-Deok (2003). "Hybrid dynamic data race detection". ACM SIGPLAN Notices. 38 (10): 167–178. doi:10.1145/966049.781528.

[6] O'Callahan, Robert; Choi, Jong-Deok (2003). "Hybrid dynamic data race detection". Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming. pp. 167–178. doi:10.1145/781498.781528. ISBN 1-58113-588-2.

[7] L. Lovász (1975). "On the ratio of optimal integral and fractional covers". Discrete Mathematics. 13 (4): 383–390. doi:10.1016/0012-365X(75)90058-8. ISSN 0012-365X. Zbl 0323.05127. Wikidata Q56391140.

[:2-8] Füredi, Zoltán (1981-06-01). "Maximum degree and fractional matchings in uniform hypergraphs". Combinatorica. 1 (2): 155–162. doi:10.1007/BF02579271. ISSN 1439-6912. S2CID 10530732.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]