# Enumeration of minimal transversals of hypergraphs of bounded VC-dimension

Arnaud Mary

<figure><img src="image_1.png" /></figure>

To cite this version:

Arnaud Mary. Enumeration of minimal transversals of hypergraphs of bounded VC-dimension. 2024. hal-04886143

HAL Id: hal-04886143

https://hal.science/hal-04886143v1

Preprint submitted on 14 Jan 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Enumeration of minimal transversals of hypergraphs of bounded VC-dimension

A. Mary

December 18, 2024

## Abstract

We consider the problem of enumerating all minimal transversals (also called minimal hitting sets) of a hypergraph $\mathcal{H}$. An equivalent formulation of this problem known as the *transversal hypergraph problem* (or *hypergraph dualization problem*) is to decide, given two hypergraphs, whether one corresponds to the set of minimal transversals of the other. The existence of a polynomial time algorithm to solve this problem is a long standing open question. In [16], the authors present the first sub-exponential algorithm to solve the transversal hypergraph problem which runs in quasi-polynomial time, making it unlikely that the problem is (co)NP-complete.

In this paper, we show that when one of the two hypergraphs is of bounded VC-dimension, the transversal hypergraph problem can be solved in polynomial time, or equivalently that if $\mathcal{H}$ is a hypergraph of bounded VC-dimension, then there exists an incremental polynomial time algorithm to enumerate its minimal transversals. This result generalizes most of the previously known polynomial cases in the literature since they almost all consider classes of hypergraphs of bounded VC-dimension. As a consequence, the hypergraph transversal problem is solvable in polynomial time for any class of hypergraphs closed under partial subhypergraphs. We also show that the proposed algorithm runs in quasi-polynomial time in general hypergraphs and runs in polynomial time if the conformality of the hypergraph is bounded, which is one of the few known polynomial cases where the VC-dimension is unbounded.

## 1 Introduction

A hypergraph $\mathcal{H}$ is a couple $(V(\mathcal{H}), \mathcal{E}(\mathcal{H}))$ where $V(\mathcal{H})$ is a finite set called the vertices and $\mathcal{E}(\mathcal{H}) \subseteq 2^{V(\mathcal{H})}$ is a family of subsets of $V(\mathcal{H})$ called the hyperedges of the hypergraph. By abuse of notation, we often treat a hypergraph as its set of hyperedges when the set of vertices is clear from the context, and we say that a set of vertices $X$ belongs to $\mathcal{H}$ if $X$ is a hyperedge of $\mathcal{H}$. A set $U \subseteq V(\mathcal{H})$ is called a transversal (or a hitting set) of $\mathcal{H}$ if $U \cap F \neq \emptyset$ for all $F \in \mathcal{E}(\mathcal{H})$. A transversal $U$ is said to be minimal if it does not contains any other transversal. The set of minimal transversals of $\mathcal{H}$ forms another hypergraph on the same
vertex set denoted by $\mathrm{Tr}(\mathcal{H})$ and referred to as the *transversal hypergraph* or
the *dual hypergraph* of $\mathcal{H}$ [1]. In this paper we are interested in the problem of
finding $\mathrm{Tr}(\mathcal{H})$ given $\mathcal{H}$.

TRANS-ENUM

**Input**: A hypergraph $\mathcal{H}$.

**Output**: All minimal transversals of $\mathcal{H}$, i.e. $\mathrm{Tr}(\mathcal{H})$.

Since $\mathrm{Tr}(\mathcal{H})$ could be exponentially larger than $\mathcal{H}$, this problem falls into
the category of enumeration problems. To measure the complexity of algo-
rithms that solving this kind of problems, we usually take into account both
the input size (the size of $\mathcal{H}$) and the output size (the size of $\mathrm{Tr}(\mathcal{H})$). With
this paradigm (called the *output-sensitive approach*), an algorithm is said to
be *output-polynomial* if its running time is a polynomial in $|\mathcal{H}|$ and $|\mathrm{Tr}(\mathcal{H})|$.
We say that an algorithm runs in *incremental polynomial time*, if it can find $\ell$
minimal transversals in time polynomial in $\mathcal{H}$ and $k$. The problem admits an
incremental polynomial time algorithm if and only if the following problem can
be solved in polynomial time (in a classical sense):

TRANS-HYP

**Input**: Two hypergraphs $\mathcal{H}$ and $\mathcal{G}$ on the same vertex set $V$ with $\mathcal{G} \subseteq \mathrm{Tr}(\mathcal{H})$.

**Output**: Either answer that $\mathcal{G} = \mathrm{Tr}(\mathcal{H})$ or find $T \in \mathrm{Tr}(\mathcal{H}) \setminus \mathcal{G}$

We assume throughout the paper that $\mathcal{H}$ is Sperner i.e. no hyperedge of
$\mathcal{H}$ contains another hyperedge. This assumption can be made without loss of
generality since otherwise $\mathcal{H}$ has the same minimal transversals as the restriction
to its inclusion-wise minimal hyperedges. For Sperner hypergraphs, it is well
known that $\mathcal{H}$ and $\mathrm{Tr}(\mathcal{H})$ forms a duality relationship in the sense that $\mathrm{Tr}(\mathcal{H}) =
\mathcal{G}$ if and only if $\mathrm{Tr}(\mathcal{G}) = \mathcal{H}$ [1]. TRANS-HYP problem corresponds to decide
whether two hypergraphs are dual, and to find a counter-example otherwise. It
has been shown in [2] that the simple decision version of this problem (without
requiring a counter-example) is equivalent.

TRANS-HYP problem has been extensively studied, due to its equivalence
to many other important problems (see e.g. [2, 7, 9, 12, 17, 18, 14, 21]). It is
a long standing open question to decide whether TRANS-HYP can be solved in
polynomial time. The best known algorithms to solve it runs in quasi-polynomial
time $nN^{o(\log N)}$ where $N = |\mathcal{H}| + |\mathcal{G}|$ and $n = |V(\mathcal{H})|$ [16]. The problem is
then very unlikely to be NP-hard. The VC-dimension of a hypergraph was
introduced in [22] and has been shown to be a important parameter for many
different applications. Given a class of hypergraph $\mathcal{H}$, the TRANS-HYP problem
restricted to $\mathcal{H}$ consists in all instances $(\mathcal{H}, \mathcal{G})$ of TRANS-HYP such that at least
one of $\mathcal{H}$ or $\mathcal{G}$ belongs to $\mathcal{H}$. The main result of this paper is that TRANS-HYP
can be solved in polynomial time in hypergraphs of bounded VC-dimension,
or equivalently, that TRANS-ENUM can be solved in incremental polynomial
time for hypergraphs of bounded VC-dimension. This answer an open question
proposed in [10].
**Theorem 1.** Let $\mathcal{H}$ be a hypergraph with VC-DIM($\mathcal{H}$) < k and let $\mathcal{G} \subseteq \text{Tr}(\mathcal{H})$. One can decide in time $O(2^k(n|\mathcal{G}|)^{k+1} + n^{2k+1}|\mathcal{G}|)$ whether $\mathcal{G} = \text{Tr}(\mathcal{H})$ and find $T \in \text{Tr}(\mathcal{H}) \setminus \mathcal{G}$ otherwise.

Many different polynomial time algorithms for TRANS-HYP have been designed for special classes of hypergraphs in the literature. While more efficient algorithms are generally presented, Theorem 1 generalizes many of those results since we observe that considered classes often have bounded VC-dimension. Among the already known polynomial cases directly covered by Theorem 1 we can cite:

* bounded hyperedge size, bounded edge-intersections, $\beta$-acyclic [6, 4, 18, 3]

* $\delta$-sparse hypergraphs, bounded degree, bounded tree-width, tatally unimodular hypergraphs [19, 20, 8, 11]

* Several geometrically defined hypergraphs: axis-parallel hyper-rectangles, half-spaces, axis-parallel hyperplanes, balls, polytopes with fixed number of facets/vertices [12, 14, 15]

We observe that all those classes are closed under partial subhypergraphs. A partial subhypergraph of a hypergraph $\mathcal{H}$ is a hypergraph obtained from $\mathcal{H}$ by selecting a subset of hyperedges $\mathcal{E}' \subseteq \mathcal{E}(\mathcal{H})$, a subset of vertices $V' \subseteq V(\mathcal{H})$ and considering the hyperedges of $\mathcal{E}'$ restricted to $V'$, i.e. the hypergraph $(V', \{F \cap V' | F \in \mathcal{E}'\})$. As an important corollary of Theorem 1 we obtain the following.

**Corollary 2.** TRANS-HYP can be solved in polynomial time in any proper class of hypergraphs closed under partial subhypergraph.

One of the most general class for which we already know that TRANS-HYP is solvable in polynomial time and which is not covered by Theorem 1 is the class of $k$-conformal hypergraphs [18]. While this class is not closed under partial subhypergraph and does not have a bounded VC-dimension we show that the algorithm developed in this paper runs also in polynomial time if the hypergraph is $k$-conformal. Up to our knowledge the two main cases for which the polynomiality cannot be directly deduced from the results present in this paper are the class of $k$-degenerate hypergraphs [8] and the class of $r$-exact hypergraphs [13].

# 2 Preliminaries

A trace on $V := V(\mathcal{H})$ is a couple $(T, S)$ with $S \subseteq V$, and $T \subseteq S$. The size of trace $(T, S)$ is defined as $|S|$ and it is called a $k$-trace if $|S| = k$. We say that a subset $F \subseteq V$ realizes a trace $(T, S)$ if $F \cap S = T$ and we denote by traces$_k(F, V)$ the set of $k$-traces realized by $F$ on $V$. When the set $V$ is clear from the context, we will simply use traces$_k(F)$ instead of traces$_k(F, V)$ For a hypergraph $\mathcal{H}$ we
denote by traces$_k(H) := \bigcup_{F \in \mathcal{H}} \text{traces}_k(F, V(H))$ the set of traces realized by its
hyperedges. In other words, a k-trace $(T, S)$ belongs to traces$_k(H)$ if there exists
a hyperedge $F \in \mathcal{H}$ such that $F \cap S = T$. A subset $E \subseteq V(H)$ is k-compatible
with $\mathcal{H}$ if traces$_k(E) \subseteq \text{traces}_k(\mathcal{H})$ i.e. for each k-subset $S \subseteq V(H)$ there exists
$F \in \mathcal{H}$ such that $E \cap S = F \cap S$. Given a hypergraph $\mathcal{H}$ and $k \le |V(H)|$,
the k-extension of $\mathcal{H}$, $\text{ext}_k(\mathcal{H})$ is the hypergraph on $V(H)$ whose hyperedges
are all subsets of $V$ k-compatible with $\mathcal{H}$, i.e. $\text{ext}_k(\mathcal{H}) := (V(\mathcal{H}), \{E \mid E \subseteq V, \text{traces}_k(E) \subseteq \text{traces}_k(\mathcal{H})\})$. Since in particular every hyperedge of $\mathcal{H}$ is k-
compatible with $\mathcal{H}$, $\mathcal{H} \subseteq \text{ext}_k(\mathcal{H})$.

A subset of vertices $U \subseteq V(\mathcal{H})$ is shattered in $\mathcal{H}$ if for all $U' \subseteq U$, there exists $F \in \mathcal{H}$ such that $F \cap U = U'$ i.e. if $(U', U) \in \text{traces}_{|U|}(\mathcal{H})$ for all $U' \subseteq U$. The VC-dimension of $\mathcal{H}$, VC-DIM($\mathcal{H}$), is the size of its largest shattered set. Using the trace definition, VC-DIM($\mathcal{H}$) < $k$ if for all $k$-subsets $S$ of $V$ there exists $T \subseteq S$ such that $(T, S) \notin \text{traces}_k(\mathcal{H})$. One of the most important property of hypergraphs of bounded dimension is given by the Sauer-Shelah Lemma.

**Lemma 3** (Sauer–Shelah Lemma). *If $\mathcal{H}$ is of VC-dimension strictly less than $k$, then $|\mathcal{H}| = O(|V|^k)$*

**Corollary 4.** *If $\mathcal{H}$ is of VC-dimension strictly less than $k$ then $|\mathrm{ext}_k(\mathcal{H})| = O(|V|^k)$*

*Proof.* Since by definition, $\mathrm{ext}_k(\mathcal{H})$ has exactly the same $k$-traces than $\mathcal{H}$ a subset of vertices of size $k$ is shattered in $\mathrm{ext}_k(\mathcal{H})$ if and only if it is shattered in $\mathcal{H}$. Since $\mathcal{H}$ shatters no subset of size $k$, VC-DIM($\mathrm{ext}_k(\mathcal{H})$) < $k$. The result follows from Lemma 3. $\square$

Given a hypergraph $\mathcal{H}$ and a subset of hyperedges $\mathcal{E}' \subseteq \mathcal{H}$, the hypergraph $(\bigcup_{F \in \mathcal{E}'} F, \mathcal{E}')$ is called the *partial hypergraph* of $\mathcal{H}$ induced by $\mathcal{E}'$. Given a subset of vertices $V' \subseteq V(\mathcal{H})$ the hypergraph $(V', \{F \cap V' \mid F \in \mathcal{H}, F \cap V' \neq \emptyset\})$ is the *subhypergraph* induced by $V'$. Given $V' \subseteq V$ and $\mathcal{E}' \subseteq \mathcal{H}$ the *partial subhypergraph* induced by $V'$ and $\mathcal{E}'$ is the hypergraph $(V', \{F \cap V' \mid F \in \mathcal{E}', F \cap V' \neq \emptyset\})$. A partial subhypergraph of $\mathcal{H}$ that does not contain isolated vertices (i.e. vertices that do not belong to any hyperedge) is a partial hypergraph of a subhypergraph of $\mathcal{H}$ or equivalently a subhypergraph of a partial hypergraph of $\mathcal{H}$.

**3 Main algorithm**

In this section we assume that we are given a hypergraph $\mathcal{H}$ with VC-DIM($\mathcal{H}$) < $k$ and a hypergraph $\mathcal{G} \subseteq \text{Tr}(\mathcal{H})$. We want to decide whether $\text{Tr}(\mathcal{H}) = \mathcal{G}$ or equivalently whether $\mathcal{G} = \text{Tr}(\mathcal{H})$ and find a new minimal transversal in $\text{Tr}(\mathcal{H}) \setminus \mathcal{G}$ otherwise. We present Algorithm 1 to solve this problem whose running time is $O(2^k(n|\mathcal{G}|)^{k+1} + n^{2k+1}|\mathcal{G}|)$ as stated by Theorem 1.

Notice that we can assume that $\mathcal{H} \subseteq \text{Tr}(\mathcal{G})$ since otherwise the answer is no, and we can easily find a new minimal transversal $\text{Tr}(\mathcal{H}) \setminus \mathcal{G}$. Indeed assume
that there exists $E \in \mathcal{F}$ such that $E$ is not a minimal transversal of $\mathcal{G}$, i.e. there exists $x \in E$ such that $E \setminus \{x\}$ is also a transversal of $\mathcal{G}$, then any minimal transversal of $\mathcal{H}$ included in $(V \setminus E) \cup \{x\}$ belongs to $\mathrm{Tr}(\mathcal{H}) \setminus \mathcal{G}$.

The algorithm will actually either answer that $\mathrm{Tr}(\mathcal{G}) = \mathcal{H}$ or find a new minimal transversal $T \in \mathrm{Tr}(\mathcal{G}) \setminus \mathcal{H}$ otherwise. In the latter case, given $T$, one can easily find a new minimal transversal of $\mathrm{Tr}(\mathcal{H}) \setminus \mathcal{G}$. Indeed it is enough to output any minimal transversal of $\mathcal{H}$ included in $V \setminus T$.

We are trying to find $T \in \mathrm{Tr}(\mathcal{G})$ such that $T \notin \mathcal{H}$. The main strategy is based on the observation that if such a $T$ exists, then either $T$ is $k$-compatible with $\mathcal{H}$ (i.e. $T \in \mathrm{ext}_k(\mathcal{H})$) or it realizes a $k$-trace that is not in $\mathrm{traces}_k(\mathcal{H})$. It is easy to check whether there exists a $T$ which satisfy the later case in general hypergraphs, and we show that the former case can be checked in polynomial time when $\mathrm{VC-DIM}(\mathcal{H}) < k$. The strategy is summarized in Algorithm 1.

<table><caption>**Algorithm 1:** Dualize</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>input</td><td>: Two hypergraphs $\mathcal{H}$ and $\mathcal{G}$ and $k \in \mathbb{N}$<br>output: Yes if $\mathrm{Tr}(\mathcal{G}) = \mathcal{H}$ or $E \in \mathrm{Tr}(\mathcal{G}) \setminus \mathcal{H}$ otherwise</td></tr><tr><td>1</td><td>begin</td></tr><tr><td>2</td><td>2</td></tr><tr><td>3</td><td>3</td></tr><tr><td>4</td><td>4</td></tr><tr><td>5</td><td>5</td></tr><tr><td>6</td><td>6</td></tr><tr><td>7</td><td>7</td></tr><tr><td>8</td><td>8</td></tr></tbody></table>

The first loop of Algorithm 1 try to find a minimal transversal $E \in \mathrm{Tr}(\mathcal{G}) \setminus \mathrm{ext}_k(\mathcal{H})$ i.e. a minimal transversal of $\mathcal{G}$ which realizes a $k$-trace $(T, S) \notin \mathrm{traces}_k(\mathcal{H})$. To do so we simply go over all $k$-traces that are not in $\mathrm{traces}_k(\mathcal{H})$ and check for each one whether it is realizable by a minimal transversal of $\mathcal{G}$. There are at most $2^k(|V|)$ such $k$-traces and we will show in Corollary 8 that we can check in polynomial time whether a $k$-trace is realizable by a minimal transversal of $\mathcal{G}$.

The second loop of Algorithm 1 try to find a minimal transversal of $\mathcal{G}$ which is $k$-compatible with $\mathcal{H}$ and that does not belong to $\mathcal{H}$. For this, we first generate $\mathrm{ext}_k(\mathcal{H})$ from $\mathcal{H}$ and we try every possible hyperedge of $\mathrm{ext}_k(\mathcal{H})$ that is not included in a hyperedge of $\mathcal{H}$. In general the size of $\mathrm{ext}_k(\mathcal{H})$ may be exponentially larger than the size of $\mathcal{H}$, but we prove in Proposition 11 that when $\mathrm{VC-DIM}(\mathcal{H}) < k$, its size is polynomial and we can compute it in polynomial time.

To check the condition on line 3, we need to test whether $\mathcal{G}$ has a minimal transversal containing $T$ and excluding $S \setminus T$ which can be done in polynomial time.
time when $T$ is of bounded size as we will see in section 3.1. The remaining part is to compute $\mathrm{ext}_k(\mathcal{H})$. We will see in section 3.2 that this can be done in polynomial time whenever $\mathrm{VC-DIM}(\mathcal{H})$ is bounded.

**Theorem 5.** For any $k \in \mathbb{N}$, Algorithm 1 correctly returns "Yes" if $\mathrm{Tr}(\mathcal{G}) = \mathcal{H}$ and a set $E \in \mathrm{Tr}(\mathcal{G}) \setminus \mathcal{H}$ otherwise.

*Proof.* Let us show first that if a set $E$ is returned by the algorithm, then $E \in \mathrm{Tr}(\mathcal{G}) \setminus \mathcal{H}$.

Assume first that $E$ is returned in line 4, i.e. that the condition in line 3 is true. The condition imposes that $E \in \mathrm{Tr}(\mathcal{G})$ and since $E$ realizes a $k$-trace $(T, S)$ that does not belong to $\mathrm{traces}_k(\mathcal{H})$, $E$ cannot belong to $\mathcal{H}$ since otherwise all $k$-traces realized by $E$ would belong to $\mathrm{traces}_k(\mathcal{H})$. So $E \in \mathrm{Tr}(\mathcal{G}) \setminus \mathcal{H}$. Suppose now that $E$ is returned in line 7. Notice that we impose in line 5 that $E$ is contained in no hyperedge of $\mathcal{H}$. In particular, $E$ cannot belong to $\mathcal{H}$. Together with the condition in line 6, $E$ is returned in line 7 only if $E \in \mathrm{Tr}(\mathcal{G}) \setminus \mathcal{H}$. So if $\mathrm{Tr}(\mathcal{G}) = \mathcal{H}$ then the algorithm answer "Yes" since otherwise it would return a set $E \in \mathrm{Tr}(\mathcal{G}) \setminus \mathcal{H}$.

Assume now that the algorithm answer "Yes" and let us show that $\mathrm{Tr}(\mathcal{H}) = \mathcal{H}$. Assume for contradiction that there exists $E \in \mathrm{Tr}(\mathcal{G}) \setminus \mathcal{H}$. If $\mathrm{traces}_k(E) \subseteq \mathrm{traces}_k(\mathcal{H})$ then $E \in \mathrm{ext}_k(\mathcal{H})$ and then, $E$ would be returned in the loop in line 5. Otherwise there is a $k$-trace $(T, S) \in \mathrm{traces}_k(E) \setminus \mathrm{traces}_k(\mathcal{H})$. But then, $E$ would be a minimal transversal of $\mathcal{G}$ which realizes a trace $(T, S) \notin \mathrm{traces}_k(\mathcal{H})$ and such a minimal transversal of $\mathcal{G}$ would be returned in line 4. Notice that it wouldn't be necessarily $E$ that would be returned, but any $E' \in \mathrm{Tr}(\mathcal{G})$ that realizes $(T, S)$. $\square$

**3.1 Finding a minimal transversal satisfying a $k$-trace**

In this section, we show that the condition in line 3 of Algorithm 1 can be check in polynomial time. More precisely, given a $k$-trace $(T, S)$ we show that we can check in time $O(n|\mathcal{G}|^{|T|+1})$ whether there exists a minimal transversal of $\mathcal{G}$ realizing $(T, S)$. When $k$ is a constant, $T$ is of constant size and the above mentioned complexity is polynomial. To do so, we reduce the problem to deciding whether $T$ is a sub-transversal in a subhypergraph of $\mathcal{G}$. A set of vertices $T$ is a sub-transversal of $\mathcal{H}$ if there exists a minimal transversal $E \in \mathrm{Tr}(\mathcal{H})$ such that $T \subseteq E$. In [5], the authors proved that one can check in polynomial time whether a subset of vertices $T$ of bounded size is a sub-transversal.

**Lemma 6.** [5] Given a subset of vertices, $T$ one can check in time $O(n|\mathcal{H}|^{|T|+1})$ whether $T$ is a sub-transversal of $\mathcal{H}$.

**Lemma 7.** Let $(T, S)$ be a $k$-trace on $V$ and let $V' := V \setminus (S \setminus T)$. Then, there exists a minimal transversal of $\mathcal{G}$ realizing $(T, S)$ if and only if $T$ is sub-transversal of the subhypergraph $\mathcal{G}' = (V', \{F \cap V' \mid F \in \mathcal{G}\})$

*Proof.* Observe first that $E \in \mathrm{Tr}(\mathcal{G}')$ if and only if $E$ is a minimal transversal of $\mathcal{G}$ such that $E \subseteq V'$. Assume first that $T$ is a sub-transversal of $\mathcal{G}'$. There
exists $E \in \mathrm{Tr}(\mathcal{G}')$ such that $T \subseteq E$. Since $E$ is a minimal transversal of $\mathcal{G}'$ it is a also a minimal transversal of $\mathcal{G}$. Now since $E \subseteq V'$ and $V' \cap S = T$ we have $E \cap S = T$ and so $E$ realizes $(T, S)$. Assume now that there exists $E \in \mathrm{Tr}(\mathcal{G})$ such that $E$ realizes $(T, S)$. We have $E \cap S = T$ and so $E$ is included in $V'$. Therefore, $E$ is a minimal transversal of $\mathcal{G}'$ containing $T$. $\square$

**Corollary 8.** *Given a k-trace $(T, S)$ on can check in time $O(n|\mathcal{G}|^{|T|+1})$ whether there exists a minimal transversal $E$ of $\mathcal{G}$ realizing $(T, S)$.*

## 3.2 Computing $\mathrm{ext}_k(\mathcal{H})$

In this section we show that when $\mathrm{VC-DIM}(\mathcal{H}) < k$, $\mathrm{ext}_k(\mathcal{H})$ can be computed in time $O(n^{2k})$

For $i \le n$, let us denote by $V_i$ the set $v_1, \dots, v_i$ and let $\mathcal{H}_i$ be the hypergraph $(V_i, \{F \cap V_i \mid F \in \mathcal{H}\})$. We iteratively build $\mathrm{ext}_k(\mathcal{H}_i)$ from $\mathrm{ext}_k(\mathcal{H}_{i-1})$. For each $E \in \mathrm{ext}_k(\mathcal{H}_{i-1})$ we check whether $E$ and $E \cup \{v_i\}$ violates a k-trace traces$_k(\mathcal{H}_i)$.

**Lemma 9.** $\mathrm{ext}_k(\mathcal{H}_k) = \mathcal{H}_k$

*Proof.* As notices previously for any hypergraph $\mathcal{H}$, $\mathcal{H} \subseteq \mathrm{ext}_k(\mathcal{H})$ so $\mathcal{H}_k \subseteq \mathrm{ext}_k(\mathcal{H}_k)$. So let us show that $\mathrm{ext}_k(\mathcal{H}_k) \subseteq \mathcal{H}_k$. Let $E \in \mathrm{ext}_k(\mathcal{H}_k)$. Since $|V_k| = k$ the only k-traces realized by $E$ on $V_k$ is the k-trace $(E \cap V_k, V_k)$. Now since $E \in \mathrm{ext}_k(\mathcal{H}_k)$, there exists a hyperedge $F \in \mathcal{H}_k$ which realizes the k-trace $(E \cap V_k, V_k)$, i.e such that $F \cap V_k = E \cap V_k$. But since both $F \subseteq V_k$ and $E \subseteq V_k$, we have $F = E$, i.e. $E$ is a hyperedge of $\mathcal{H}_k$. $\square$

**Lemma 10.** Let $k < i \le n$ and let $E \in \mathrm{ext}_k(\mathcal{H}_i)$, then $E \setminus \{v_i\} \in \mathrm{ext}_k(\mathcal{H}_{i-1})$.

*Proof.* Let $E' := E \setminus \{v_i\}$. Let us show that traces$_k(E', V_{i-1}) \subseteq traces_k(\mathcal{H}_{i-1})$. Let $S \subseteq V_{i-1}$ with $|S| = k$. Since $E \in \mathrm{ext}_k(\mathcal{H}_i)$ there exists $F \in \mathcal{H}_i$ such that $E \cap S = F \cap S$. Let $F' := F \setminus \{v_i\}$. Since $v_i \notin S$, $E' \cap S = F' \cap S$. Since $F$ is a hyperedge of $\mathcal{H}_i$, $F'$ is a hyperedge of $\mathcal{H}_{i-1}$ and so the trace $(E' \cap S, S) = (F' \cap S, S) \in \mathrm{traces}_k(\mathcal{H}_{i-1}, V_{i-1}))$. $\square$

**Proposition 11.** If $\mathrm{VC-DIM}(\mathcal{H}) < k$ then $\mathrm{ext}_k(\mathcal{H})$ can be computed in time $O(n^{2k})$

*Proof.* To compute $\mathrm{ext}_k(\mathcal{H})$ we iteratively compute $\mathrm{ext}_k(\mathcal{H}_i)$ from $\mathrm{ext}_k(\mathcal{H}_{i-1})$ starting by $\mathrm{ext}_k(\mathcal{H}_k) = \mathcal{H}_k$ up to $\mathrm{ext}_k(\mathcal{H}_n) = \mathrm{ext}_k(\mathcal{H})$. By Lemma 9 we start from $\mathcal{H}_k$. Then for each $k < i \le n$ we compute $\mathrm{ext}_k(\mathcal{H}_i)$ from $\mathrm{ext}_k(\mathcal{H}_{i-1})$ in the following way :

For each $E \in \mathrm{ext}_k(\mathcal{H}_{i-1})$ Do:

Add $E$ to $\mathrm{ext}_k(\mathcal{H}_i)$ if traces$_k(E, V_i) \subseteq traces_k(\mathcal{H}_i)$

Add $E' := E \cup \{v_i\}$ to $\mathrm{ext}_k(\mathcal{H}_i)$ if traces$_k(E', V_i) \subseteq traces_k(\mathcal{H}_i)$.

By Lemma 10 each hyperedge of $\mathrm{ext}_k(\mathcal{H}_i)$ is found by the above procedure. Now observe that for any $i \le n$, the hypergraph $\mathcal{H}_i$ is a subhypergraph of $\mathcal{H}$ and
so VC-DIM($\mathcal{H}_i$) $\le$ VC-DIM($\mathcal{H}$) < $k$. So, by Corollary 4, $|\text{ext}_k(\mathcal{H}_i)| = O(i^k) = O(n^k)$. Now, for a given $E \in \text{ext}_k(\mathcal{H}_{i-1})$ we need to check whether $E$ (resp. $E' := E \cup \{v_i\}$) belong to $\text{ext}_k(\mathcal{H}_i)$ i.e whether traces$_k(E, V_i) \subseteq \text{traces}_k(\mathcal{H}_i)$ (resp. traces$_k(E', V_i) \subseteq \text{traces}_k(\mathcal{H}_i)$). We claim that this can be checked in time $O((i-1)^{k-1}) = O(n^{k-1})$. Let $S$ be such that $v_i \notin S$. Since $S \subseteq V_{i-1}$ and since $E \in \text{ext}_k(\mathcal{H}_{i-1})$, there exists $F \in \mathcal{H}_{i-1}$ such that $E \cap S = F \cap S$. Now there exists $F' \in \mathcal{H}_i$ such that $F = F' \setminus \{v_i\}$ and since $v_i \notin S$, we have $F' \cap S = F \cap S = E \cap S = E' \cap S$. So the $k$-trace $(E \cap S, S) \in \text{traces}_k(\mathcal{H}_i)$ (resp. $(E' \cap S, S) \in \text{traces}_k(\mathcal{H}_i)$). So if $E$ (resp. $E'$) realizes a trace $(E \cap S, S) \notin \text{traces}_k(\mathcal{H}_i)$ (resp. $(E' \cap S, S) \notin \text{traces}_k(\mathcal{H}_i)$), $S$ must contain $v_i$. Therefore, to check whether traces$_k(E, V_i) \subseteq \text{traces}_k(\mathcal{H}_i)$ (resp. traces$_k(E', V_i) \subseteq \text{traces}_k(\mathcal{H}_i))$ we only have to check for each of the $O((i-1)^{k-1})$ subsets $S$ of $V_i$ of size $k$ that contain $v_i$, whether $(E \cap S, S) \in \text{traces}_k(\mathcal{H}_i)$.

Hence, $\text{ext}_k(\mathcal{H}_i)$ is computed in $O(n^{2k-1})$ since we check for each of the $O(n^k)$ hyperedge $E$ of $\text{ext}_k(\mathcal{H}_{i-1})$ whether $E$ and $E'$ belong to $\text{ext}_k(\mathcal{H}_i)$ which can be done in $O(n^{k-1})$. So in total $\text{ext}_k(\mathcal{H})$ can be computed in time $O(n \times n^{2k-1}) = O(n^{2k})$.

□

We are now ready to prove Theorem 1

**Theorem 1.** Let $\mathcal{H}$ be a hypergraph with VC-DIM($\mathcal{H}$) < $k$ and let $\mathcal{G} \subseteq \text{Tr}(\mathcal{H})$. One can decide in time $O(2^k(n|\mathcal{G}|)^{k+1} + n^{2k+1}|\mathcal{G}|)$ whether $\mathcal{G} = \text{Tr}(\mathcal{H})$ and find $T \in \text{Tr}(\mathcal{H}) \setminus \mathcal{G}$ otherwise.

*Proof.* From Theorem 5 Algorithm 1 returns "Yes" if and only if $\text{Tr}(\mathcal{G}) = \mathcal{H}$ and $E \in \text{Tr}(\mathcal{G}) \setminus \mathcal{H}$ otherwise. By the duality property, the algorithm returns "Yes" if and only if $\text{Tr}(\mathcal{H}) = \mathcal{G}$. Assume now that the algorithm returns an element $E \in \text{Tr}(\mathcal{G}) \setminus \mathcal{H}$. Since we assumed that all hyperedges of $\mathcal{H}$ are transversals of $\mathcal{G}$, $E$ does not contain any hyperedge of $\mathcal{H}$ and thus $V \setminus E$ is a transversal of $\mathcal{H}$. Observe furthermore that $V \setminus E$ contains no hyperedge of $\mathcal{G}$ since otherwise $E$ would not be a transversal of $\mathcal{G}$. So to output a minimal transversal $E' \in \text{Tr}(\mathcal{H}) \setminus \mathcal{G}$ it is enough to compute any minimal transversal of $\mathcal{H}$ contained in $V \setminus E$ which can be done in $O(n|\mathcal{H}|)$. Let us show now that Algorithm 1 runs with the announced complexity. The for loop in line 2 goes over all $k$-traces $(T, S) \notin \text{traces}_k(\mathcal{H})$. There is at most $O(2^k n^k)$ such traces and for each $k$-trace the condition in line 3 can be checked in time $O(n|\mathcal{G}|^{k+1})$ by Corollary 8. So the first for loop take in total $O(2^k(n|\mathcal{G}|)^{k+1})$.

For the second loop, by Lemma 11, we can compute $\text{ext}_k(\mathcal{H})$ in time $O(n^{2k})$. Since for each $E \in \text{ext}_k(\mathcal{H})$ one can check whether $E \in \text{Tr}(\mathcal{G})$ in time $O(n|\mathcal{G}|)$ the total time taken by the for loop in line 2 is $O(n^{2k+1}|\mathcal{G}|)$.

□

## 3.3 Consequences

The first immediate consequence of Theorem 1 is obtained when the VC-dimension is bounded, i.e. when $k$ is a constant.
**Corollary 12.** *TRANS-HYP problem is solvable in polynomial time in hypergraph classes of bounded VC-dimension.*

Even if several quasi-polynomial time algorithms are already known for general hypergraphs, we observe Algorithm 1 runs also in quasi-polynomial time.

**Corollary 13.** *Algorithm 1 runs in time $(n|\mathcal{G}|)^{O(\log(\mathcal{H}))}$.*

*Proof.* Notice that if a set of size $k$ is shattered by $\mathcal{H}$, then $\mathcal{H}$ contains at least $2^k$ hyperedges, and so we have $\text{VC-DIM}(\mathcal{H}) = O(\log(\mathcal{H}))$. So by Theorem 1, we obtain the result. □

Another important property of Algorithm 1 is that it runs in polynomial time on hypergraphs of bounded conformality. The conformality of hypergraph was introduced in [1], a hypergraph $\mathcal{H}$ is said to be $k$-conformal if any minimal subset of vertices that is not included in any hyperedge of $\mathcal{H}$ is of size at most $k$. In [18], the authors prove that TRANS-HYP is solvable in polynomial time in $k$-conformal hypergraphs. Although $k$-conformal hypergraphs can have arbitrarily large VC-dimension, Algorithm 1 runs in polynomial time for hypergraphs of bounded conformality. In the proof of Theorem 1 the VC-dimension is used to bound the size $\text{ext}_k(\mathcal{H})$ and to be able to compute it in polynomial time. The following proposition assert that if $\mathcal{H}$ is $k$-conformal, then any hyperedge of $\text{ext}_k(\mathcal{H})$ is a subset of an hyperedge of $\mathcal{H}$. Hence, even though the size of $\text{ext}_k(\mathcal{H})$ may be exponential in $\mathcal{H}$, we don't need to compute it since the for loop in line 5 of Algorithm 1 only runs through hyperedges of $\text{ext}_k(\mathcal{H})$ not included in any hyperedge of $\mathcal{H}$.

**Proposition 14.** *Let $\mathcal{H}$ be a $k$-conformal hypergraph. If $E \in \text{ext}_k(\mathcal{H})$, there exists $F \in \mathcal{H}$ such that $E \subseteq F$.*

*Proof.* Assume that there exists $E \in \text{ext}_k(\mathcal{H})$ such that $E$ is not included in any hyperedge of $\mathcal{H}$. Let $E' \subseteq E$ be a minimal subset that is contained in no hyperedge of $\mathcal{H}$. $E'$ is well defined since $E$ itself is contained in no hyperedge of $\mathcal{H}$. By definition of the conformality, we have $|E'| \le k$. Let $S$ be any superset of $E'$ of size $k$. Then the $k$-trace $(E \cap S, S)$ is realized by $E$ but does not belong to traces$_k(\mathcal{H})$ since $E' \subseteq E \cap S$ while no hyperedge of $\mathcal{H}$ contains $E'$. So $E$ realizes a $k$-trace which does not belongs to traces$_k(\mathcal{H})$ which is in contradiction with $E \in \text{ext}_k(\mathcal{H})$. □

**Corollary 15.** *Algorithm 1 runs in time $O(2^k(n|\mathcal{G}|)^{k+1})$ on $k$-conformal hypergraphs*

*Proof.* By Proposition 14 the second for loop is empty, and only the for loop in line 2 has to be taken into account. As already shown in the proof of Theorem 1 it runs in time $O(2^k(n|\mathcal{G}|)^{k+1})$. □
# 4 Hypergraph classes closed under subhypergraphs

As already mentioned in the introduction, a consequence of Theorem 1 or more precisely of corollary 12 is that TRANS-HYP is solvable in polynomial time in any proper class of hypergraph closed under partial subhypergraph. Indeed, any class of hypergraphs $\mathcal{H}$ that forbids a hypergraph $\mathcal{H}$ as partial subhypergraph is of bounded dimension and thus, Algorithm 1 can be used to solve the TRANS-HYP problem. We also show in this section that such a result is hopeless for the other notions of subhypergraph except if one can solve the TRANS-HYP problem in general hypergraphs in polynomial time.

## 4.1 Classes closed under partial subhypergraphs.

**Lemma 16.** If VC-DIM($\mathcal{H}$) = $k$, then $\mathcal{H}$ contains all hypergraphs on at most $k$ vertices as partial subhypergraph.

*Proof.* Let $\mathcal{H}' = (V' := \{v_1, ..., v_{|V'|}, F'\})$ be a hypergraph with $|V'| \le k$. Since VC-DIM($\mathcal{H}$) = $k \ge k$, $\mathcal{H}$ has a shattered set of vertices $T := \{t_1, ..., t_{|T'|}\}$ of size $|T'|$. Now since $T$ is shattered, for every $F := \{v_{i_1}, ..., v_{i_{|F'|}}\} \in \mathcal{H}'$ there exists $f(F) \in \mathcal{H}$ such that $f(F) \cap T = \{t_{i_1}, ..., t_{i_{|T'|}}\}$ and the partial subhypergraph $(T, \{f(F) | E \in \mathcal{H}'\})$ of $\mathcal{H}$ is a copy of $\mathcal{H}'$. $\square$

**Proposition 17.** Any proper class of hypergraphs $\mathcal{H}$ which is closed under partial subhypergraphs has a bounded VC-dimension.

*Proof.* Let $\mathcal{H}'$ a hypergraph with the minimum number $k$ of vertices which is not in $\mathcal{H}$. Such a hypergraph exists since $\mathcal{H}$ is a proper class of hypergraphs (i.e. it does not contain all hypergraphs). Let us show that the VC-dimension of $\mathcal{H}$ is bounded by $k$. Indeed let $\mathcal{H} \in \mathcal{H}$. Since $\mathcal{H}$ is closed under partial subhypergraph and since $\mathcal{H}' \notin \mathcal{H}$, $\mathcal{H}$ does not contain $\mathcal{H}'$ as partial subhypergraph. Hence, by Lemma VC-DIM($\mathcal{H}$) < $k$. $\square$

**Corollary 2.** TRANS-HYP can be solved in polynomial time in any proper class of hypergraphs closed under partial subhypergraph.

## 4.2 Other subhypergraphs types

Several types of subhypergraphs have been defined in the literature namely, *partial hypergraphs*, *subhypergraphs*, *partial subhypergraphs*, *edge-induced subhypergraphs* and *restrictions*. Even if the concepts of partial hypergraphs, subhypergraphs and partial subhypergraphs have been already defined, we recall them for comparison to the other notions. For a hypergraph $\mathcal{H} = (V, F)$,

* a *partial hypergraph* of $\mathcal{H}$ is a hypergraph $\mathcal{H}' = (V, F')$, for $F' \subseteq F$;

* a *subhypergraphs* of $\mathcal{H}$ is a hypergraph $\mathcal{H}' = (V', \{F \cap V' | F \in \mathcal{F}, F \cap V' \neq \emptyset\})$, for $V' \subseteq V$;
* a partial subhypergraphs of $\mathcal{H}$ is a hypergraph $\mathcal{H}' = (V', \{F \cap V' | F \in \mathcal{F}'\})$, for $V' \subseteq V$ and $\mathcal{F}' \subseteq \mathcal{F}$;

* an edge-induced subhypergraphs of $\mathcal{H}$ is a hypergraph $\mathcal{H}' = (\bigcup_{F \in \mathcal{F}'} F, \mathcal{F}')$, for $\mathcal{F}' \subseteq \mathcal{F}$;

* a restriction of $\mathcal{H}$ is a hypergraph $\mathcal{H}' = (V', \{F \in \mathcal{F} | F \subseteq V'\})$, for $V' \subseteq V$.

We show that a result similar to the one obtained in Corollary 2 for the other notions of subhypergraphs would imply a polynomial time algorithm for the general problem. More precisely we focus on the class of hypergraphs that forbids a specific hypergraph $\mathcal{F}$ as subhypergraph. Given a hypergraph $\mathcal{F}$, we denote by $\mathcal{H}_{\mathcal{F}}^{\mathcal{S}}$, $\mathcal{H}_{\mathcal{F}}^{\mathcal{Es}}$, $\mathcal{H}_{\mathcal{F}}^{\mathcal{R}}$, the set of hypergraphs that forbid $\mathcal{F}$ respectively as subgraph, edge-induced subgraph and restriction. For the case of edge-induced subhypergraphs, for any hypergraph $\mathcal{F}$, we prove that the TRANS-HYP problem in the class $\mathcal{H}_{\mathcal{F}}^{\mathcal{Es}}$ is as hard as in the general case.

For the case of restrictions and induced subhypergraphs, the difficulty of TRANS-HYP in the classes $\mathcal{H}_{\mathcal{F}}^{\mathcal{R}}$ and $\mathcal{H}_{\mathcal{F}}^{\mathcal{S}}$ depends of the hypergraph $\mathcal{F}$. For exemple if $\mathcal{F}$ is the complete hyperegraph on $k$ vertices (the hypergraph that contains all subsets as hyperedges), then the class $\mathcal{H}_{\mathcal{F}}^{\mathcal{S}}$ is precisely the class of hypergraph of VC-dimension strictly smaller than $k$ and Theorem 1 the problem is polynomial. However, if the hypergraph $\mathcal{F}$ is sparse enough, we prove that the TRANS-HYP problem restricted to the class $\mathcal{H}_{\mathcal{F}}^{\mathcal{S}}$ is as hard as in general hypergraphs.

For the case of restrictions, if $\mathcal{F}$ is the empty hypergraph on $k$ vertices (the hypergraph without any hyperedge), then the class $\mathcal{H}_{\mathcal{F}}^{\mathcal{R}}$ is the class of hypergraph for which the maximum independent set is strictly smaller than $k$. Since maximal independent sets are the complements of minimal transversals, one can enumerate all subsets of size smaller than $k$ and check whether the complement is a minimal transversal. Therefore, if $\mathcal{F}$ is the empty hypergraph, then TRANS-HYP problem in $\mathcal{H}_{\mathcal{F}}^{\mathcal{R}}$ is polynomial. In any other case, we prove that TRANS-HYP problem restricted to $\mathcal{H}_{\mathcal{F}}^{\mathcal{R}}$ is as hard as the general problem.

In order to prove the results of this section, we will use two different reductions. Given a hypergraph $\mathcal{H}$ and an integer $k$, we define $\hat{\mathcal{H}}^k$ to be the hypergraph obtained from $\mathcal{H}$ by adding $k$ new vertices to every hyperedges, and $\hat{\mathcal{H}}_k$ to be the hypergraph obtained from $\mathcal{H}$ by adding $\binom{n}{k}$ new hyperedges of size $k+1$ corresponding to all $k$-subsets of vertices of $\mathcal{H}$ plus a new vertex $x$.

* $\hat{\mathcal{H}}^k = (V(\mathcal{H}) \cup \{x_1, \dots, x_k\}, \{E \cup \{x_1, \dots, x_k\} | E \in \mathcal{E}(\mathcal{H})\})$

* $\hat{\mathcal{H}}_k = (V(\mathcal{H}) \cup \{x\}, \mathcal{E}(\mathcal{H}) \cup \{X \cup \{x\} | X \subseteq V(\mathcal{H}), |X| \le k\})$

We now show how the enumeration of minimal transversal of $\mathcal{H}$ can be reduced to the enumeration of minimal transversal of $\hat{\mathcal{H}}^k$ and $\hat{\mathcal{H}}_k$.

**Proposition 18.** Let $k$ be an integer and $\mathcal{H}$ be a hypergraphs, then $\text{Tr}(\hat{\mathcal{H}}^k) = \text{Tr}(\mathcal{H}) \cup \{\{x\} | x \in V(\hat{\mathcal{H}}^k) \setminus V(\mathcal{H})\}$.
**Proof.** Let $T \in \mathrm{Tr}(\hat{\mathcal{H}}^k)$. Then either $T \subseteq V(\mathcal{H})$ and $T$ is also a minimal transversal of $\mathcal{H}$ or $T$ contains at least one vertex $x \in V(\hat{\mathcal{H}}^k) \setminus V(\mathcal{H})$. Since $x$ belongs to every hyperedges of $\hat{\mathcal{H}}^k \{x\}$ is a transversal and my minimality of $T$ we have $T = \{x\}$. So $\mathrm{Tr}(\hat{\mathcal{H}}^k) \subseteq \mathrm{Tr}(\mathcal{H}) \cup \{\{x\} \mid x \in V(\hat{\mathcal{H}}^k) \setminus V(\mathcal{H})\}$. Now since every minimal transversal of $\mathcal{H}$ is also a minimal transversal of $\hat{\mathcal{H}}^k$ and any $x \in V(\hat{\mathcal{H}}^k) \setminus V(\mathcal{H})$ belongs to every hyperedge of $\hat{\mathcal{H}}^k$, we have $\mathrm{Tr}(\hat{\mathcal{H}}^k) \supseteq \mathrm{Tr}(\mathcal{H}) \cup \{\{x\} \mid x \in V(\hat{\mathcal{H}}^k) \setminus V(\mathcal{H})\}$. $\square$

**Proposition 19.** Let $k$ be an integer, $\mathcal{H}$ be a hypergraphs, then $\mathrm{Tr}(\hat{\mathcal{H}}_k) = \{T \cup \{x\} \mid T \in \mathrm{Tr}(\mathcal{H}), |T| < n-k+1\} \cup \mathcal{J}$ where $\mathcal{J}$ only contains subsets of size larger than $n-k+1$.

**Proof.** Let $T \in \mathrm{Tr}(\hat{\mathcal{H}}_k)$. Assume first that the only vertex $x \in V(\hat{\mathcal{H}}_k) \setminus V(\mathcal{H})$ belongs to $T$. Then $T \setminus \{x\}$ must minimally cover the hyperedges that don't contain $x$ i.e. $T \setminus \{x\}$ must be a minimal transversal of $\mathcal{H}$ since the hyperedges that contain $x$ are exactly $\mathcal{E}(\hat{\mathcal{H}}_k) \setminus \mathcal{E}(\mathcal{H})$. Assume now that $x \notin T$ and assume that $|T| < n-k+1$. Let $X \subseteq V(\mathcal{H}) \setminus T$ be a subset of vertices included in the complement of $T$ such that $|X| = k$, then $X \cup \{x\}$ is a hyperedge of $\hat{\mathcal{H}}_k$ whose intersection with $T$ would be empty contradicting the fact that $T$ is a transversal of $\hat{\mathcal{H}}_k$. So if $T \in \mathrm{Tr}(\hat{\mathcal{H}}_k)$ then either $x \in T$ and $T \setminus \{x\}$ is a minimal transversal of $\mathcal{H}$ or $|T| \ge n-k+1$. Assume now that $T \in \mathrm{Tr}(\mathcal{H})$ with $|T| < n-k+1$ and let us show that $T \cup \{x\} \in \mathrm{Tr}(\hat{\mathcal{H}}_k)$. Since $T$ is a minimal transversal of $\mathcal{H}$ and since $x$ belongs to every hyperedge of $\mathcal{E}(\hat{\mathcal{H}}_k) \setminus \mathcal{E}(\mathcal{H})$, $T \cup \{x\}$ is a transversal of $\hat{\mathcal{H}}_k$. Let us show that it is minimal. Observe first that since $|T| < n-k+1$, $T$ cannot be a transversal since its complement contains at least one $k$-subset $X$ of $V(\mathcal{H})$ and the hyperedge $X \cup \{x\}$ would be avoided by $T$. Now if there exists $T' \subset T$ such that $T' \cup \{x\} \in \mathrm{Tr}(\hat{\mathcal{H}}_k)$, since $x$ does not belong to any original hyperedge of $\mathcal{H}$, $T'$ would be a transversal of $\mathcal{H}$ contradicting the minimality of $T$. $\square$

**Lemma 20.** Let $\mathcal{F}$ be a fixed hypergraph on $k$ vertices, and let $\mathcal{H}$ be a hypergraph on at least $k$ vertices, then:

1. $\hat{\mathcal{H}}^{k+1}$ is edge-induced $\mathcal{F}$-free.

2. If $\mathcal{F}$ has at least one hyperedge, $\hat{\mathcal{H}}^{k+1}$ is restriction $\mathcal{F}$-free.

3. If there exists $\ell \le k$ such that $\mathcal{F}$ has strictly less than $(\binom{k-1}{\ell-1})$ hyperedges of size $\ell$, then $\hat{\mathcal{H}}_\ell$ is subhypergraph $\mathcal{F}$-free.

**Proof.** 1) Since every hyperedges of $\hat{\mathcal{H}}^{k+1}$ contains the set $X := \{x_1, \dots, x_{k+1}\}$ of additional vertices, any edge-induced subgraph of $\hat{\mathcal{H}}^{k+1}$ contains at least these $k+1$ vertices. Since $\mathcal{F}$ has only $k$ vertices, no edge-induced subgraph of $\hat{\mathcal{H}}^{k+1}$ can be isomorphic to $\mathcal{F}$.

2) Let $U \subseteq V(\mathcal{H})$. Since $X$ is included in every hyperedges of $\hat{\mathcal{H}}^{k+1}$, if $X \not\subseteq U$, the restriction of $\hat{\mathcal{H}}^{k+1}$ to $U$ contains no hyperedge. So any non empty restriction of $\hat{\mathcal{H}}^{k+1}$ must contain $X$ and so contains at least $k+1$ vertices. Since $\mathcal{F}$ has exactly $k$ vertices, $\hat{\mathcal{H}}^{k+1}$ is restriction $\mathcal{F}$-free.
3) Assume that there exists $\ell \le k$ such that $\mathcal{F}$ has strictly less than $\binom{k-1}{\ell-1}$ hyperedges of size $\ell$ and let $U \subseteq V(\mathcal{H})$ be a subset of size $k$. Let $x$ be the extra vertex added in $V(\hat{\mathcal{H}}_{\ell+1})$ not present in $V(\mathcal{H})$. If $U$ does not contain $x$, any subset $E$ of $U$ of size $\ell$ will form a hyperedge with $x$. Since $x$ does not belong to $E$, $E$ is an hyperedge of the subhypergraph induced by $U$. So the subhypergraph induced by $U$ contains $\binom{k}{\ell} \ge \binom{k-1}{\ell-1}$ hyperedges of size $\ell$ and cannot be isomorphic to $\mathcal{F}$. Assume now that $x \in U$. Since we assumed that $\mathcal{H}$ has at least $k$ vertices, $\hat{\mathcal{H}}_\ell$ has at least $k+1$ vertices and there exists a vertex $y \notin U$. Now for any subset $E$ of $U \setminus \{x\}$, of size $\ell-1$, there exists a hyperedge $E \cup \{x,y\}$ in $\hat{\mathcal{H}}_\ell$ and so the subhypergraph induced by $U$ has $E \cup \{x\}$ as hyperedge. So the subhypergraph induced by $U$ contains at least $\binom{k-1}{\ell-1}$ hyperedges of size $\ell$ and cannot be isomorphic to $\mathcal{F}$. $\square$

**Theorem 21.** Let $\mathcal{F}$ be a hypergraph, then the restriction of the TRANS-HYP problem to the following classes of hypergraph is as hard as the TRANS-HYP problem in general hypergraphs:

* $\mathcal{H}_{\mathcal{F}}^{Es}$

* $\mathcal{H}_{\mathcal{F}}^{R}$ if $\mathcal{F}$ is different from the empty hypergraph.

* $\mathcal{H}_{\mathcal{F}}^{S}$ if there exists $\ell \le |V(\mathcal{F})|$ such that $\mathcal{F}$ has less than $\binom{|V(\mathcal{F})|-1}{\ell-1}$ hyper-edges of size $\ell$.

*Proof*. By lemma 20 it is sufficient to prove that for a given integer $k$, one can reduce in polynomial time the enumeration of minimal transversal of $\mathcal{H}$ to the enumeration of minimal transversal of $\hat{\mathcal{H}}^k$ and $\hat{\mathcal{H}}_k$.

Assume that one can enumerate the minimal transversal of $\hat{\mathcal{H}}^k$ in $O((|\hat{\mathcal{H}}^k| + |Tr(\hat{\mathcal{H}}^k)|)^\ell)$. By lemma 18, $Tr(\hat{\mathcal{H}}^k) = Tr(\mathcal{H}) \cup \{\{x\} | x \in V(\hat{\mathcal{H}}^k) \setminus V(\mathcal{H})\}$. So one can simply check for each $T \in Tr(\hat{\mathcal{H}}^k)$ whether $T$ is a minimal transversal of $\mathcal{H}$. Since $|\hat{\mathcal{H}}^k| = |\mathcal{H}|$ and $|Tr(\hat{\mathcal{H}}^k)| = |Tr(\mathcal{H})| + k$, the total running time is $O((|\mathcal{H}| + |Tr(\mathcal{H})|)^\ell)$.

Assume now that one can enumerate the minimal transversal of $\hat{\mathcal{H}}_k$ in $O((|\hat{\mathcal{H}}^k| + |Tr(\hat{\mathcal{H}}^k)|)^\ell)$. By lemma 19, $Tr(\hat{\mathcal{H}}_k) = \{T \cup \{x\} | T \in Tr(\mathcal{H}), |T| < n-k+1\} \cup \mathcal{J}$ where $\mathcal{J}$ only contains subsets of size larger than $n-k+1$. One can start by enumerating all minimal transversal of $\mathcal{H}$ of size larger than $n-k+1$ in a brute-force way by checking all the $O(n^{k-1})$ such subsets. Then for every $T \in Tr(\hat{\mathcal{H}}_k)$ with $|T| \le n-k+1$ that contains $x$, output $T \setminus \{x\}$ (where $x$ is the additional vertex of $V(\hat{\mathcal{H}}^k) \setminus V(\mathcal{H})$). Since $|\hat{\mathcal{H}}_k| = O(|\mathcal{H}| + n^k)$ and $|Tr(\hat{\mathcal{H}}_k)| = O(|Tr(\mathcal{H})| + n^k)$, the total running time is $O(|\mathcal{H}| + |Tr(\mathcal{H})|)^{\ell k}$. $\square$

## References

[1] Claude Berge. Hypergraphs: combinatorics of finite sets. Number v. 45 in North-Holland mathematical library. North Holland : Distributors for the
U.S.A. and Canada, Elsevier Science Pub. Co, Amsterdam ; New York, 1989.

[2] J.C. Bioch and T. Ibaraki. Complexity of identification and dualization of positive boolean functions. *Information and Computation*, 123(1):50-63, November 1995.

[3] E. Boros, V. Gurvich, K. Elbassioni, and L. Khachiyan. An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension. *Parallel Processing Letters*, 10(04):253-266, December 2000.

[4] Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Leonid Khachiyan. Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections. In Gerhard Goos, Juris Hartmanis, Jan van Leeuwen, and Martín Farach-Colton, editors, *LATIN 2004: Theoretical Informatics*, volume 2976, pages 488-498. Springer Berlin Heidelberg, Berlin, Heidelberg, 2004.

[5] Endre Boros, Vladimir Gurvich, and Peter L. Hammer. Dual subimpli-cants of positive boolean functions. *Optimization Methods and Software*, 10(2):147-156, 1998.

[6] Thomas Eiter and Georg Gottlob. Identifying the minimal transversals of a hypergraph and related problems. *SIAM Journal on Computing*, 24(6):1278-1304, December 1995.

[7] Thomas Eiter and Georg Gottlob. Hypergraph Transversal Computation and Related Problems in Logic and AI. In G. Goos, J. Hartmanis, J. van Leeuwen, Sergio Flesca, Sergio Greco, Giovambattista Ianni, and Nicola Leone, editors, *Logics in Artificial Intelligence*, volume 2424, pages 549-564. Springer Berlin Heidelberg, Berlin, Heidelberg, 2002.

[8] Thomas Eiter, Georg Gottlob, and Kazuhisa Makino. New results on monotone dualization and generating hypergraph transversals. *Proceedings of the thiry-fourth annual ACM symposium on Theory of computing*, page 9, 2002.

[9] Thomas Eiter, Kazuhisa Makino, and Georg Gottlob. Computational aspects of monotone dualization: A brief survey. *Discrete Applied Mathematics*, 156(11):2035-2049, June 2008.

[10] Khaled Elbassioni and Adrian Dumitrescu. Computational geometry column 66. *SIGACT News*, 48(4):57-74, dec 2017.

[11] Khaled Elbassioni and Kazuhisa Makino. Enumerating vertices of covering polyhedra with totally unimodular constraint matrices. *SIAM Journal on Discrete Mathematics*, 34(1):843-864, 2020.
[12] Khaled Elbassioni, Kazuhisa Makino, and Imran Rauf. Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs. In *Amos Fiat and Peter Sanders, editors, *Algorithms - ESA 2009*, volume 5757, pages 143–154. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009.

[13] Khaled Elbassioni and Imran Rauf. Polynomial-time dualization of *r*-exact hypergraphs with applications in geometry. *Discrete Mathematics*, 310(17-18):2356–2363, September 2010.

[14] Khaled Elbassioni, Imran Rauf, and Saurabh Ray. A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs. *Theoretical Computer Science*, 767:26–33, 2019.

[15] Khaled Elbassioni, Imran Rauf, and Saurabh Ray. A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs. *Theoretical Computer Science*, 767:26–33, May 2019.

[16] Michael L. Fredman and Leonid Khachiyan. On the complexity of dualization of monotone disjunctive normal forms. *Journal of Algorithms*, 21(3):618–628, November 1996.

[17] Dimitrios Gunopulos, Heikki Mannila, Roni Khardon, and Hannu Toivonen. Data mining, hypergraph transversals, and machine learning (extended abstract). In *Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems - PODS '97*, pages 209–216, Tucson, Arizona, United States, 1997. ACM Press.

[18] Leonid Khachiyan, Endre Boros, Khaled Elbassioni, and Vladimir Gurvich. On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs. *Theoretical Computer Science*, 382(2):139–150, August 2007.

[19] Leonid Khachiyan, Endre Boros, Vladimir Gurvich, and Khaled Elbassioni. Computing many maximal independent sets for hypergraphs in parallel. *Parallel Processing Letters*, 17(02):141–152, June 2007.

[20] Nina Mishra and Leonard Pitt. Generating all maximal independent sets of bounded-degree hypergraphs. In *Proceedings of the tenth annual conference on Computational learning theory*, COLT '97, pages 211–217, New York, NY, USA, July 1997. Association for Computing Machinery.

[21] Ken Takata. A worst-case analysis of the sequential method to list the minimal hitting sets of a hypergraph. *SIAM Journal on Discrete Mathematics*, 21(4):936–946, January 2008.

[22] V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. *Theory of Probability &amp; Its Applications*, 16(2):264–280, January 1971. Publisher: Society for Industrial and Applied Mathematics.