text:
\section{Introduction}

Let $W$ be a finite set (such as all sets in this article).  Given a hypergraph
(=set system) $\mathbb{H}\subseteq {\cal P}(W)$, a ($\mathbb{H}$-){\it hitting set\footnote{Synonymously we sometimes speak (from Section 4 onwards) of a 'transversal'. }} is a set $X\subseteq W$ such that $X\cap H\neq \emptyset$ for all {\it hyperedges} $H\in \mathbb{H}$. Let $HS(\mathbb{H})$ be the set of all $\mathbb{H}$-hitting sets, and $MHS(\mathbb{H})$ the subset of all (inclusion-)minimal $\mathbb{H}$-hitting sets.
The famous {\it Minimal Hitting Set Problem (MHS-Problem)} is this: Given a hypergraph
  $\mathbb{H}\subseteq {\cal P}(W)$, is it possible to enumerate $MHS(\mathbb{H})$  in polynomial total time, i.e. polynomial in $N:=|MHS(\mathbb{H})|,\ w:=|W|$, and $h:=|\mathbb{H}|$? We  refer to [GV] and [EGM] for the history and the state of the art concerning the 'classic' MHS-Problem.

The  objective in our article  is to tweak the MHS-Problem in another direction.  Instead of chasing  polynomial total time we attempt a {\it compressed} (as opposed to one-by-one) enumeration of $MHS(\mathbb{H})$. Our essential compression tools are multivalued rows, e.g. $01g$-rows like $c=(0,g,g,g,1,g',0,g')$. They feature wildcards $ggg$ and $g'g'$ that demand 'exactly one 1 here'. Formally $c$ is the set of six bitstrings $x\in\{0,1\}^8$ satisfying
$x_1=x_7=0,\ x_5=1$, as well as $|\{i\in\{2,3,4\}:\ x_i=1\}|=1$ and $|\{i\in\{6,8\}:\ x_i=1\}|=1$. We shall henceforth silently identify a bitstring like $x=(0,0,0,1,1,0,0,1)$  with the set $X=\{4,5,8\}$ in the usual way. Accordingly the 01g-row $c$ can be viewed as a set system containing six sets.

{\bf 1.1}
Section 2 deals with {\it exact} $\mathbb{H}$-hitting sets $X\subseteq W$, i.e. satisfying $|X\cap H|=1$ for all hyperedges $H$ in $\mathbb{H}$. For instance, finding a solution to a Sudoku puzzle amounts to find an exact hitting set.  Under a mild assumption the class $EHS(\mathbb{H})$ of all hitting sets is a subclass of
$MHS(\mathbb{H})$ that is easier to handle  than the whole of $MHS(\mathbb{H})$, and hence we dwell on it first.
Call the $01g$-row $c\subseteq {\cal P}(W)$ {\it feasible} if $c\cap EHS(\mathbb{H})\neq\emptyset$. A straightforward adaption of Knuth's Dancing-Links algorithm suggests itself as feasibility test in the general case. By iteratively 'imposing' the hyperedges, and by repeated feasibility tests, we render $EHS(\mathbb{H})$ in
a compressed format, i.e. as a disjoint union of $01g$-rows $c_i$ (Theorem 1). According to Corollary 2  all perfect matchings of a $K_{3,3}$-minor-free graph can be enumerated  in polynomial total time. (Accepting randomization one can even dispense with $K_{3,3}$-minor-freeness.)

 Section 3 introduces a natural but apparently novel  equivalence relation $\sim$ on $W$ which is induced by $\mathbb{H}\subseteq {\cal P}(W)$. It turns out that compressing  $EHS(\mathbb{H})$ is possible iff $\sim$ is nontrivial. In contrast, for {\it minimal} hitting sets, our topic in the remaining Sections 4 to 11, compressing $MHS(\mathbb{H})$ is possible more often than not, even when $\sim$ is trivial.

 Section 4  reviews the transversal e-algorithm [W1] that represents  $HS(\mathbb{H})$  as a disjoint union of $R$ many 012e-rows $r_i$.
 We call them {\it semifinal} because, while being crucial, they will require  further processing. The $e$ in $012e$ refers to a second kind of wildcard $ee...e$ which demands 'at least one 1 here'. For instance the $012e$-row $r=(0,e,e,e,1,e',2,e')$ consists of all bitstrings $x\in \{0,1\}^8$ satisfying $x_1=0,\ x_5=1$, as well as $1\in\{x_2,x_3,x_4\}$ and $1\in\{x_6,x_8\}$. The family of all $r$-{\it minimal}, i.e. all inclusion-minimal $X\in r$, is denoted as $min(r)$. It consists of all sets $Y\cup\{5\}$ where $Y$ ranges over the six transversals of $\{\{2,3,4\},\{6,8\}\}$.
 It is an obvious yet crucial observation that each minimal hitting set $X$ is a fortiori $r$-minimal in the unique
 semifinal row $r$ to which it happens to belong.
 Consequently  $MHS(\mathbb{H})\subseteq \biguplus_{i=1}^R min(r_i)$. While this was observed already in [W1], the present article attempts  to find efficient ways for sieving $MHS(r_i):=min(r_i)\cap MHS(\mathbb{H})$ from $min(r_i)$.
  For starters, call a semifinal row $r$ {\it bad} if $MHS(r)=\emptyset$, and {\it good} otherwise.
 If  $MHS(r)=min(r)$ then $r$ is {\it very-good}.

  Let us discuss the latter kind first\footnote{For the sake of the storyline we prefer to {\it not} discuss the Sections 5 to 11  in chronological order. Also note that Section 5.1 will give  a detailed survey of the Sections ahead of it; this would be impossible at present.}.
 Most importantly, all
 {\it minimum} (cardinality) hitting sets must occur in very-good rows, and are whence discovered immediately.  There seems to be no previous publication dedicated to the minimum hitting sets, let alone producing them in compressed format.
  As to detecting {\it other} very-good rows,
  upon sampling a few random members of $min(r)$, one may know that $r$ is {\it likely-very-good}\footnote{If say 12 out of 20 random members of $min(r)$ turn out to be minimal hitting sets (by brute-force testing) then $r$ is {\it merely-good} (=good but not very-good). But if 20 out of 20 succeed, the $r$ is likely-very-good.}. In the latter case one has to test whether it {\it really} is very-good, preferably in more clever ways than investigating all members of $min(r)$ individually.
   We will offer two more subtle ways. The one in Section 6 is based on inclusion-exclusion, the one in Section 8 involves a certain MC-condition
 introduced in [MU].

 As to identifying bad semifinal 012e-rows, upon sampling  random members of $min(r)$, one
 can again identify {\it likely-bad} rows.
  In the latter case deciding  whether $r$ is really bad is harder than deciding 'really very-good'. Section 9 develops three inreasingly sophisticated badness-tests, again all of them  based on the MC-condition.
  A badness-test is also necessary in Section 5, which discusses how a merely-good  row $r$ can be replaced by very-good rows $\rho_1,...,\rho_s$ in such a way that $MHS(r)=MHS(\rho_1)\uplus\cdots\uplus MHS(\rho_s)$. Section 11 is dedicated to numerical experiments. In a nutshell, our algorithm is most efficient for hypergraphs with few (but possibly large) hyperedges. Then the very-good rows are numerous and each can compress billions of minimal hitting sets. For hypergraphs with many hyperedges the competiveness of our algorithm is less clear-cut. On the plus side, it is easier to parallelize than some algorithms investigated in [GV], and it supports cut-off. Furthermore, almost independent of the size of $\mathbb{H}$, it invites uniform random sampling of minimal hitting sets.

  Sections 7 and 10 are of  lesser importance for the overall picture. The former is about  a technique from data mining (Vertical Layout) which we adopt in order to more efficiently manipulate large set families ${\cal S}$.

\section{Enumerating all exact hitting sets }

Instead of arbitrary finite sets $W$ we mostly stick to $[w]:=\{1,2,\ldots,w\}$ and let ${\cal P}[w]$ be the powerset of $[w]$. Throughout the article we look at hypergraphs  $\mathbb{H}\subseteq {\cal P}[w]$ of cardinality $h:=|\mathbb{H}|$ which are {\it full} in the sense that $\bigcup\mathbb{H}=[w]$ (to avoid trivial cases).
An {\it exact hitting set (EHS)} with respect to a hypergraph $\mathbb{H}$ is a subset $X\subseteq [w]$ such that $|X\cap H|=1$ for all $H\in\mathbb{H}$.
Because of $\bigcup\mathbb{H}=[w]$  each $a\in X$ belongs to some hyperedge $H$. This implies that each EHS is a minimal hitting set\footnote{The converse fails. In fact $\mathbb{H}_2$ in 4.1.1 has {\it no} EHSes. We mention in passing that hypergraphs $\mathbb{H}$ with $MHS(\mathbb{H})=EHS(\mathbb{H})$ can be reckognized in polynomial time [E], and that $MHS(\mathbb{H})$ can be output one-by-one with polynomial delay.}.

Imagine a hypergraph with 20 mutually disjoint 10-element hyperedges. Then it has $10^{20}$ exact hitting sets.
Is there a systematic way to render them in a compressed format? Of course that way should also offer compression in less trivial cases.
In the sequel we compress the set $EHS(\mathbb{H})$ of all exact $\mathbb{H}$-hitting sets  by 'imposing' the hyperedges one after the other\footnote{This is in line with previous  publications  where various types of 'constraints' have been imposed one after the other; see [W2] for a survey of the story so far.}.

{\bf 2.1}
Consider the hypergraph $\mathbb{H}_1\subseteq {\cal P}[9]$ consisting of the three hyperedges

(1) \quad $K_1 =\{2,3,4,6\},\ K_2=\{1,2,3,4,5,7\},\ K_3=\{2,8,9\}$.

If instead of $\{K_1,K_2,K_3\}$ we just have $\{K_1\}$, then the set of $\{K_1\}$-hitting sets, i.e.\\
 $\{X\subseteq [9]: |X\cap \{2,3,4,6\}|=1\}$, can be written as the 012g-row $c_0$ below (recall the definitions in Section 1).

\begin{tabular}{l|c|c|c|c|c|c|c|c|c|c}

	&1 &2 &3 &4 &5 &6 & 7&8 &9&    \\ \hline

	& & & & & & & & &  &  \\ \hline

	$c_0=$ &  2 &  $g$ &  $g$ &  $g$ &  2 &  $g$ &   2&  2 &  2 & pending $K_2$     \\ \hline
		& & & & & & & & &  &  \\ \hline
	$\gamma_1=$ &  2 &  ${\bf 0}$ &  ${\bf 0}$ &  ${\bf 0}$ &  2 &  1 &    2&  2 &  2 &  \\ \hline
	$\gamma_2=$ &  2 &  ${\bf g}$ &  ${\bf g}$ &  ${\bf g}$ &  2 &  0 &    2&  2 &  2 &  \\ \hline\hline

	$c_1=$ &  ${\bf g}$ &   0 &   0 &   0 &  ${\bf g}$&  1 &    ${\bf g}$&  2 &  2 & pending $K_3$ \\ \hline
	$c_2=$ &  {\bf 0} &  ${ g}$ &  ${ g}$ &  ${ g}$ &  {\bf 0} &  0 &    {\bf 0}&  2 &  2 & pending $K_3$ \\ \hline\hline
		& & & & & & & & &  &  \\ \hline

	$c_3=$ &  $g_1$ &   0 &   0 &   0 &  $g_1$&  1 &    $g_1$&  $g_2$ &  $g_2$ & final  \\ \hline
	$c_2=$ &  0 &  ${ g}$ &  ${ g}$ &  ${ g}$ &  0 &  0 &    0&  2 &  2 & pending $K_3$ \\ \hline
		& & & & & & & & &  &  \\ \hline
	$\gamma_3=$ &  0 &  ${\bf 0}$ &  ${ g}$ &  ${ g}$ &  0 &  0 &    0&  2 &  2 &  \\ \hline
	$\gamma_4=$ &  0 &  ${\bf 1}$ &  0 &  0 &  0 &  0 &    0&  2 &  2 &  \\ \hline\hline
	$c_4=$ &  0 &  0 &  ${ g_1}$ &  ${ g_1}$ &  0 &  0 &    0&  $g_2$ &  $g_2$ & final \\ \hline
	$c_5=$ &  0 &  1 &  0 &  0 &  0 &  0 &    0&  0 &  0 & final \\ \hline
\end{tabular}

{\sl Table 1: The working stack for the g-algorithm}

In order to sieve the $\{K_1,K_2\}$-EHSes $X$ from $c_0$  we observe that $K_1\cap K_2=\{2,3,4\}$ and accordingly write $c_0=\gamma_1\uplus\gamma_2$ (Table 1). That helps because sieving the $\{K_1,K_2\}$-EHSes from the auxiliary rows $\gamma_1,\gamma_2$  is easy. It results in $c_1,c_2$ respectively. For both rows the imposition of $K_3$ is still {\it pending}. Each row in the  stack must be tagged with this kind of information. Picking the top row of the current {\it working stack} $\{c_1,c_2\}$ we focus on $c_1$. It is evident that the subset of all $X\in c_1$ with $|X\cap K_3|=1$ can be as the 012g-row $c_3$ in Table 1; notice that the two independent $g$-wildcards in $c_3$ are distinguished by subscripts. Row $c_3$ is {\it final} in the sense that all hyperedges have been imposed on it; this amounts to $c_3\subseteq EHS(\mathbb{H})$. We hence remove $c_3$  from the  working stack and make it the first final row\footnote{Our working stack is a Last-In-First-Out (LIFO) stack. The activities in the LIFO stack are cryptomorphic to tracing a computation tree whose leaves correspond to our final rows.}. In order to impose $K_3$ on the last row $c_2$ in the working stack we again split it into auxiliary rows, i.e. $c_2=\gamma_3\uplus\gamma_4$. Imposing $K_3$ upon $\gamma_3,\gamma_4$ individually is easy and gives rise to $c_4,c_5$ respectively, both of which are final.

We hence have $EHT(\mathbb{H}_1)=c_3\uplus c_4\uplus c_5$. In particular $\mathbb{H}_1$ has
 $3\cdot 2+2\cdot 2+1=11$ exact hitting sets.

{\bf 2.2} Let us explain  how to generally impose a hyperedge $K$ upon a 012g-row. Instead of the ad hoc 'auxiliary rows' above we embrace the more systematic concept of a {\it 0g0-Abraham\footnote{This visualizes an idea of Abraham from 1979, see [W2] for more details.}-Flag}. To fix ideas we impose $K=\{1,2...,6\}$ upon the 012g-row\footnote{To avoid distraction we chose $twos(c)=ones(c)=zeros(c)=\emptyset$. Only trivial modifications would occur otherwise.} $\overline{c_0}$ in Table 2.
The Abraham $0g0$-Flag in Table 2 is the boldface $4\times 6$-rectangle whose 'diagonal' consists of $g$-wildcards, with the understanding that each $g$-wildcard of length one "degenerates" to a 1-bit.

\begin{tabular}{l|c|c|c|c|c|c|c|c|c|c|c|c|c|}

	&1 &2 &3 &4 &5 &6 & &7 &8 &9 &10 &11 &12  \\ \hline

	& & & & & & & & & & & & &   \\ \hline

	$\overline{c_0}=$ &  $g_1$ &  $g_1$ &  $g_2$ &  $g_2$ &  $g_3$ &  $g_4$ &  &  $g_1$&  $g_1$ &  $g_2$ &  $g_3$ &  $g_3$ &  $g_4$    \\ \hline

	& & & & & & & & & & & & &   \\ \hline

	$\overline{c_1}=$ &  ${\bf g_1}$ &  ${\bf g_1}$ &  ${\bf 0}$ &  ${\bf 0}$ &  ${\bf 0}$ &  ${\bf 0}$ &  &  $0$&  $0$ &  $1$ &  $g_3$ &  $g_3$ &  $1$    \\ \hline

	$\overline{c_2}=$ &  ${\bf 0}$ &  ${\bf 0}$ &  ${\bf g_2}$ &  ${\bf g_2}$ & ${\bf 0}$  & ${\bf 0}$ &  &  $g_1$&  $g_1$ &  $0$ &  $g_3$ &  $g_3$ &  $1$    \\ \hline

	$\overline{c_3}=$ &  ${\bf 0}$ &  ${\bf 0}$ & ${\bf 0}$ & ${\bf 0}$ &  ${\bf 1}$ & ${\bf 0}$ &  &  $g_1$&  $g_1$ &  $1$ &  $0$ &  $0$ &  $1$    \\ \hline

	$\overline{c_4}=$ &  ${\bf 0}$ &  ${\bf 0}$ &  ${\bf 0}$ & ${\bf 0}$ &  ${\bf 0}$ &  ${\bf 1}$ &  &  $g_1$&  $g_1$ &  $1$ &  $g_3$ &  $g_3$ &  $0$    \\ \hline
\end{tabular}

{\sl Table 2: Imposing the exact hitting set $\{1,\ldots,6\}$ upon the 01g-row $c_0$}

The bitstrings (=sets) $X\in \overline{c_0}$ that  hit $K$ in exactly one element $i\in K$ come in four  flavors dictated by the structure of $\overline{c_0}$; either $i\in\{1,2\}$, or $i\in\{3,4\}$, or $i=5$, or $i=6$.
Pleasantly, the corresponding mutually disjoint sets of bitstrings, call them $\overline{c_1}$ to $\overline{c_4}$, can themselves be written as 01g-rows in obvious ways.

{\bf 2.3} Adhering to previous terminology we call $\overline{c_1}$ to $\overline{c_4}$ the {\it candidate sons} of $\overline{c_0}$ (that arise upon imposing $K$ on $\overline{c_0}$). Usually $K$ is  one among many hyperedges in $\mathbb{H}$ pending to be imposed, and we need to know which of the candidate sons $\overline{c_i}$ are {\it feasible} in the sense that $\overline{c_i}\cap EHS(\mathbb{H})\neq \emptyset$. Infeasible candidate sons (=duds)
should be cancelled because they can\footnote{Nevertheless, it does not pay running an expensive feasibility test if the duds are few.} cause a lot of useless work. The popular (google) Dancing-Links algorithm of Knuth which decides (though not in polynomial time) whether or not a given hypergraph admits a hitting set, is easily adapted to a feasibility test for
candidate sons. The surviving candidate sons of $\overline{c_0}$ are its {\it sons}. The described method will be coined\footnote{This name was previously used by the author in various circumstances involving g-wildcards. There is no danger of confusion.} the {\it g-algorithm}.

{\bf Theorem 1:} {\it Let $\mathbb{H}\subseteq{\cal P} [w]$ be a hypergraph. Then $EHS(\mathbb{H})$ can be enumerated as a disjoint union of $R$ many 01g-rows in time $O(Rhw\cdot feas(h,w))$. Here $feas(h,w)$ upper-bounds the time for any chosen subroutine (e.g. Dancing-Links) to decide whether a hypergraph with $\le w$ vertices and $\le h$ hyperedges has an EHS.}

{\it Proof.} Throughout the g-algorithm the  top rows in the LIFO-stack  match the nodes of a computation tree (rooted at $r_0$) whose $R$ leaves are the final rows. The length of a root-to-leaf path equals the number of impositions that were required to generate that leaf (=final row), and hence that length is at most $h$. In the worst case (i.e. when all root-to-leaf paths are mutually disjoint and have maximal length) the number of non-root nodes, i.e. the number of impositions, equals $Rh$.

What is the maximum cost $imp(h,w)$ of imposing a hyperedge on a LIFO top row $r$?
Building the at most $\tau=\tau(\mathbb{H}):=max \{ |H|:\ H\in\mathbb{H}\}$
candidate sons $c_i$ of $c$ (by way of  0g0-Abraham-Flags) costs $O(\tau w)$.   Letting $feas(h,w)$ be any time bound\footnote{For technical reasons we postulate that $f(h,w)\ge hw$. For every non-trivial hypergraph $\mathbb{H}$ this inequality holds anyway.} for checking  the feasibility of a 012g-row it costs $O(\tau feas(h,w))$ to discard the infeasible candidate sons. A surviving son $\overline{c_i}$ satisfies a fixed hyperedge $K$ iff in $\overline{c_i}$ the bits with indices in $K$ are all  0's except for one 1 (alternatively: for one entire $g$-wildcard). Hence it costs $O(\tau hw)$ to tag each son with its pending hyperedge.
We conclude that $imp(h,w)=O(\tau w+\tau hw+\tau feas(h,w))$ and
therefore:

(2)\quad The overall cost of imposing the hyperedges of $\mathbb{H}$ in order to pack all exact hitting sets of\\ \hspace*{1cm}
 $\mathbb{H}$ into $R$ disjoint 01g-rows  is $O(Rh\cdot imp(h,w))=O(Rh\tau(hw+feas(h,w)) )$.

Since we postulated $f(h,w)\ge hw$ and since $\tau\le w$, we have $O(Rh\tau(hw+feas(h,w)) )=O(Rhw\cdot feas(h,w)).\ \square$

{\bf 2.4} An important  kind of exact hitting set arises from any  graph $G$ with vertex set $V$ and edge set $E$. Namely, if $star(v)$ is the set of all edges incident with vertex $v$ and $\mathbb{H}:=\{star(v):\ v\in V\}\subseteq {\cal P}(E)$, then the EHSes of $\mathbb{H}$ are exactly the perfect matchings of $G$. Recall that $K_{3,3}$ is the complete bipartite graph both shores of which having 3 vertices. A graph $G$ is $K_{3,3}$ {\it minor-free} if one cannot obtain $K_{3,3}$ from $G$ by deleting edges and vertices of $G$, nor by contracting edges of $G$.

{\bf Corollary 2:} {\it All perfect matchings of a $K_{3,3}$ minor-free graph $G$ can be enumerated in polynomial total time.}

{\it Proof.} In our context each feasibility test performed by the $g$-algorithm  on a $01g$-row $c$ de facto decides whether a certain
minor $G(0,1)$ of $G$ of has a perfect matching. Specifically, the 0's in  $c$ delete edges from $G$ which thus becomes a sparser graph $G(0)$. The 1's in $c$ constitute a partial matching $P$ in $G(0)$ which wants to be extended to a perfect matching of $G(0)$. This is possible iff a certain subgraph $G(0,1)$ of $G(0)$ has a perfect matching. Namely, $G(0,1)$ is obtained by removing all edges  of $P$, along with all edges incident with them. The arising isolated vertices are also removed.
With $G$ also its minor $G(0,1)$ is $K_{3,3}$-minor-free. By Corollary 1 in [V] one can decide in polynomial time (in fact even NC-time) whether $G(0,1)$ has a perfect matching. Hence the function $feas(h,w)$ in Theorem 1 is bound by a polynomial in $h,w$, causing the overall algorithm to run in total polynomial time. $\square$

One can dispense with $K_{3,3}$-minor-freeness if one allows for randomization because deciding the existence of a perfect matching is in RNC [MR,p.347]. Perfect matchings in bipartite graphs have been dealt with before [U].

\section{Degenerate and nondegenerate hypergraphs}

 For a hypergraph $\mathbb{H}=\{K_1,\ldots,K_h\}\subseteq {\cal P}(W)$ we say that $x,y\in W$ are ($\mathbb{H}$-){\it equivalent}\\ (written $\sim$) if $\forall (1\le i\le h)\ x\in K_i\Leftrightarrow y\in K_i$. If the equivalence relation $\sim$ is the identity relation, then $\mathbb{H}$ is called {\it nondegenerate}, otherwise {\it degenerate}. For instance, if $\mathbb{H}$ is the  hypergraph of all stars of a graph (see 2.4) then $\mathbb{H}$ is  nondegenerate. On the other hand, the vertices $5,7$ are $\mathbb{H}_1$-equivalent (see 2.1), and so $\mathbb{H}_1$ is degenerate.
  For each index set
 $I\subseteq [h]$ let $\mathbb{H}(I)$ be the set of $x\in W$ which are in all $K_i$'s $(i\in I)$ and nowhere else. Formally

 (3)\quad $\mathbb{H}(I):=\bigcap \{K_i:\ i\in I\}\ \cap\ \bigcap\{W\setminus K_i:\ i\in [h]\setminus I\}$.

 If $\mathbb{H}(I)\neq\emptyset$ then $\mathbb{H}(I)$ is a $\sim$class, and each  $\sim$class arises this way\footnote{A fast way to calculate the $\sim$classes will be discussed in Section 7.2.}. It follows that $2^h<w$ is a sufficient condition for $\mathbb{H}$ to be degenerate.
 Generally, if a $\sim$class $C$ intersects $K_i$, then it must be {\it contained} in $K_i$; otherwise there were $x,y\in C$, one in $K_i$, the other not, which is impossible. Therefore, if
  $\overline{K_i}$ denotes the set of $\sim$classes contained in $K_i$, then $K_i=\biguplus \overline{K_i}$.
   The {\it reduced} hypergraph $\overline{\mathbb{H}}:=\{\overline{K_1},\ldots,\overline{K_h}\}$ has $h_0\le h$ hyperedges and is nondegenerate. For instance, for $\mathbb{H}_1$ in (1) the $\mathbb{H}_1$-classes are
  $\overline{1}(=\overline{5}=\overline{7})=\{1,5,7\},\ \overline{2}=\{2\},\ \overline{3}=\{3,4\},\ \overline{6}=\{6\},\ \overline{8}=\{8,9\}$. Hence
  $\overline{\mathbb{H}_1}=\{\overline{K_1},\overline{K_2},\overline{K_3}\}$, where $\overline{K_1}=\{\overline{2},\overline{3},\overline{6}\},\ \overline{K_2}=\{\overline{1},\overline{2},\overline{3}\},\ \overline{K_3}=\{\overline{2},\overline{8}\}$.

  {\bf 3.1} Let us connect all of this with $g$-wildcards. It will henceforth be handy to call $g$-{\it bubble} the position set of a $g$-wildcard. Thus the $g$-bubble of the $g$-wildcard in row $c_0$ of Table 1 is $\{2,3,4,6\}$.
  In fact this $g$-bubble is $K_1$ and whence a union of $\sim$classes. By induction and the workings of 0g0-Abraham-Flags named property gets perpetuated:

  \begin{itemize}
  	\item[(4)] {\it When applying the g-algorithm to the hypergraph $\mathbb{H}$,  each occuring g-bubble is a union of $\sim$-classes.}
  	\end{itemize}

  Suppose for some hypergraph $\mathbb{H}$ we managed (with the g-algorithm or otherwise) to write $EHS(\mathbb{H})$ as a disjoint union of final $01g$-rows. Fix any position set $\Gamma=\{a,b,\ldots\}$ of any g-wildcard in any final $01g$-row $c$ and take any set $X\in c$. Then $|X\cap\Gamma|=1$ (by definition of $g$-wildcard), say $X\cap\Gamma=\{a\}$. Let $Y$ be the set obtained from $X$ by substituting $a$ with $b$. Then $Y\in c$ by definition of 01g-row. In particular $Y\in EHS(\mathbb{H})$, and so for any hyperedge $K_i$ with $b\in K_i$ we have $Y\cap K_i=\{b\}$. Therefore for all $K_i\in\mathbb{H}$ it holds that

 $a\in K_i\Leftrightarrow X\cap K_i=\{a\}\ \Leftrightarrow
      \ Y\cap K_i=\{b\}\Leftrightarrow b\in K_i.$

 Therefore $a$ and $b$ are $\mathbb{H}$-equivalent. One concludes that each $g$-bubble of each final row is {\it contained} in an $\mathbb{H}$-class.
 Suppose the representation of $EHS(\mathbb{H})$ via $01g$-rows originated from the $g$-algorithm.
 Then, by (4), each $g$-bubble actually {\it is} an $\mathbb{H}$-class.

  In particular, when applying the $g$-algorithm to a nondegenerate hypergraph, each final $01g$-row must be a $01$-row (=bitstring).
  For instance, applying the  $g$-algorithm to the nondegenerate hypergraph $\overline{\mathbb{H}_1}$ would  give the final $01$-rows in the left part of Table 3:

  \begin{tabular}{l|c|c|c|c|c|c |c|c|c|c|c|c |c|c|c|c}
 	& $\overline{1}$ & $\overline{2}$ & $\overline{3}$ & $\overline{6}$  & $\overline{8}$&    & 1&5&7&2&3&4&6&8&9&\\ \hline
 	& & & & & &  & & & & & & & & & &  \\ \hline
 	 &  1 & 0 & 0 & 1& 1&$\Rightarrow$  &$g_1$ &$g_1$ &$g_1$ &0 &0 &0 &1 &$g_2$ &$g_2$ &$\ =c_3$    \\ \hline

	&  0 & 0 & 1 & 0& 1&$\Rightarrow$  &0 &0 &0 &0 &$g$ &$g$ &0 &$g$ &$g$ &$\ =c_4$    \\ \hline
	&  0 & 1 & 0 & 0& 0&$\Rightarrow$  &0 &0 &0 &1 &0 &0 &0 &0&0 &$\ =c_5$    \\ \hline
 \end{tabular}

{\sl Table 3: The $g$-algorithm necessarily enumerates $EHS(\overline{\mathbb{H}_1})$ one-by-one}

 One retrieves the final rows $c_3,c_4,c_5$ in Table 1 by inflating each $1$ at position $\overline{k}$ to a $g$-wildcard as large as the
 class $\overline{k}$ (with the understanding that $1$ stays $1$ if $\overline{k}$ is a singleton).

 {\bf 3.2} What is the bottom line in all of that? A devil's advocate might argue: For nondegenerate hypergraphs the  $g$-algorithm offers no compression, and for degenerate hypergraphs $\mathbb{H}$ the compression can also be achieved by enumerating the EHSes of $\overline{\mathbb{H}}$ with any {\it other algorithm}, and then inserting $g$-wildcards in a trivial manner.

 Here is the defender's argument: As elementary as they are, the  concepts  'degenerate' and 'nondegenerate' are new.
 Likewise for '$g$-wildcards' and 'Abraham-Flags'. Concerning 'other algorithm',  the author could not google any publication concerning the enumeration of all exact hitting sets of a  general hypergraph. Even concerning specific hypergraphs, the algorithm in [U] seems to be the  only publication.

\section{The minhit e-algorithm: First steps}

In 4.1 we review $e$-wildcards and the transversal $e$-algorithm of [W1] which generates $HS(\mathbb{H})$. In 4.2 and 4.3 (which formulates the 'Main Quest')  first strides are made to refine it to the\footnote{Due to its use in previous publications we stick with 'transversal e-algorithm'. However, 'minhit algorithm' not only fits the notation $MHS(\mathbb{H})$ (see Sec.1) but also sounds better than 'mintransversal e-algorithm'.} 'minhit algorithm' that only generates the minimal members of $HS(\mathbb{H})$. Subsection 4.4 briefly resumes the equivalence relation $\sim$ induced by $\mathbb{H}$.

{\bf 4.1} The $e$-wildcard $(e,e,\ldots,e)$  means 'at least one 1 here'. To spell it out, if there are $t$ symbols $e$, then $2^t-1$ bitstrings are allowed, i.e. all except $(0,0,\ldots,0)$.  The so obtained {\it 012e-rows} are handy generalizations of 012-rows.
Similar to $g$-wildcards (Section 2) we will distinguish distinct $e$-wildcards within a 012e-row by subscripts.
The meaning of $e$-{\it bubbles} matches the meaning of $g$-bubbles. Thus

(5)\quad $r=(2,e_1,e_2,0,1,e_2,0,e_1,2,e_2,1)$

 by definition is the set of  bitstrings $(x_1,\ldots,x_{11})$ which have $x_4=x_7=0$ and $x_5=x_{11}=1$ and $1\in \{x_2, x_8\}$ and $1\in\{x_3, x_6, x_{10}\}$. The values of $x_1, x_9$ being free, the cardinality of $r$ is

(6)\quad $|r|=2^2\cdot(2^2-1)\cdot(2^3-1)=84$.

The (inclusion-)minimal members of $r$ are obtained by setting all 2's to 0 and augmenting $ones(r)$ by all possible transversals of the e-bubbles. Thus for $r$ in (5) the $r$-minimal sets are\footnote{Here the ordering of the sets is 'lexicographic' with respect to the ordering of the (indices of) e-bubbles and the natural ordering $[w]=\{1,2,..,w\}$. However, the ordering is irrelevant.}

$\{5,11,{\bf 2},3\},\{5,11,{\bf 2},6\},\{5,11,{\bf 2},10\},\{5,11,{\bf 8},3\},\{5,11,{\bf 8},6\},\{5,11,
{\bf 8},10\}.$

 For a general 012e-row $r$ with $t$ many e-bubbles of cardinalities $\epsilon_1,...,\epsilon_t$ respectively, let $min(r)$ be the family of all $r$-minimal sets. Evidently $|min(r)|=\epsilon_1\cdot \epsilon_2\cdots\epsilon_t$ and
 the {\it degree}

 $(7)\quad deg(r):=|ones(r)|+t$

 equals the common cardinality of all $X\in min(r)$.

{\bf 4.1.1}
Similar\footnote{The most noteworthy difference is the trivial feasibility test for the transversal e-algorithm. It is stated in [W1] but we present a sped-up version of it in 7.3.} to the g-algorithm  in the proof of Theorem 1 the transversal e-algorithm imposes the hyperedges individually one after the other and  renders  $HS(\mathbb{H})$  as disjoint union of  012e-rows. For instance, take the hypergraph $\mathbb{H}_2\subseteq {\cal P}[6]$ with hyperedges

  $(8)\ H_1=\{1,2,5\},\ H_2=\{3,4\},\ H_3=\{4,5,6\},\ H_4=\{1,3,5\},\ H_5=\{2,6\}.$

  It gets represented as

 \begin{tabular}{l|c|c|c|c|c|c|c}
 	& $1$ & $2$ & $3$ & $4$  &$5$  & $6$  & row-minimal sets \\ \hline
 	& & & & & & &  \\ \hline
 	$\rho_4=$ &  $e$ & $e$ & 1 & 0 & 0& 1&  136, 236 \\ \hline
 	$\rho_3=$ &  2 & $e_1$ & $e_2$ & $e_2$ & 1& $e_1$&  235,245,356,456  \\ \hline
 	$\rho_2=$ &  0 & 1 & 1 & 1 & 0& 2&  234  \\ \hline
 	$\rho_1=$ &  $1$ & $e$ & 2 & 1 & 0& $e$&  124, 145  \\ \hline
 \end{tabular}

 {\sl Table 4: Representing $HS(\mathbb{H}_2)$ as disjoint union of final $012e$-rows}

 In the remainder of Section 4 we assume that the transversal e-algorithm has displayed $HS(\mathbb{H})$ as a disjoint union  of $R$ many 012e-rows $\rho_i$, thus

(9)\quad $HS(\mathbb{H})=\biguplus_{i=1}^R \rho_i.$

Instead of final 012e-rows we henceforth speak of {\it semifinal} 012e-rows (or just ' semifinal rows') $\rho_i$ because, different from the final 01g-rows in Section 2, calculating $HS(\mathbb{H})$ is only the beginning.

{\bf 4.2} Recall from Section 1 that $MHS(\mathbb{H})$ is the set of all minimal $\mathbb{H}$-hitting sets. Say $X\in MHS(\mathbb{H})$ happens to be in the  semifinal 012e-row $\rho_i$. Being (globally) minimal, $X$ a fortiori is $\rho_i$-{\it minimal}, i.e. $X\in min(\rho_i)$. It follows from (9) that

(10)\quad $MHS(\mathbb{H})\subseteq\biguplus_{i=1}^R min(\rho_i),\ and\ so\ MSH(\mathbb{H})=\biguplus_{i=1}^R \Big(MHS(\mathbb{H})\cap min(\rho_i)\Big).$

In the sequel $\rho=\rho_i$ is any semifinal 012e-row. We put

(11)\quad  $MHS(\rho):=min(\rho)\cap MHS(\mathbb{H})\quad (=\rho\cap MHS(\mathbb{H}))$

 and call $\rho$ {\it bad} if $MHS(\rho)=\emptyset$, and {\it good} otherwise. Additionally call $\rho$  {\it very-good} if $MHS(\rho)=min(\rho)$, and call $\rho$  {\it merely-good} if it is good but not very-good. It is catchy to call $min(\rho)$ the {\it promise} of $\rho$, and call each $X\in min(\rho)\setminus MHS(\rho)$  a {\it dud}. Note that for 012-rows it holds that $good\Leftrightarrow$ $very$-$good$.

{\bf 4.2.1} The {\it naive dud-test} applied to $X\in min(\rho)$ checks whether any
   of its $\le w$ many subsets $Y=X\setminus\{a\}\ (a\in X)$ is an $\mathbb{H}$-transversal. It invests $O(hw)$ time for each $Y$ to calculate all $H\cap Y\ (H\in\mathbb{H})$. Hence one naive dud-test costs already $O(hw^2)$. (A more clever MC-dud-test will be presented later.)

 {\bf 4.2.2} Here comes the most pleasant way  to avoid individual dud-tests. The {\it minimum} size of an $\mathbb{H}$-transversal equals $\mu:=min\{deg(\rho_i):\ 1\le i\le R\}$, and so $\mu$ can be found in $O(Rw)$ time. Evidently all rows $\rho_i$ with $deg(\rho_i)=\mu$ are very-good. Furthermore the union of the corresponding promises
 $min(\rho_j)$ coincides with the set $MHS(\mathbb{H},\mu)$ of all minimum $\mathbb{H}$-transversals.
 The best scenario happens when {\it all} minimal transversals have the {\it same}  cardinality, which hence equals $\mu$. That e.g. happens in Table 4.

 {\bf 4.2.3} More relevant, and well known, $MHS(\mathbb{H})=MHS(\mathbb{H},\mu)$ happens\footnote{Readers aware of  other scenarios of that type, please  let the author know.} whenever $\mathbb{H}$ is the family of all co-circuits of a matroid, in which case  $MHS(\mathbb{H})$ is the set of all matroid bases. This and more has been carried out  in arXiv:2002.09707 for $\mathbb{H}$ being the set of all minimal cutsets of a graph $G$, and hence $MHS(\mathbb{H})$ being the set of all spanning trees of $G$.

 Speaking of work in progress, can the transversal $e$-algorithm be sped up for graphs, i.e. hypergraphs $\mathbb{H}\subseteq {\cal P}[w]$ that have $|H|=2$ for all $H\in \mathbb{H}$? In this scenario it is better not to impose the {\it edges} $H\in \mathbb{H}$ individually, but rather to process the usually fewer {\it vertices} $a\in [w]$. Suppose $a=4$ is adjacent to the vertices $3,5,6$. Instead of imposing the edges $\{4,3\},\{4,5\},\{4,6\}$ upon  $r=(\ast,\ast,2,2,2,2,\ast,...)$ and its successors, we simply replace $r$ by $(\ast,\ast,2,{\bf 1},2,2,\ast,...)\uplus (\ast,\ast,1,{\bf 0},1,1,\ast,...)$. One can condense further by using the wildcard $(\ast,\ast,\beta,\alpha,\beta,\beta,\ast,...)$. In this way all minimal $\mathbb{H}$-hitting sets (aka minimal {\it vertex-covers}) can be generated in compressed format. Of course, it would have been more cumbersome had the four 2's in $r$ been other symbols. Details can be found in the preprint arXiv:0901.4417 which embraces the dual view of maximal anticliques (=complements of minimal vertex-covers).

 {\bf 4.2.4} Trivially, if $\mathbb{H}$ contains $h$ mutually disjoint hyperedges, it triggers exactly one very-good semifinal 012e-row $r$ with $min(r)=MSH(\mathbb{H})$. (And all $X\in min(r)$ are exact hitting sets, see Section 2.) It gets more colorful if the hyperedges are 'almost disjoint'. Thus Table 14 in Section 11 features a hypergraph $\mathbb{H}\subseteq {\cal P}[100]$ having 40 hyperedges of uniform cardinality 3. It triggered 4480 semifinal rows of which 4479 were very-good and jointly contained about $2\cdot 10^{14}$ minimal hitting sets. Specifically, the average degree of a semifinal row was 32, and there were exactly 58'989'951 minimum hitting sets ($\mu=26$).

{\bf 4.3}  With terminology as above, the {\it Main Quest} will be to  design a {\it first grade}
 minhit algorithm which by definition

  \begin{enumerate}
  	\item[{(A)}] {\bf reckognizes} the very-good 012e-semifinal rows (and calls them {\it final}),
  	\item[{(B)}]  {\bf prunes} the bad semifinal rows,
  	\item [{(C)}] {\bf replaces} each  merely-good semifinal row $r$ by a disjoint union of  ({\it final}) very-good rows
  	$\rho_1,...,\rho_n$ such that $MHS(r)=MHS(\rho_1)\uplus\cdots\uplus MHS(\rho_n)$.
  \end{enumerate}

  If the minhit algorithm manages only (A) and (B) (as e.g. in Section 11) then it is {\it second grade}. There are more or less efficient ways to achieve a particular grade. For instance, the {\it naive} first grade minhit algorithm patiently scans the promise of each semifinal row $r$ one-by-one. If $MHS(r)=min(r)$, then $r$ is declared final; this yields (A).  If it turns out that $MHS(r)=\emptyset$ then $r$ is thrown away;
  hence (B) is met. If $r$ happened to be merely-good, say $MHS(r)=\{Z_1,...,Z_n\}$, then let $\rho_1,...,\rho_n$ be the corresponding 01-rows; this yields (C).

   {\bf 4.3.1} The remainder of the article strives to design methods that fulfil (A),(B),(C)  efficiently. Once (A),(B),(C) are satisfied, i.e. all final rows $\rho_i$ are very-good, one can replace them by $01g$-rows $c_i$. This yields a compact representation of $MHS(\mathbb{H})$ as disjoint union of $01g$-rows. Thus  Table 4 yields Table 5.

  \begin{tabular}{l|c|c|c|c|c|c|c}
  	& $1$ & $2$ & $3$ & $4$  &$5$  & $6$  &  \\ \hline
  	& & & & & & &  \\ \hline
  	$c_4=$ &  $g$ & $g$ & 1 & 0 & 0& 1&  $=\{136, 236\}$ \\ \hline
  	$c_3=$ &  0 & $g_1$ & $g_2$ & $g_2$ & 1& $g_1$&  $=\{235,245,356,456\}$  \\ \hline
  	$c_2=$ &  0 & 1 & 1 & 1 & 0& 0&  $=\{234\}$  \\ \hline
  	$c_1=$ &  $1$ & $g$ & 0 & 1 & 0& $g$&  $=\{124, 145\}$  \\ \hline
  \end{tabular}

  {\sl Table 5: Compactly representing $MHS(\mathbb{H}_2)$ as $c_1\uplus c_2\uplus c_3\uplus c_4$.}

   {\bf 4.3.2} Let $\mu\le m\le w$. What about  {\it cut-off} at $m$, i.e. only generating the set $HS(\mathbb{H},\le m)$ of all hitting sets of cardinality $\le m$; respectively the set $MHS(\mathbb{H},\le m)$ of all {\it minimal} hitting sets of cardinality $\le m$? As to the former, this is readily achieved by generalizing\footnote{In a nutshell, by definition $(g(k),...,g(k))$ means 'exactly $k$ many 1's here'. If $m=4$ then the $m$-element sets in $r:=(e,e,e,e,e',e',e')$ are the sets in $(g(3),g(3),g(3),g(3),g,g,g)\uplus (g(2),g(2),g(2),g(2),g'(2),g'(2),g'(2))\uplus (g,g,g,g,1,1,1)$. Similarly proceed for $k<m$.}  $g$-wildcards. As to the latter, $MHS(\mathbb{H},\le m)$  is contained in the disjoint union $S$ of the promises $min(r)$, where $r$ ranges over all semifinal rows with $deg(r)\le m$. (As shown in [W1], the transversal e-algorithm can be trimmed to avoid the generation of semifinal rows of degree $>m$ in the first place.)
  Each row $r$ with $deg(r)\le m$ undergoes the Main Quest.

{\bf 4.4} Recall from Subsection 3.2, if the hypergraph $\mathbb{H}\subseteq {\cal P}[w]$ is nondegenerate, then the  $g$-algorithm necessarily outputs $EHS(\mathbb{H})$ one-by-one. In contrast, the minhit algorithm has the potential to render $MHS(\mathbb{H})$ in a compressed format  even when $\mathbb{H}$ is nondegenerate. For instance, $\mathbb{H}_2$ in (8) is nondegenerate (by inspection) and Table 5 testifies that it can be compressed.

What about enumerating $MHS(\mathbb{H})$ when $\mathbb{H}$ is degenerate? Can (and should) matters be reduced to the nondegenerate case as in  Section 3? To fix ideas, consider $\mathbb{H}_3:=\{K_1,...,K_6\}$ defined by

$K_1:=\overline{1}\cup\overline{2}\cup\overline{5},\ K_2:=\overline{3}\cup\overline{4},\ K_3:=\overline{4}\cup\overline{5}\cup\overline{6},\ K_4:=\overline{1}\cup\overline{3}\cup\overline{5},\
K_5:=\overline{2}\cup\overline{6},$

where

$\overline{1}:=\{1a,1b,1c\},\ \overline{2}:=\{2a,2b\},\ \overline{3}:=\{3a,3b,3c\},\ \overline{4}:=\{4a\},
\ \overline{5}:=\{5a,5b\},\ \overline{6}:=\{6a,6b,6c\}$

are any disjoint sets. In view of (8) it is evident that the reduced hypergraph $\overline{\mathbb{H}_3}$ is isomorphic to  $\mathbb{H}_2$. A compressed representation of $MHS(\mathbb{H}_3)$ is immediately obtained from the compressed enumeration of
$MHS(\overline{\mathbb{H}_3})\simeq MHS(\mathbb{H}_2)$ in Table 5:

\begin{tabular}{l|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
	& 1a &1b&1c&   & 2a&2b& &3a& 3b&3c& &4a & &5a&5b& &6a&6b&6c& \\ \hline

	& & & & & & & & & & & & & & && & & & &  \\ \hline

	$\overline{c_4}=$ & $g_1$ &$g_1$ &$g_1$&  &$g_1$&$g_1$& &$g_2$ & $g_2$&$g_2$ & & 0& &
	0 & 0 & &
	$g_3$  &$g_3$ & $g_3$ & \\ \hline

		$\overline{c_3}=$ & 0 &0 &0&  &$g_1$ &$g_1$& &$g_2$ & $g_2$&$g_2$ & & $g_2$& &
	$g_3$ & $g_3$& &
	$g_1$  &$g_1$ & $g_1$ & \\ \hline

		$\overline{c_2}=$ & 0 &0 &0&  &$g_1$&$g_1$& &$g_2$ & $g_2$&$g_2$ & & 1& &
	0 & 0 & &	0  &0 & 0 & \\ \hline

		$\overline{c_1}=$ & $g_1$ &$g_1$ &$g_1$&  &$g_2$&$g_2$&   &0 & 0&0  & & 1& &
	0 & 0 & &
	$g_2$  &$g_2$ & $g_2$ & \\ \hline

\end{tabular}

{\sl Table 6: Getting $MHS(\mathbb{H}_3)$ from $MHS(\overline{\mathbb{H}_3})$ (in Table 5) by inflating  $g$-symbols and 1's}

 To summarize, for degenerate hypergraphs $\mathbb{H}$ one has the option\footnote{However, different from Section 3 it seems that 'imposing the hyperedges' and 'reducing the hypergraph' are not interchangeable. The precise relationship remains to be clarified. In the sequel (including the numerical experiments in Section 11) neither hypergraph will be reduced. We also will not bother
  to switch from final 012e-rows to 01g-rows. It suffices to remember that 2's become 0's and that exactly one $e$ per $e$-wildcard must be $1$, the others $0$.}
  to first build $\overline{\mathbb{H}}$. Recall from 2.3 that this takes time $O(hw^2)$. Second, represent $MHS(\overline{\mathbb{H}})$ as a disjoint union of 01g-rows (the Main Quest). Third, akin to the transition from Table 5 to Table 6, inflate the result by replacing some $g$-symbols (or 1's) by new $g$-wildcards.
The result is a compressed representation of $MHS(\mathbb{H})$.

\section{Replacing merely-good rows by  very-good rows}

 {\bf 5.1} We are now in a position to survey the remainder of the article in more detail than it was possible in Section 1. Subsections 5.2 and 5.3 tackle part (C) of the Main Quest. Thus we show how each merely-good semifinal 012e-row $r$ can  be decomposed into
rows $r_i$ (its 'sons') which are classified as bad, merely-good, or very-good. The bad ones are thrown away, the very-good ones become final rows, and the merely-good ones recursively undergo the just described treatment.
In the end $r$ gets replaced by a disjoint union of final very-good rows that comprise exactly the same minimal hitting sets.
 Unfortunately it is hard to

  {\bf (i)}  decide  whether a semifinal row is very-good or not;

  and if not, to

  {\bf (ii)}  decide whether it is good or bad.

Because (ii) subsumes (B) in the Main Quest, Section 5 reduces the Main Quest  to the solution of (i) and (ii). As to (i), we offer three methods.
 The first (Section 6) is based on inclusion-exclusion, the second is mentioned in a footnote in 11.2, and the third (Section 8) drives further an idea of Murakami-Uno [MU] who  found a nice  necessary condition (called MC) for a set to be a minimal transversal. Section 9 settles (ii) by developping three increasingly sophisticated badness-tests based on the MC condition. Much depends on a certain set system $MinNotMC$, whose calculation
  is postponed to Section 10. Sections 7 and 11 were sufficiently surveyed in the Introduction.

{\bf 5.2} Consider the hypergraph $\mathbb{H}_4\subseteq{\cal P}[6]$ with hyperedges

(12)\quad $H_1=\{1,5,6\},\ H_2=\{3,4,5\},\ H_3=\{2,3\},\ H_4=\{1,4,6\}.$

Feeding the transversal e-algorithm with $\mathbb{H}_4$ yields (among others) the semifinal row $r$ in Table  7. It is good since it e.g. contains the minimal $\mathbb{H}_4$-hitting set $\{1,2,5\}$. Yet $r$ is not very-good since $\{1,3,5\}\in min(r)\setminus MHS(\rho)$ is a dud (viewing that $\{1,3\}\in HS(\mathbb{H}_4)$).

 \begin{tabular}{l|c|c|c|c|c|c|c}
	& $1$ & $2$ & $3$ & $4$  &$5$  & $6$  &  \\ \hline
	& & & & & & &  \\ \hline
	$r=$ &  $e_1$ & $e_2$ & $e_2$ & $e_1$ & 1& $e_1$&  good (semifinal) \\ \hline
	& & & & & & &  \\ \hline
	$r_1=$ &  {\bf 1} & $e_2$ & $e_2$ & {\bf 0} & 1& {\bf 0}&  not very-good \\ \hline
		$r_2=$ &  {\bf 0} & $e_2$ & $e_2$ & {\bf 1} & 1& {\bf 0}&   very-good \\ \hline
		$r_3=$ &  {\bf 0} & $e_2$ & $e_2$ & {\bf 0} & 1& {\bf 1}&  not very-good \\ \hline\hline
	$r_4=$ &  1 & 1 & 0 & 0 & 1& 0&    \\ \hline
	$r_5=$ &  0 & 1 & 0 & 0 & 1& 1&   \\ \hline
	& & & & & & &  \\ \hline
	$\rho_1=$ &  $e_1$ & {\bf 1} & {\bf 0} & $e_1$ & 1& $e_1$&  very-good  \\ \hline
	$\rho_2=$ &  $e_1$ & {\bf 0} & {\bf 1} & $e_1$ & 1& $e_1$&  not very-good  \\ \hline\hline
	$\rho_3=$ & 0 &0 & 1 & 1 & 1& 0&    \\ \hline
\end{tabular}

{\sl Table 7: Replacing a  good row by very-good rows.}

We strive to replace $r$ by disjoint rows which are very-good and jointly contain the same minimal hitting sets as $r$.
It is natural to start by picking any e-wildcard of $r$, say $(e_1,e_1,e_1)$, and expand $r$ accordingly as $r=r_1\uplus r_2\uplus r_3$ (see Table 7). We call $r_1,r_2,r_3$ the {\it sons} of $r$.
One checks that $\{2,4,5\},\{3,4,5\}\in MHS(\mathbb{H}_4)$, and so $r_2$ is very-good. As to $r_1$, it is merely-good. Specifically,by expanding the second e-wildcard $(e_2,e_2)$ one obtains $r_1=(1,{\bf 0},{\bf 1},0,1,0)\uplus (1,{\bf 1},{\bf 0},0,1,0)$, where the first son (=01-row) is bad since $\{1,3\}\in \mathbb{H}_4$, and the second (call it $r_4$) is very-good. Also $r_3$ is merely-good; it decomposes as
$r_3=(0,{\bf 0},{\bf 1},0,1,1)\uplus (0,{\bf 1},{\bf 0},0,1,1)$, where the first son is bad and the second (call it $r_5$) is very-good. To summarize, we managed to replace the semifinal merely-good row $r$ by the final very-good rows $r_2,r_4,r_5$.

Alternatively, one can start by expanding $(e_2,e_2)$. This yields the rows $\rho_1,\rho_2$ in Table 7. One checks that $\rho_1$ is very-good, but $\rho_2$ is not. Specifically, when expanding $(e_1,e_1,e_1)$ in $\rho_2$, two of the three arising 01-rows are bad.
The third one (labelled $\rho_3$) is very-good. To summarize, $r$ can even be replaced by {\it two} very-good rows, i.e. $\rho_1,\rho_3$.

{\bf 5.3} The example above suggests the following method to replace a semifinal good row $r$ (w.r.t. $\mathbb{H}$) by  final very-good rows that jointly contain the same minimal hitting sets as $r$. There is nothing to do if $r$ is already very-good. By induction assume that a stack is filled with disjoint merely-good 012e-rows which jointly contain exactly the minimal $\mathbb{H}$-hitting sets contained in $r$. (Initially $r$ is the only member of the stack.) Remove the top row $r'$ from the stack. Expanding any e-wildcard of $r'$ yields candidate sons $r_1,r_2,...$ akin to 2.3. The very-good candidate sons are final; they are removed from the stack and stored somewhere else. The bad candidate sons are thrown away, and the merely-good candidate sons are put on top of the stack\footnote{The candidate sons $r_i$ of $r'$ are related to each other, and to their father. Therefore no $r_j$ needs to be evaluated from scratch. Details follow in 9.9.}.
It is clear that the new stack maintains the induction hypothesis. When the stack is empty, the final rows are disjoint
and  jointly contain the same minimal hitting sets as $r$.

\section{Deciding very-goodness using inclusion-exclusion}

Suppose the transversal e-algorithm has processed $\mathbb{H}\subseteq {\cal P}[w]$ and packed $HS(\mathbb{H})$ in a disjoint union of semifinal 012e-rows $r$. In order to state one\footnote{Another criterion follows in Section 8. The numerical examples in Section 11 will indicate which is better when.}  criterion for  $r$ to be very-good, we say that $X\subseteq [w]$ is a {\it potential $r$-spoiler}  if there is a $Y\in min(r)$ with $X\uplus\{a\}=Y$. Different $r$-minimal sets $Y$ and $Y'$ can yield the same potential $r$-spoiler $Y\setminus\{a\}=Y'\setminus\{b\}$, but only if $a,b$ belong to the same $e$-bubble. We  conclude that:

(13)\quad With $\epsilon_i$ as in 4.1, the number of potential $r$-spoilers of a final 012e-row $r$ is\\ \hspace*{1cm} $Pot=(\epsilon_2\cdots\epsilon_t)+(\epsilon_1\epsilon_3\cdots\epsilon_t)+\cdots+(\epsilon_1\cdots\epsilon_{t-1})+|ones(r)|\cdot\epsilon_1\cdots\epsilon_t$.

In Table 8  the set system of all potential $r$-spoilers of some 012e-row $r$ is represented  as disjoint union $d_1\uplus\cdots\uplus d_5$ of 01g-rows. Its cardinality is $24+\cdots+6=74$. Attention: Do not confuse this kind of 01g-rows $d_i$ with the kind of 01g-rows $c_i$ in Subsection 4.3.

\begin{tabular}{l|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}

	&1 &2 & &3 & &4 &5 &6 & &7& &8 &9 &10 &11&  &12 &13& cardinality   \\ \hline

		& & &  & & & & & & & & & & & & & & & & & \\ \hline
	$r=$ &  $e_1$ &  $e_1$ & & $0$& &  $e_2$ &  $e_2$ &  $e_2$& &$2$&  &  $e_3$&  $e_3$ &  $e_3$ &  $e_3$ &  & $1$ &  $1$ & 630   \\ \hline

	& & & & & & & & & & & & & & & & & & & \\ \hline
	$d_1=$ &  $g_1$ &  $g_1$ & & $0$ & & $g_2$ &  $g_2$ &  $g_2$& &$0$&  &  $g_3$&  $g_3$ &  $g_3$ &  $g_3$ & & ${\bf 0}$ &  $1$ & 24   \\ \hline

	$d_2=$ &  $g_1$ &  $g_1$ & & $0$ & & $g_2$ &  $g_2$ &  $g_2$& &$0$&  &  $g_3$&  $g_3$ &  $g_3$ &  $g_3$ &  &$1$ &  ${\bf 0}$  & 24  \\ \hline

	$d_3=$ &  ${\bf 0}$ &  ${\bf 0}$ & & $0$ & & $g_2$ &  $g_2$ &  $g_2$& &$0$&  &  $g_3$&  $g_3$ &  $g_3$ &  $g_3$ &  &$1$ &  $1$ & 12   \\ \hline

	$d_4=$ &  $g_1$ &  $g_1$ & & $0$ & & ${\bf 0}$ &  ${\bf 0}$ &  ${\bf 0}$ & &$0$&  &  $g_3$&  $g_3$ &  $g_3$ &  $g_3$ &  &$1$ &  $1$  & 8  \\ \hline

	$d_5=$ &  $g_1$ &  $g_1$ & & $0$ & & $g_2$ &  $g_2$ &  $g_2$& &$0$&  &  ${\bf 0}$&  ${\bf 0}$ &  ${\bf 0}$ &  ${\bf 0}$ &   &$1$ &  $1$ & 6   \\ \hline

	& & & & & & & & & & & & & & & & & & &\\ \hline
	$\delta_1=$ &  $g_1$ &  $g_1$ & & $0$ & & $1$ &  {\bf 0} &  {\bf 0}& &
	{\bf 0}&  &  {\bf 0}&  {\bf 0} &  $g_3$ &  $g_3$ & & $0$ &  $1$ & 4   \\ \hline

	$\delta_2=$ &  $g_1$ &  $g_1$ & & $0$ & & $1$ &  {\bf 0} &  {\bf 0}& &
	{\bf 0}&  &  {\bf 0}&  {\bf 0} &  $g_3$ &  $g_3$ & & $1$ &  $0$ & 4   \\ \hline

	$\delta_3=$ &  $0$ &  $0$ & & $0$ & & $1$ &  {\bf 0} &  {\bf 0}& &
	{\bf 0}&  &  {\bf 0}&  {\bf 0} &  $g_3$ &  $g_3$ & & $1$ &  $1$ & 2   \\ \hline

	$\delta_4=$ &  $g_1$ &  $g_1$ & & $0$ & & $0$ &  {\bf 0} &  {\bf 0}& &
	{\bf 0}&  &  {\bf 0}&  {\bf 0} &  $g_3$ &  $g_3$ & & $1$ &  $1$ & 4   \\ \hline

	$\delta_5=$ &  $g_1$ &  $g_1$ & & $0$ & & $1$ &  {\bf 0} &  {\bf 0}& &
	{\bf 0}&  &  {\bf 0}&  {\bf 0} &  $0$ &  $0$ & & $1$ &  $1$ & 2   \\ \hline

	\end{tabular}

{\sl Table 8: Counting  $r$-spoilers by  applying inclusion-exclusion}

{\bf 6.1} For a general semifinal $r$ we define an {\it $r$-spoiler} as a potential $r$-spoiler that happens to be a $\mathbb{H}$-transversal. A moment's reflection confirms:

(14)\quad The final $012e$-row $r$ is very-good  iff there are no  $r$-spoilers.

We define say $N(i,j,k)$  as the number of potential $r$-spoilers $X$ with $X\cap H_i=X\cap H_j=X\cap H_k=\emptyset$.  Since a potential spoiler is a spoiler iff it cuts all hyperedges of $\mathbb{H}$,
we can compute the number $Sp$ of $r$-spoilers with inclusion-exclusion as

(15)\quad $Sp=Pot-N(1)-N(2)-\cdots -N(h)+N(1,2)+\cdots+(-1)^h N(1,2,..,h)$.

According to (14) row $r$ is very-good iff $Sp=0$. Calculating $2^h$ terms $N(..)$ may seem inefficient but
the larger $min(r)$ and $w$, and the smaller $h$, the more inclusion-exclusion will prevail over
  the naive way which, according to 4.2.1, spends $O(hw^2)$ time per $X\in min(r)$.

{\bf 6.2}  Furthermore, based on the first three {\bf B}on{\bf f}erroni inequalities (google) these implications often alleviate full-blown inclusion-exclusion:

\begin{enumerate}
\item[{(Bf1)}] $Pot-N(1)-\cdots -N(h)>0\ \Rightarrow\ Sp>0$

\item[{(Bf2)}] $Pot-N(1)-\cdots -N(h)+N(1,2)+\cdots +N(h-1,h)=0\ \Rightarrow\ Sp=0$

\item[{(Bf3)}] $Pot-N(1)-\cdots +N(1,2)-N(1,2,3)-\cdots -N(h-2,h-1,h)>0\ \Rightarrow\ Sp>0$
\end{enumerate}

To illustrate (Bf1), suppose $\mathbb{H}_4=\{H_1,\cdots,H_4\}\subseteq {\cal P}[13]$ is any hypergraph such that $12\in H_1,\ 13\in H_2,\ 12,13\in H_3$ and $H_4:=\{5,6,7,8,9\}$. Then  for all $i\neq 1$ we have $12\in H_1\cap X$ for all $X\in d_i$ (see Table 8). Hence $N(1)\le |d_1|=24$. Similarly $N(2)\le |d_2|=24$. Further $N(3)=0$ since
$H_3\cap X\supseteq \{12,13\}\cap X\neq\emptyset$ for all $X\in d_i$ and $i\in [5]$.
As to $N(4)$, see Table 8 for a compressed representation of the set systems
$\delta_i:=\{X\in d_i:\ X\cap H_4=\emptyset\}$ for $1\le i\le 5$. It follows that $N(4)=4+4+2+4+2=16$, and so

$Pot-N(1)-N(2)-N(3)-N(4)\ge 74-24-24-0-16=10>0$.

Therefore (Bf1) and (14) imply that $r$ is not\footnote{Generally $N(i_1,...,i_t)$ is the number of potential spoilers $X$ with $X\cap H_{i_1}=\cdots =X\cap H_{i_t}=\emptyset$. But this is equivalent to $X\cap (H_{i_1}\cup\cdots \cup H_{i_t})=\emptyset$. Hence, as in the lower part of Table 8, in order to calculate $N(i_1,...,i_t)$ it suffices to set exactly those columns to zero whose indices are in $H_{i_1}\cup\cdots\cup H_{i_t}$.} very-good.

{\bf 6.3} But $r$ is likely still good. To make this more precise, let us generally order the sizes of the $e$-wildcards occuring in $r$ as $\epsilon_1\le\cdots\le\epsilon_t$. Then each $r$-spoiler $X$ can prevent at most $\epsilon_t$ many $r$-minimal sets from being minimal transversals.  Since the number of $r$-minimal sets is $(\epsilon_1\cdots\epsilon_{t-1})\epsilon_t$, we conclude:

(16)\quad If $\epsilon_1\le\cdots\le\epsilon_{t-1}\le\epsilon_t$ and the number $Sp$ of $r$-spoilers is smaller\\ \hspace*{1.1cm} than $\epsilon_1\cdots\epsilon_{t-1}$, then $r$ is good.

Although the bound $\epsilon_1\cdots\epsilon_{t-1}$ is sharp, let us argue that even for significantly higher values of $Sp$ the row $r$ is  likely good. To fix ideas, let $ones(r)=\emptyset$ and $\epsilon_1=\epsilon_2=\epsilon_3=\epsilon_4=3$. The probabilities 'prob(good)' for $r$ being good (despite $Sp$ being larger than
$\epsilon_1\cdots\epsilon_{t-1}=27$) were approximated by computer simulation\footnote{For example $\approx 0.27$ in Table 9 was obtained as follows. From the pool of 108 $r$-spoilers we picked 100'000 times subsets $S$ of cardinality 80 and tested whether some minimal $r$-sets survived the attack of the members of $S$. This was the case 27'309 times.} and are as follows:

\begin{tabular}{l|c|c|c|c|c|c|c|c}
		$Sp=$ &  26 &  57 & 70 & 80&90 &  100 &  105     \\ \hline
		$prob(good)$ &  $=1$ &  $\approx 0.99$ & $\approx 0.70$ &
		 $\approx 0.27$&$\approx 0.05$ &  $\approx 0.001$ &  $=0$     \\ \hline
\end{tabular}

{\sl Table 9: The probability that $r$ is good in dependence of $Sp$}

As to $Sp=105$ in Table 9, one has $Pot=\epsilon_1\epsilon_2\epsilon_3+\epsilon_1\epsilon_2\epsilon_4+\epsilon_1\epsilon_3\epsilon_4+\epsilon_2\epsilon_3\epsilon_4=108$ because of $ones(r)=\emptyset$ and  (14). Hence $Sp\le 108$. If $Sp=104$ then the four missing $r$-spoilers could be the 3-element subsets of some $X\in min(r)$. In this case $X$ is a minimal $\mathbb{H}$-transversal, and so $r$ is good. Thus $r$ is {\it guaranteed} to be bad only when $105\le Sp\le 108$.

\section{The benefits of Vertical Layout}

After introducing the basic idea of Vertical Layout, we discuss specific applications in Subsections 7.1 to 7.3. They concern topics of our article that were dealt with already (in Sections 3 and 4), but also that lie ahead (Section 10).

Recall that the binary operation $\vee$ ("or") on the symbols $1\ (=True)$ and $0\ (=False)$ satisfies $0\vee1=1\vee 0=1\vee 1=1$
and $0\vee 0=0$. Calculating component-wise the operation extends to bitstrings of the same length. Adopting Mathematica terminology we call this operation $BitOr$. For instance, referring to the columns of the 0,1-matrix  with rows $Y_1'$ to $Y_8'$ (Table 10), it holds that
$BitOr(col_1,col_5)=(1,1,1,1,1,1,0,0)^T$ (where the $T$ means 'transposed').

\begin{tabular}{l|c|c|c|c|c|c|}
	& $col_1$ & $col_2$ & $col_3$ & $col_4$  &$col_5$  & $col_6$     \\ \hline
	& & & & & &   \\ \hline\hline
	$Y_1'=$ &  1 & 1 & 1 & 0 & 0& 0  \\ \hline
	$Y_2'=$ &  1 & 0 & 0 & 0 & 1& 0  \\ \hline
	$Y_3'=$ &  1 & 1 & 0 & 0 & 0& 1  \\ \hline
	$Y_4'=$ &  0 & 1 & 0 & 0 & 1& 1  \\ \hline
	$Y_5'=$ &  1 & 0 & 1 & 1 & 0& 0  \\ \hline
	$Y_6'=$ &  0 & 0 & 1 & 1 & 1& 0  \\ \hline
	$Y_7'=$ &  0 & 0& 1 & 1 & 0& 1  \\ \hline
	$Y_8'=$ &  0 & 1 & 0 & 1 & 0& 1  \\ \hline\hline
	& & & & & &   \\ \hline
	$\rho_2=$ &  0 & 1 & 1 & 1 & 0& 2  \\ \hline
	$\rho_4=$ &  $e$ & $e$ & 1 & 0 & 0& 1  \\ \hline
\end{tabular}

{\sl Table 10: Applying BitOr to the columns of a 0,1-matrix}

Consider now the set system

 $(17)\quad {\cal G}:=\{\{1,2,3\},\{1,5\},\{1,2,6\},\{2,5,6\},\{1,3,4\},\{3,4,5\},\{3,4,6\},\{2,4,6\}\}.$

The straightforward (='horizontal') way to see whether $X=\{1,2,5\}$ is a ${\cal G}$-transversal checks whether any intersection $X\cap Y\ (Y\in {\cal G})$ is empty. In contrast, {\it Vertical Layout (VL)} demands\footnote{We omit the the history of VL (see e.g. arXiv:2002.09707) and delve into medias res.}  to build the 0,1-matrix $M({\cal G})$ whose $i$th row $Y_i'$ is the characteristic bitstring of the $i$th set $Y_i$ listed in (17). It happens that $M({\cal G})$ is given in Table 10. A moment's reflection confirms the following. The fact that
 $BitOr(col_1,col_2,col_5)=(1,1,1,1,1,1,0,1)^T$
  does not equal $ (1,1,1,1,1,1,1,1)^T=:{\bf \vec{1}}$, is tantamount to $X$ not being a ${\cal G}$-transversal ($X\cap Y_7=\emptyset$).  Although the formal complexities of the horizontal and vertical way  coincide (for whatever task), VL is much faster when $\mathbb{H}$ gets large. Simply put, computer hardware prefers doing few operations with long bitstrings to doing many operations with short bitstrings.

{\bf 7.1} Let ${\cal S}\subseteq {\cal P}[w]$ be any set system. The problem to sieve the minimal members of ${\cal S}$ occurs frequently in discrete mathematics. To the author's best knowledge, the following VL-based method, as natural at it is, has not appeared in the literature before (not even in Donald Knuth's books). We will update a family $Min$ until it contains exactly the minimal members of ${\cal S}$. Start by grouping the members of ${\cal S}$ according to their cardinalities $m_1<m_2<\cdots <m_s$. Initially $Min$ is filled with all sets $X\in {\cal S}$ having $|X|=m_1$. By induction assume that $Min$ contains exactly the minimal members of ${\cal S}$ whose cardinalities belong to $\{m_1,\ldots,m_i\}$. As defined above build the 0,1-matrix of dimension $|Min|\times w$ coupled to the set system $Min$.
Let $col[1],...,col[w]$ be its columns. For each $Y\in {\cal S}$ with $|Y|=m_{i+1}$ do the following. For the sake of notation say  the characteristic bitstring of $Y$ is $(0,0,1,...,1,0,0)$ (thus having exactly four 0's). Then $Y$  is a minimal member of ${\cal S}$ iff
$BitOr(col[1],col[2],col[w-1],col[w])={\bf \vec{1}}$. Only in the latter case $Y$ is added to $Min$. Once all $Y$'s with $|Y|=m_{i+1}$ have been processed, the inflated set $Min$  satisfies the induction hypothesis for
$\{m_1,\ldots,m_{i+1}\}$. When one arrives at $\{m_1,\ldots,m_{s}\}$ then $Min$ contains exactly the minimal members of ${\cal S}$, and thus can be labelled $Min({\cal S})$.

{\bf 7.1.1} Recall from 4.2.2 that the hitting sets of minimum cardinality $\mu$ are found immediatly. Thus let ${\cal S}$ be the union of all semifinal rows of degrees, say, $\mu\ or\ \mu+1\ or\ \mu+2$. Then $Min({\cal S})=MHS(\mathbb{H},\le \mu+2))$ (cut-off) can be calculated as shown above. This does not involve $\mathbb{H}$ and is efficient if ${\cal S}$ is moderate. What is more, it is a {\it first grade} minhit algorithm (albeit one-by-one), whereas some of the upcoming methods are second grade. Interestingly, for the upcoming methods some {\it other}
 type of set system  ${\cal S}$ needs to be minimized (in order to get a certain set system $MinNotMC$).

 {\bf 7.2} Here comes an application of Vertical Layout to the hypergraphs $\mathbb{H}\subseteq {\cal P}[w]$ of Section 3. Scanning all subsets $I\subseteq [w]$ in order to calculate the $\mathbb{H}$-equivalence classes is expensive. Instead build the 0,1-matrix of dimension $h\times w$ whose $i$th row is the characteristic bitstring of the $i$th hyperedge. Let $col[1]$ to $col[w]$ be the columns of this matrix. Notice that $BitOr(col[1],col[k])=col[1]$ iff the 1's of $col[k]$ constitute a {\it subset} of the 1's in $col[1]$. Likewise $BitAnd(col[1],col[k])=col[1]$ iff the 1's of $col[k]$ constitute a {\it superset} of the 1's in $col[1]$.
 It follows that $1\sim k$ iff ($BitOr(col[1],col[k])=col[1]$ and $BitAnd(col[1],col[k])=col[1]$). In this way the $\sim$class $\overline{1}$ can be determined. Next pick any $j\in [w]\setminus \overline{1}$ and determine $\overline{j}$ likewise. And so forth.

 {\bf 7.3} Here comes an application of VL to feasibility testing. Suppose that during the transversal e-algorithm (4.1.1) the top row $r$ of the working stack has been replaced by its candidate sons $r_1,r_2,..$. Then each $r_i$ should (unless this gets too expensive, see 2.3)  undergo a feasibility test, i.e. it must be checked whether $r_i$ contains at least one hitting set $X$. This is much easier than deciding the existence of an {\it exact} hitting set  because such $X$ exists iff no hyperedge $H$ is a subset of $Z:=zeros(r_i)$; indeed then $X:=[w]\setminus Z$ does the job. Vertical Layout speeds up matters. Namely, refering to the terminology of 7.2, suppose that $Z=\{1,2,3,4\}$. Then $r_i$ contains a hitting set iff
 $BitOr(col[5],col[6],..,col[w])=(1,1,...,1)^T$.

\section{Deciding very-goodness with the MC-condition}

The MC-condition of [MU] gives rise to a certain set system $MinNotMC(\mathbb{H})$ in 8.1. Using it (and preferably combining it with VL) one can  decide both very-goodness  (8.2) and  badness (Section 9) of semifinal rows. How to calculate $MinNotMC(\mathbb{H})$ in the first place is the theme of Section 10.

{\bf 8.1} Let $T$ be an $\mathbb{H}$-transversal of some fixed hypergraph $\mathbb{H}\subseteq {\cal P}[w]$. Suppose $b\in T$ is such that for each $H\in\mathbb{H}$ it follows from $b\in H\cap T$ that $|H\cap T|\ge 2$. Then $T\setminus\{b\}$ is still a transversal; in particular $T$ was not minimal. This prompts the following terminology adopted from [MU]. For {\it any} set $S\subseteq [w]$ and any $b\in S$,
the hyperedge $H$ is {\it critical for $b$} if $S\cap H=\{b\}$. Let $crit(b,S):=\{H\in\mathbb{H}:\ S\cap H=\{b\}\}$ be\footnote{More precise (but clumsy) is the notation $crit(b,S;\mathbb{H})$.} the set of all   hyperedges critical for $b$.

(18)\quad {\it If $T\subseteq [w]$ happens to be an $\mathbb{H}$-transversal and $a\in [w]\setminus T$, then $crit(a,T\cup\{a\})=\emptyset$.}

To see why, by the fullness of $\mathbb{H}$ there are hyperedges $H\in \mathbb{H}$ with $a\in H$, and any such $H$ also contains an element (by assumption $\neq a)$ of $T$ since $T$ is a transversal. Thus $|H\cap T|\ge 2$, and so $H$ is not critical for $a$.

We say  $S\subseteq [w]$ is a {\it MC-set}, or   $S$ {\it is MC}, if $crit(b,S;\mathbb{H})\neq\emptyset$ for all $b\in S$. It is evident that a subset of a MC-set is again a MC-set. Hence the family

(19)\quad $MC(\mathbb{H}):=\{S\subseteq [w]:\ S\ is\ MC\}$ {\it is a set ideal.}

As seen above, each minimal transversal $T$ is MC. In view of (18) we further conclude that each minimal transversal is a {\it maximal} member of $MC(\mathbb{H})$.
This, up to terminology, was first observed in [MU]. It can also be stated as follows:

(20) \quad  $HS(\mathbb{H})\cap MC(\mathbb{H})=MHS(\mathbb{H}).$

We stress that being a MC-set, even  a maximal one, is not sufficient for being a minimal transversal, only necessary\footnote{This explains the acronym MC which, according to Murakami and Uno, stands for 'Minimal Condition'. }. For instance take $\mathbb{H}:=\{\{1,3\},\{2,4\},\{3,4\}\}$.
One checks that $T=\{1,2\}$ is a maximal MC-set yet not an $\mathbb{H}$-transversal.

(21)\quad $MHS(r)=min(r)\cap MC(\mathbb{H})=r\cap MC(\mathbb{H}).$

{\it Proof of (21).} From definition (11) and $r\subseteq HS(\mathbb{H})$ and (20) follows $r\cap MC(\mathbb{H})\subseteq MHS(r)$. From (11) and (20) follows $MHS(r)\subseteq min(r)\cap MC(\mathbb{H})$. And $ min(r)\cap MC(\mathbb{H})\subseteq  r\cap MC(\mathbb{H})$ is trivial. $\square$

Because $MC(\mathbb{H})\subseteq {\cal P}(W)$ is a set ideal by (19), the set system ${\cal F}:={\cal P}(W)\setminus MC(\mathbb{H})$ is a {\it set filter}, i.e. from ($Y\in {\cal F}$ and $Y\subseteq Z$) follows $Z\in{\cal F}$. Letting $MinNotMC(\mathbb{H})$ be the set of minimal members of ${\cal F}$ (its {\it generators}), one concludes that

(22)\quad $(\forall Z\in {\cal P}(W))\ \Big( Z\in MC(\mathbb{H})\Leftrightarrow (\forall Y\in MinNotMC(\mathbb{H}))\ Y\not\subseteq Z\Big).$

By (21), any $Z\in min(r)$ is a minimal $\mathbb{H}$-transversal iff $Z\in MC(\mathbb{H})$, which  by (22) is equivalent to $Y\not\subseteq Z$ for all $Y\in MinNotMC(\mathbb{H})$. It thus follows:

 (23)\quad The semifinal 012e-row $r$ is very-good iff $ (\forall Z\in min(r))(\forall Y\in MinNotMC(\mathbb{H}))\ Y\not\subseteq Z.$

 While $MinNotMC(\mathbb{H})$ may be large, Vertical-Layout will alleviate matters. What is more, the promise $min(r)$ needs not be scanned one-by-one.

{\bf 8.2}  Let us illustrate this further.  As we will see in Section 10, it holds that (using shorthand notation)

(24)\quad  $MinNotMC(\mathbb{H}_2)=\{123,15,216,256,314,345,436,624\}.$

Reconsider the $\mathbb{H}_2$-semifinal rows $\rho_2$ and $\rho_4$ of Table 10.  Due to foresight the $8\times 6$ matrix in Table 10 coincides with the
01-matrix of $MinNotMC(\mathbb{H}_2)$.
The easier row to test is $\rho_2$ because $min(\rho_2)$ only contains $ones(\rho_2)=\{2,3,4\}=:Z$. One proceeds as in Section 7  to check that $Z$ does not contain any set  $Y_i\in MinNotMC(\mathbb{H}_2)$. Consequently $Z$ is a minimal transversal, i.e. $\rho_2$ is very-good.

 For a fixed semifinal 012e-row $r$ call $Y\in MinNotMC(\mathbb{H})$ {\it harmless}  if $Y\not\subseteq Z$ for all $Z\in min(r)$; and call $Y$ a {\it killer} otherwise. As to $\rho_4$,
if $ones(Y_i')\cap (zeros(\rho_4)\cup twos(\rho_4))\neq \emptyset$, then $Y_i$ in Table 10 cannot be in any member of $min(\rho_4)$, i.e. $Y_i$ is harmless. Because of $zeros(\rho_4)\cup twos(\rho_4)=\{4,5\}$ one calculates $BitOr(col_4,col_5)$ in Table 10 and finds that the latter $Y_i$'s are the ones with $i\not\in \{1,3\}$. Hence at most $Y_1=\{1,2,3\}$ and $Y_3=\{1,2,6\}$ are killers. But neither is contained in a member of $min(\rho_4)=\{136,236\}$, and so\footnote{Generally speaking, let $Y\in MinNotMC(\mathbb{H})$ be such that $ones(Y')\cap (zeros(r)\cup twos(r))=\emptyset$. Then $Y$ is harmless iff $Y$ cuts some e-bubble of $r$ in $\ge 2$  elements. This condition can again  be tested fast with VL but $BitOr$ needs to be replaced by ordinary addition (+) of columns (try).  } $\rho_4$ is very-good.

\section{Three badness-tests based on  the MC-condition}

Testing the badness of a semifinal row $r$ is harder than testing very-goodness. Our first test (9.1) simply scans $min(r)$ one-by-one, yet with a dud-test more clever than the naive one in 4.2. The other badness-tests are based on this characterization of badness (compare with (23)):

 (25)\quad {\it The semifinal 012e-row $r$ is bad iff} $ (\forall Z\in min(r))(\exists Y\in MinNotMC(\mathbb{H}))\ Y\subseteq Z.$

  After the  second badness-test (9.2 and 9.3) the third test and its prelimimaries occupy all of 9.4 to 9.8. There we switch from $Ki(r)\subseteq MinNotMC(\mathbb{H})$  to a certain subset $NC(Ki(r))\subseteq MC(\mathbb{H})$  which we render in a compressed format. All three badness-tests have their pros and cons. In 9.9 we fill in the details that were left out in 5.3 (concerning the transition from merely-good rows to very-good rows).

  {\bf 9.1}. Let $\mathbb{H}\subseteq {\cal P}[w]$. The naive dud-test of cost $O(hw^2)$ now gives way to a {\it MC-dud-test} of cost $O(hw)$. Namely, fix $Z\in min(r)$. Because $Z$ is no dud iff it is MC (see (20)), we calculate all intersections $Z\cap H\ (H\in \mathbb{H})$. Starting with $T:=\emptyset$ we update the test set $T:=T\cup(Z\cap H)$ whenever $|Z\cap H|=1$. As soon as $T=Z$ occurs, we know that $Z$ is a minimal hitting set. If  $T$ never reaches $Z$, then $Z$ is a dud. By definition the {\it first badness-test} decides the badness of $r$ by testing each $Z\in min(r)$ with the MC-dud-test.

  {\bf 9.1.1}  When $min(r)$ is very large then the following VL-implementation of the first badness-test pays off. For fixed $a\in [w]$ call $Z\in min(r)$ an $a$-{\it dud} if $crit(a,Z)=\emptyset$. If $D_a$ is the set of all $a$-duds, then $r$ is bad iff $\bigcup\{D_a:\ a\in [w]\}=min(r)$. As to calculating $D_a$, only sets $Z$ with $a\in Z$ risk being in $D_a$. Hence let $M[a]$ be the 0,1-matrix whose rows are the characteristic bitstrings of all $Z\in min(r)$ with $a\in Z$. For fixed $H\in\mathbb{H}$ with $a\in H$ let $D_a(H)$ be the set of all '$H$-duds', i.e. all above $Z$ with $|H\cap Z|\ge 2$. With the background  from Section 7 the reader will readily see how combining the columns of $M[a]$ yields $D_a(H)$ (more precisely: the indices of the members in $D_a(H)$). Evidently $D_a=\bigcap\{D_a(H):\ a\in H\in \mathbb{H}\}$.

 {\bf 9.2} Recall from 8.2 that the set $Ki=Ki(r)$ of all killers $Y\in MinNotMC(\mathbb{H})$
 can be determined with Vertical-Layout, and that $r$ is very-good iff $Ki=\emptyset$. In contrast, $r$ is bad iff each $Z\in min(r)$ is killed by at least one $Y\in Ki$.

  Let us illustrate the  two basic types of bad rows. For some random
 hypergraph $\mathbb{H}_5\subseteq {\cal P}[40]$ there was a $\mathbb{H}_5$-semifinal row $r^*$ which suffered a {\it super-killer} $Y^*\in Ki(r^*)$ in the sense that $Y^*\subseteq ones(r^*)$.
 Then $Y^*\subseteq ones(r^*)\subseteq Z$ for all $Z\in min(r^*)$, and so $r^*$ is bad. Generally $r^*$ has a superkiller iff\footnote{If there is a superkiller $Y\subseteq ones(r^*)$, then with $Y$ also $ones(r^*)$ is not MC. Conversely if $ones(r^*)$ is not MC, then there are subsets $Y\subseteq ones(r^*)$ with $Y\in MinNotMC(\mathbb{H})$. Notice that each semifinal 012-row is either very-good or superkilled.}$ones(r^*)$ is not a MC-set (as detected by the MC-dud-test). A bad row $r'$ without a superkiller will be called {\it sophisticated-bad}. As an example take
  the $\mathbb{H}_5$-semifinal row $r'$ of degree 7 and promise size  $|min(r')|=2^3\cdot 3=24$ that had

 (26)\quad {\it $ones(r')=\{17,19,24\}$, and e-bubbles  $\{6,28\},\{8,32\},\{16,33\},\{27,29,39\}$,\\ \hspace*{0.8cm} and $Ki(r')=\{Y_1,Y_2,Y_3,Y_4\}:=\{\{8,17,24\},\{8,19,24\},\{6,19,32\},\{19,28,32\}  \}$.}

 Here $Y_1$ kills (exactly) the twelve $r'$-minimal sets of type $\{{\bf 17},19,{\bf 24}\}\cup\{a,{\bf 8},c,d\}$, $Y_2$ kills the  sets of type $\{17,{\bf 19},{\bf 24}\}\cup\{a,{\bf 8},c,d\}$, i.e. the
  {\it same} as before, $Y_3$ kills the six sets of type $\{17,{\bf 19},24\}\cup\{{\bf 6,32},c,d\}$, and $Y_4$ the six sets of type $\{17,{\bf 19},24\}\cup\{{\bf 28, 32},c,d\}$.
 Since these sets happen to be either identical or disjoint, it follows from $12+6+6=|min(r')|$ that  $min(r')$ gets killed entirely.

 {\bf 9.3} The above suggests the following badness-test. As we saw, for each semifinal 012e-row $r$ it holds that
 each killer $Y\in Ki=Ki(r)$ satisfies (a) $Y\cap (zeros(r)\cup twos(r))=\emptyset$, and (b) $Y$ cuts each $e$-bubble of $r$ in at most one element. Thus, if $Ki[j]$ contains the killers that cut exactly $j$ many $e$-bubbles, then $Ki=Ki[0]\uplus Ki[1]\uplus\cdots\uplus Ki[t]$. The set $Ki[0]$ of super-killers needs not be calculated explicitely. As seen above $r$ is {\it superkilled} iff $ones(r)$ is not a MC-set. Otherwise $r$ is either sophisticated-bad or 'actually-good'. To find out,
  the  second most effective killers are the ones in $Ki[1]$ (e.g. $Y_1$ in 9.2) which we hence exploit first, then the ones from $Ki[2]$, and so forth. Here 'exploiting' $Y\in Ki[j]$ means the following. Suppose $Survivors\subseteq min(r)$ is the set of $r$-minimals that escaped the previously tested killers. (Initially put $Survivors:=min(r)$.)
 Using Vertical Layout  the set $Vic(Y)$ of (indices of) victimes  $Z\in min(r)$  can be determined fast. We update $Survivors:=Survivors\setminus Vic(Y)$. Scanning all $Y\in Ki$ we stop and report 'bad row' as soon as $Survivors=\emptyset$ happens. If this never happens then $r$ is good. We call this method the {\it second badness-test}.

 {\bf 9.3.1} Notice that for {\it any} semifinal row $r$ the second badness-test could be 'abused' to get $MHS(r)\ (=Survivors)$ in a one-by-one fashion. Hence the second  badness-test, in tandem with the detection of very-good rows $r$ via '$Ki(r)=\emptyset $ ?' yields a (first grade) minhit algorithm. The first badness-test (9.1) combined with Section 6 similarly yields a (first grade) minhit algorithm. While it may be slower, it does not rely on $MinNotMC(\mathbb{H})$.

 {\bf 9.4} We now embark on the third badness-test which, different from its forerunners, does not expand $min(r)$ in order to sieve it.
 Let ${\cal S}\subseteq {\cal P}[w]$ be a set system. Call $Z\in {\cal P}[w]$ a ${\cal S}$-{\it noncover} if $Z\not\supseteq Y$ for all $Y\in {\cal S}$.
 The family $NC({\cal S})$ of all ${\cal S}$-noncovers is a set ideal. Trivially $NC(\emptyset)={\cal P}[w]$. Reformulating (22) it holds that

(27)\quad  $NC(MinNotMC(\mathbb{H}))=MC(\mathbb{H})$.

 Also recall from (21)  that $MHS(r)=min(r)\cap MC(\mathbb{H})$. This equality can be sharpened as follows.

 (28)\quad $MHS(r)=min(r)\cap NC(Ki(r))$ {\it for all semifinal 012e-rows $r$.}

 {\it Proof of (28).} Let $MinNotMC(\mathbb{H})=\{Y_1,...,Y_s,Y_{s+1},..\}$ be such that $Ki(r)=\{Y_1,...,Y_s\}$. By (27) one has $MC(\mathbb{H})=NC(\{Y_1\})\cap\cdots \cap NC(\{Y_s\})\cap NC(\{Y_{s+1}\})\cap\cdots$. However if $i>s$ then, since $Y_i$ is harmeless for $r$, one has $min(r)\subseteq NC(\{Y_i\})$. Hence $MHS(r)=min(r)\cap MC(\mathbb{H})=min(r)\cap NC(\{Y_1\})\cap\cdots \cap NC(\{Y_s\})=min(r)\cap NC(Ki(r))$. $\square$

For instance, if $r$ is very-good then $Ki(r)=\emptyset$, and so (28) implies\\ $MHS(r)=min(r)\cap NC(\emptyset)=min(r)\cap {\cal P}[w]=min(r)$, as it must.

 {\bf 9.5} The $n$-{\it wildcard} $(n,n,...,n)$ is dual to the $e$-wildcard and thus means 'at least one 0 here'. Accordingly  {\it  012n-rows} are defined. So $\sigma':=(0,n,1,n,2)$ equals $(0,{\bf 0},1,{\bf 0},2)\uplus(0,{\bf 1},1,{\bf 0},2)\uplus(0,{\bf 0},1,{\bf 1},2)$.
 Instead of row-minimal sets, for 012n-rows the {\it row-maximal} sets are relevant. They are obtained by setting the 2's to 1, and filling all $n$-bubbles with 1's up to one position. If generally $max(\sigma)$ is the set of all $\sigma$-maximal sets, then  $max(\sigma')=\{352,354\}$.
 The {\it noncover n-algorithm}\footnote{This essentially is a dual version of the $e$-algorithm with the role of 0's and 1's switched. We recommend [W2] and the references therein.}, fed with ${\cal S}$, renders $NC({\cal S})$ as a disjoint union of {\it final}  012n-rows. Dually to 4.2 each maximal member $X$ of $MC(\mathbb{H})$ is a fortiori maximal in the final 012n-row $\sigma$ it happens to belong to, i.e. $X\in max(\sigma)$. Because each minimal $\mathbb{H}$-hitting set is a maximal member of $MC(\mathbb{H})$ (8.1), we conclue that

 (29)\quad $MHS(\sigma):=\sigma\cap MHS(\mathbb{H})\subseteq max(\sigma).$

 As in 4.2 we call the final 012n-row $\sigma$ {\it bad} if $MHS(\sigma)=\emptyset$, and {\it good} otherwise. If $MHS(\sigma)=max(\sigma)$ then $\sigma$ is {\it very}-{\it good}.
For instance, feeding $MinNotMC(\mathbb{H}_2)$ (given in (24)) yields $MC(\mathbb{H}_2)$ as a disjoint union of the  final 012n-rows $\sigma_1$ to $\sigma_6$ in Table 11.
For instance, $\sigma_4$  is bad since $\{2,6\}\not\in MHS(\mathbb{H}_2)$.
All other rows happen to be very-good.

{\bf 9.6} Instead of $HS(\mathbb{H})$ one could\footnote{This is done in [MU], albeit in a one-by-one manner without any wildcards. } dually mine $MHS(\mathbb{H})$ from $MC(\mathbb{H})$, i.e. replace merely-good 012n-rows by very-good 012n-rows and so forth.  However, we keep mining $MSH(\mathbb{H})$ from the semifinal 012e-rows and only attribute an auxiliary function to the final 012n-rows. (That's why they are 'final' and not 'semifinal'.)
 How exactly can the final 012n-rows facilitate mining $MHS(\mathbb{H})$?
For instance,  from (20), Table 4, and Table 11 follows

 $MHS(\mathbb{H}_2)=HS(\mathbb{H}_2)\cap MC(\mathbb{H}_2)=(\rho_1\uplus\cdots\uplus \rho_4)\cap (\sigma_1\uplus\cdots\uplus\sigma_6),$

  which by (21) implies

(30)\quad $MHS(\rho_3)=\rho_3\cap MC(\mathbb{H}_2)=(\rho_3\cap \sigma_1)\uplus\cdots\uplus(\rho_3\cap\sigma_6).$

For convenience we repeated $\rho_3$ at the bottom of Table 11. By inspection  $\rho_3\cap\sigma_4=\rho_3\cap\sigma_5=\rho_3\cap\sigma_6=\emptyset$ and $\rho_3\cap\sigma_1=\{235,245\},\rho_3\cap\sigma_2=\{356\},\rho_3\cap\sigma_3=\{456\}$. Hence $MHS(\rho_3)=\{235,245,356,456\}=min(\rho_3)$. The very-goodness of $\rho_3$ is no surprise;  $\rho_3$ was immediatly reckognized as such in 4.2.2.

\begin{tabular}{l|c|c|c|c|c|c|c}
	& $1$ & $2$ & $3$ & $4$  &$5$  & $6$    & row-maximal sets \\ \hline
	& & & & & & &  \\ \hline
	$\sigma_1=$ &  0 & 2 & $n$ & $n$ & $n$& 0&  234,235,245  \\ \hline
	$\sigma_2=$ &  0 & $n$ & 1 & 0 & $n$& 1&  236,356  \\ \hline
	$\sigma_3=$ &  0 & 0 & 0 & 2 & 2& 1&  456  \\ \hline
	$\sigma_4=$ &  0 & 1 & 0 & 0 & 0& 1&  {\bf 26}  \\ \hline
	$\sigma_5=$ &  1 & 0 & $n$ & $n$ & 0& 2&  136, 146  \\ \hline
	$\sigma_6=$ &  1 & 1 & 0 & 2 & 0& 0&  124  \\ \hline
		& & & & & & &  \\ \hline
	$\rho_3=$ &  2 & $e_1$ & $e_2$ & $e_2$ & 1& $e_1$&  copied from Table 4  \\ \hline
\end{tabular}

{\sl Table 11: Representing $MC(\mathbb{H}_2)$ as disjoint union of  012n-rows}

{\bf 9.7} This raises a question of wider interest: How can intersections of type $012e\cap 012n$ (such as $r\cap\sigma=\rho_3\cap\sigma_i$ ) be handled? As carried out in [W3], in this setting inclusion-exclusion is benign enough to quickly yield the cardinality $|r\cap\sigma|$. As will be explored elsewhere, this carries over to calculate the number of models of Boolean CNF's of type $Horn\wedge Anti$-$Horn$, which includes type $monotone\wedge antitone$.

{\bf 9.7.1} Interestingly, merely deciding whether or not $|r\cap\sigma|=0$,
works faster still. Namely, as seen before, intersections of type $012e\cap 012n$ can be empty because of 0's and 1's clashing. Another such {\it trivial reason} for $r\cap\sigma=\emptyset$ is it when an $e$-bubble is contained in $zeros(\sigma)$, or when an $n$-bubble is contained in $ones(r)$. Slightly more subtle is it when a trivial reason only arises after {\it new} 0's and 1's have been 'propagated'.

\begin{tabular}{l|c|c|c|c|c|}
	$\sigma=$	& $n_1$ & $n_1$ & $n_2$ & $n_2$  &$n_2$  \\ \hline
	$r=$	& 1 & $e_1$ & $e_1$ & $e_2$  &$e_2$  \\ \hline
	& & & & &   \\ \hline
	$\sigma'=$ &  {\bf 1} & {\bf 0} & $n_2$ & $n_2$ & $n_2$  \\ \hline
	$r'=$ &  1 & {\bf 0} & {\bf 1} & $e_2$ & $e_2$  \\ \hline
	$\sigma''=$ &  1 & 0 & {\bf 1} & $n_2$ & $n_2$  \\ \hline
\end{tabular}

{\sl Table 12: Propagating 0's and 1's to simplify intersetions of 012e-rows with 012n-rows.}

Table 12 illustrates what is meant by propagating. Whatever $\sigma\cap r$ is, each bitstring $x\in\sigma\cap r\subseteq r$ is of type $x=(1,?,..,?)$.
But $n_1n_1$ in $\sigma$ forces $x=(1,0,..,?)$, and so $\sigma\cap r=\sigma'\cap r$. Thus a new 1 and 0 have been {\it propagated}.
In turn, because $e_1e_1$ and $0n_2$ occupy the same positions,one concludes $\sigma'\cap r=\sigma'\cap r'$. Likewise $\sigma'\cap r'=\sigma''\cap r'$, where it ends. Therefore  a single 1 (in $r$) propagated two 0's and three 1's before the process stabilized with the result that
$\sigma\cap r=\sigma''\cap r'$. It is a nontrivial result proved in [W3] that the intersection of a 012e-row with a (same length) 012n-row is empty {\it only} if a trivial reason occurs at the beginning or during the (attempted) stabilization process. For instance, in our example stabilization succeeded, and indeed e.g. $(10101)\in \sigma\cap r\neq\emptyset$.

{\bf 9.8} We  can now formulate the stepping stone to our third badness-test:

(31)\quad {\it The semifinal 012e-row $r$ is bad iff} $r\cap NC(Ki(r))=\emptyset.$

{\it Proof of (31).} While $r\cap NC(Ki(r))$ may be strictly larger than $min(r)\cap NC(Ki(r))$, we claim that $ min(r)\cap NC(Ki(r))=\emptyset\Leftrightarrow r\cap NC(Ki(r))=\emptyset$. Indeed, let
$X\in r\cap NC(Ki(r))$. Then there is $Y\in min(r)$ with $Y\subseteq X$. Since $X$ is a noncover of $Ki(r)$, a fortiori $Y$ is. Hence $Y\in min(r)\cap NC(Ki(r))$.  By (28) it holds that  $MHS(r)=\emptyset$ iff  $r\cap NC(Ki(r))=\emptyset$. $\square$

From 8.2 we know how to calculate $Ki(r)\subseteq MinNotMC(\mathbb{H})$, and upon applying the noncover $n$-algorithm we obtain $NC(Ki(r))$ as a disjoint union $\sigma_1'\uplus\sigma_2'\uplus\cdots \sigma_k'$ of 012n-rows. From
$r\cap NC(Ki(r))=(r\cap \sigma_1')\uplus\cdots\uplus (\rho\cap \sigma_k')$ and (31) follows that $r$ is bad iff all intersections $r\cap\sigma_i'$ are empty. This constitutes our {\it third badness-test}.

{\bf 9.8.1} Recall that $Ki(r)$ is necessary for the second and third badness-test.
As to the latter, does the effort  to produce $NC(Ki(r))$ pay off? That depends  on (a) the size of $min(r)$, and (b) the number of 012n-rows entering $NC(Ki(r))$.
As to (a), for likely-bad but not superkilled rows $r$ the second badness-test must first expand the potentially large promise $min(r)$ and then chop off pieces of it. Good news is, such $r$'s are rare and chances are $r$ is actually-good rather than sophisticated-bad (11.3).
As to (b), recall that the noncover $n$-algorithm  is as expensive as the transversal $e$-algorithm, and both  may produce way more 'multi-valued' rows than the size of their input. However, the sets in $Ki(r)$ are {\it not} random, and this  will considerably cut the number of 012n-rows to be handled by the third badness-test.

 {\bf 9.9} We are now in a position to give more details about replacing merely-good rows $r'$ by very-good rows. Thus suppose $r'$ in Table 13 is the top row of the stack from 5.3. Pick any $e$-wildcard of $r'$, say the $e_1$-wildcard, and expand it. This yields the candidate sons $r_1$ to $r_4$.

\begin{tabular}{l|c|c|c|c|c|c|c|c|c|c|c|c|c|c| }
	& 1 & 2 & 3 & 4  &5  & 6 &7 &8 &9 &10 &11 &12 &13 & 14 \\ \hline
	& & & & & & &  & & & & & & & \\ \hline
$r'=$	& $e_1$ & $e_1$ & $e_1$ & $e_1$  &$0$  & $1$ &$e_2$ &$e_2$ &$1$ &$2$ &$e_3$ &$e_3$ &$e_3$ & $2$ \\ \hline\hline
$r_1=$	& ${\bf 1}$ & ${\bf 2}$ & ${\bf 2}$ & ${\bf 2}$  &$0$  & $1$ &$e_2$ &$e_2$ &$1$ &$2$ &$e_3$ &$e_3$ &$e_3$ & $2$ \\ \hline
$r_2=$	& ${\bf 0}$ & ${\bf 1}$ & ${\bf 2}$ & ${\bf 2}$  &$0$  & $1$ &$e_2$ &$e_2$ &$1$ &$2$ &$e_3$ &$e_3$ &$e_3$ & $2$ \\ \hline
$r_3=$	& ${\bf 0}$ & ${\bf 0}$ & ${\bf 1}$ & ${\bf 2}$  &$0$  & $1$ &$e_2$ &$e_2$ &$1$ &$2$ &$e_3$ &$e_3$ &$e_3$ & $2$ \\ \hline
$r_4=$	& ${\bf 0}$ & ${\bf 0}$ & ${\bf 0}$ & ${\bf 1}$  &$0$  & $1$ &$e_2$ &$e_2$ &$1$ &$2$ &$e_3$ &$e_3$ &$e_3$ & $2$ \\ \hline

\end{tabular}

{\sl Table 13: Expanding $r'$ according to its $e_1$-wildcard.}

It holds that $r=r_1\uplus\cdots\uplus r_4$ and $ min(r')=min(r_1)\uplus\cdots\uplus min(r_4)$. From $min(r_j)\subseteq min(r')$ follows $Ki(r_j)\subseteq Ki(r')$; see 9.9.1 for more details. If $Ki(r_j)=\emptyset$ then $r_j$ is very-good and hence final. Otherwise decide the potential badness of $r_j$ as follows. From $Ki(r_j)\subseteq Ki(r')$ follows $NC(Ki(r_j))\supseteq NC(Ki(r'))$. Thus if $r_j\cap NC(Ki(r'))\neq\emptyset$ (which can be tested fast since $NC(Ki(r'))$ is known) then $r_j\cap NC(Ki(r_j))\neq\emptyset$, and so $r_j$ is not bad by (31). If $r_j\cap NC(Ki(r'))=\emptyset$ then we need to calculate $NC(Ki(r_j))$ in order to make sure (again with (31)) whether or not $r_j$ is bad. If yes, $r_j$ is discarded, otherwise it is merely-good and put on top of the stack.

{\bf 9.9.1} As to sieving $Ki(r_j)$ from the known set $Ki(r')$, let $K_0$ be the set of all $Y\in Ki(r')$ with $Y\cap\{1,2,3,4\}=\emptyset$, and for $1\le j\le 4$ let $K_j$ be the set of all $Y\in Ki(r')$ with $Y\cap\{1,2,3,4\}=\{j\}$. It is clear that $Ki(r')=K_0\uplus K_1\uplus\cdots\uplus K_4$ and that $Ki(r_j)=K_0\uplus K_j\ (1\le j\le 4)$. The sets $K_0,...,K_4$ are easily sieved from $Ki(r')$ using Vertical Layout. Moreover, the expansion of $NC(K_0\uplus K_j)$ into disjoint 012n-rows, should it be necessary, can exploit the pre-calculated expansion of $NC(K_0)$.  As to 'Pick any $e$-wildcard' at the beginning of 9.9, perhaps  choosing the $e$-wildcard that maximizes $K_0$  tends to minimize the time for calculating the set systems $NC(K_0\uplus K_j)$.
If not the total time for processing $r'$ but a small number of final very-good rows is the target, another heuristic may be better.

\section{How to calculate $MinNotMC(\mathbb{H})$ in the first place}

 In order to understand how $MinNotMC(\mathbb{H}_2)$ in (24) was computed, it pays to momentarily relabel\footnote{Otherwise the elements of $H_1,...,H_6$ clash with the {\it indices} 1,2,...,6 of $H_1,...,H_6$.} the hyperedges of $\mathbb{H}_2$ in obvious ways:

(32)\quad $H_1=\{a,b,e\},\ H_2=\{c,d\},\ H_3=\{d,e,f\},\ H_4=\{a,c,e\},\  H_5=\{b,f\}$

Let us refine the  property '$T$ is MC'. Thus for any set $T$ and fixed $u\in T$ we  say '$T$ {\it is $u$-MC}' if  $crit(u,T)\neq\emptyset$. Consequently it holds for all $T\subseteq W:=\{a,b,c,d,e,f\}$ that:

(33)\quad $T$ is MC \hspace*{0.3cm} $\Longleftrightarrow$ \hspace*{0.3cm} $T$ is $u$-MC for all $u\in T$

(34)\quad $T$ is not-MC \hspace*{0.2cm} $\Longleftrightarrow$ \hspace*{0.2cm} $T$ is not-$u$-MC for some $u\in T\ \Longleftrightarrow\ crit(u,T)=\emptyset$\hspace*{0.2cm} for some $u\in T$

For instance $T=\{d,c,f\}$ is not-$d$-MC because from $d\in T\cap H_i$ always follows $|T\cap H_i|\ge 2$, the relevant indices being $i=2,3$.

{\bf 10.1} For $u\in W$ put ${\cal S}_u:=\{i\in [h]:\ u\in H_i\}$. Therefore

(35)\quad ${\cal S}_a=\{1,4\},\ {\cal S}_b=\{1,5\},\ {\cal S}_c=\{2,4\},\ {\cal S}_d=\{2,3\},\
{\cal S}_e=\{1,3,4\},\ {\cal S}_f=\{3,5\}.$

The fact hat $\{d,c,f\}$ is not-$d$-MC can now be seen as tantamount to ${\cal S}_d \subseteq
{\cal S}_c \cup {\cal S}_f$. Generally the not-$u$-MC sets bijectively match the {\it set coverings} of ${\cal S}_u$
by {\it other}  ${\cal S}_v$'s.

Our aim is to calculate the family $MinNotMC(\mathbb{H}_2)$ of minimal not-MC sets. According to (34) they are found {\it among} the minimal not-$u$-MC sets, where $u$ ranges over $W$. Let us hence find for each fixed $u\in W$ all minimal set coverings of ${\cal S}_u$. The systematic method follows in 10.2, but for $\mathbb{H}=\mathbb{H}_2$ we can proceed by inspecting (35):

\begin{itemize}
	\item The minimal set coverings of ${\cal S}_a$ are $\{{\cal S}_b,{\cal S}_c\},\ \{{\cal S}_e\}$

	\item The minimal set coverings of ${\cal S}_b$ are
	     $\{{\cal S}_a,{\cal S}_f\},\ \{{\cal S}_e,{\cal S}_f\}$

	     \item The minimal set coverings of ${\cal S}_c$ are
	     $\{{\cal S}_a,{\cal S}_d\},\ \{{\cal S}_d,{\cal S}_e\}$

	     \item The minimal set coverings of ${\cal S}_d$ are
	     $\{{\cal S}_c,{\cal S}_e\},\ \{{\cal S}_c,{\cal S}_f\}$

	     \item The minimal set coverings of ${\cal S}_e$ are
	     $\{{\cal S}_a,{\cal S}_d\},\ \{{\cal S}_a,{\cal S}_f\},\
	     \{{\cal S}_b,{\cal S}_c,{\cal S}_d,\},\ \{{\cal S}_b,{\cal S}_c,{\cal S}_f\}$

	     \item The minimal set coverings of ${\cal S}_f$ are
	     $\{{\cal S}_b,{\cal S}_d\},\ \{{\cal S}_b,{\cal S}_e\}$
\end{itemize}

Therefore the minimal not-$a$-MC sets are $\{{\bf a},b,c\}$ and $\{{\bf a},e\}$, and so forth until the
minimal not-$f$-MC sets are $\{{\bf f},b,d\}$ and $\{{\bf f},b,e\}$. The inclusion-minimal sets among these sets\footnote{ For instance $\{e,a,d\}$ gets killed by $\{a,e\}$, and e.g. the double occurence of $\{b,e,f\}=\{f,b,e\}$ can be pruned. In general proceed as in 7.1 to get the minimal sets.} are (in shorthand notation)
$abc,ae,baf,bef,cad,cde,dcf,fbd$.
Relabelling back $a\to 1,...,f\to 6$ yields $MinNotMC(\mathbb{H}_2)$ in (24).

{\bf 10.2} As is well known, finding minimal set coverings is cryptomorphic to finding minimal hypergraph transversals. Let us make this cryptomorphism explicite by recalculating the  set coverings of the set ${\cal S}_e$ by the set system ${\cal S}:=\{{\cal S}_a,{\cal S}_b,{\cal S}_c,{\cal S}_d,{\cal S}_f\}$. Because ${\cal S}_e=\{1,3,4\}$, at least one member of ${\cal S}$ must cover 1; only ${\cal S}_a,{\cal S}_b$ can do that. Similarly, only ${\cal S}_d,{\cal S}_f$ can contain 3, and only ${\cal S}_a,{\cal S}_c $ can contain 4. Thus we define the {\it auxiliary hypergraph} triggered by $e$ as

$(36)\ \mathbb{H}_2^{aux}(e):=\{  \{{\cal S}_a,{\cal S}_b \},\{{\cal S}_d,{\cal S}_f \},\{{\cal S}_a,{\cal S}_c \} \}.$

It follows that the $\mathbb{H}_2^{aux}(e)$-transversals are exactly the minimalset coverings of ${\cal S}_e$ by other ${\cal S}_u$'s.
It is natural to employ again the transversal e-algorithm to calculate all minimal $\mathbb{H}_2^{aux}(e)$-transversals.

The transversal e-algorithm starts by imposing the hyperedge $\{{\cal S}_a,{\cal S}_b \}$ of $\mathbb{H}_2^{aux}(e)$, and then imposes $\{{\cal S}_d,{\cal S}_f \}$. Since the two happen to be disjoint, this is achieved by the single 012e-row $r_1$ in Table 13. Imposing $\{{\cal S}_a,{\cal S}_c \}$ upon $r_1$ yields the two final rows $r_2$ and $r_3$.
It happens that both of them are very-good, i.e. $min(r_2)$ and $min(r_3)$ need not  be pruned further.

 \begin{tabular}{l|c|c|c|c|c|c}
	& ${\cal S}_a$ & ${\cal S}_b$ & ${\cal S}_c$ & ${\cal S}_d$  & ${\cal S}_f$& $min(r_i)$ \\ \hline
	& & & & & &   \\ \hline
	$r_1=$ &  $e$ & $e$ & $2$ & $e'$ & $e'$&     \\ \hline
	& & & & & &  \\ \hline
	$r_2=$ &  {\bf 1} &  2 &{\bf 2} & $e'$ & $e'$&
	$\{\{{\cal S}_a,{\cal S}_d\},\ \{{\cal S}_a,{\cal S}_f\}\}$  \\ \hline
	$r_3=$ &   {\bf 0} & 1  &{\bf 1} & $e'$ & $e'$&
	$\{\{{\cal S}_b,{\cal S}_c,{\cal S}_d\},\ \{{\cal S}_b,{\cal S}_c,{\cal S}_f\}\}$ \\ \hline
\end{tabular}

{\sl Table 14: Calculating all the minimal set coverings of ${\cal S}_e$ with the $e$-algorithm}

\section{Numerical experiments}

We run the minhit algorithm on various random but  full\footnote{Everything in this article could be adapted to non-full hypergraphs, but e.g. because of the failure of (18) it would be cumbersome. It is easy to generate random and equicardinal hyperedges with Mathematica. If the corresponding hypergraph is not full, this can be fixed by trimming some (random) hyperedges in obvious ways. } hypergraphs $\mathbb{H}=\mathbb{H}(w,h,k)$ characterized by the {\it signature} $(w,h,k)$. That means that $\mathbb{H}\subseteq {\cal P}[w]$ and all $h$ hyperedges $H\in\mathbb{H}$ are random and have {\it uniform cardinality} $|H|=k$. (We omit $k=2$ in view of 4.2.3.)
For most signatures the  minhit algorithm is second grade, but sometimes more, sometimes less.
We also use extrapolation. Subsections 11.1 and 11.2  explain the various ways to handle
$\mathbb{H}(w,h,k)$. Subsection 11.3 compares the second and third badness-test, and  11.4  focuses on two among nineteen algorithms evaluated in [GV].

{\bf 11.1} For each signature $(w,h,k)$ we record\footnote{The variation among random instances of the same signature can be high. Thus some random (70,20,5)-instance different from the one listed in Table 14 triggered only 3147 semifinal rows in 2 seconds. An average promise of 365067 still pushed $|MHS(\mathbb{H})|$ to about $11\cdot 10^8$, and it took 4347 seconds to further process the semifinal rows (the percentages being 73+24+3).
Since this article is not about classifying signatures, we were content to just pick {\it one} random instance per signature. It was advantageous to skip the feasibility test of 7.3.} the number
$R$ of semifinal 012e-rows $r$ delivered by the transversal $e$-algorithm, the average promise size $|min(r)|$, and the average degree (see (7)) of a row. The next column (sometimes) contains\footnote{For various small $\mathbb{H}(w,h,k)\ (w<20)$ the author checked brute-force (by applying the MC-dud-test to a great many subsets of $[w]$) that the sophisticated method of Section 10 to find $MinNotMC(\mathbb{H})$ works correctly.} the cardinality  $mnMC:=|MinNotMC(\mathbb{H})|$, calculated as in Section 10. Note that considerably less time was spent for running the $w$ many auxiliary
transversal e-algorithms than for minimizing the resulting set system ${\cal S}$ to $Min({\cal S})=MinNotMC(\mathbb{H})$. For instance for the (30,50,7)-instance it took only 61 seconds to calculate ${\cal S}$ (of cardinality 252'211), but 2503 seconds to shrink
 ${\cal S}$ to $MinNotMC(\mathbb{H})$ (of cardinality 55538) by using Vertical Layout (Section 7).

 As to the last two columns in Table 15,
  in each semifinal row $r$ we sampled\footnote{Sampling 20 instead of 100 made little difference. Well known formulas from statistics could be used to calculate the likelihood that an estimate for $|MHS(\mathbb{H})|/|min(r)|$ violates a predetermined error-margin $\varepsilon$.   } 20 row-minimal sets, and  the $\alpha(r)$ minimal transversals among them were counted (using the MC-dud-test). If $0<\alpha(r)<20$ then $r$ is merely-good. When $\alpha(r)=20$ then $r$ is {\it likely-good} and undergoes the very-goodness test of Section 8 in order to decide between very-good and merely-good. When $\alpha(r)=0$ then $r$ is {\it likely-bad} and undergoes an appropriate  badness-test  in order to decide between bad and merely-good.
  Thus whenever all semifinal rows, as well as $MinNotMC(\mathbb{H})$, got computed,
  we could determine the precise number of very-good, merely-good, and bad semifinal rows respectively (which defines a second grade minhit algorithm). The  percentages of row-types, rounded to integers, are rendered\footnote{Sometimes the numbers sum up to  101, due to rounding. } in the last column, say as 43,49,8 for the (60,20,5) signature. From  the 2174 bad semifinal rows $(\approx 8\%)$ a whopping 2157 suffered a superkiller, and 17 were sophisticated-bad. From another perspective, 2235 rows were likely-bad; the mentioned 2174 'badies' and 61 'actually-good' ones.

  {\bf 11.1.1} Once the semifinal rows are classified, finding the exact numbers $|MHS(r)|$ for the  very-good or bad rows $r$ is trivial. (For instance, in the (100,40,3)-example the very-good rows contributed the lion share of 319986284352327 ($\approx$ 320 trillion) minimal hitting sets.)
    For the merely-good rows $r$ we approximated $|MHS(r)|$ by ${\frac{\alpha(r)}{20}}|min(r)|$. Altogether this yields an approximation of $|MHS(\mathbb{H})|$, which is given in the second last column. In some cases we obtained the exact number $|MHS(\mathbb{H})|$ (=first grade minhit) by sieving one-by-one the promise of all merely-good rows (see 9.3.1).
  For instance  $|MHS(\mathbb{H}(60,20,5))|=50'109'682$ was calculated in 5042 seconds, whereas the mere estimation $|MHS(\mathbb{H}(60,20,5))|\approx 5\cdot 10^7$ in the line above took 198 seconds.

\begin{tabular}{|c|c|c|c|c|}
$(w,h,k)$	&$R$, av.prom, av.deg  & mnMC & $ |MHS(\mathbb{H})|$ & row-types       \\ \hline
	& & & &  \\ \hline
     $(50,20,5)$ & $9242,319,11,3s$ & 415, 1s & $\approx (23\cdot 10^5)$ & $52,43,5,\ 26s $   \\ \hline
	$(50,20,5)$ & $9242,319,11,3s$ & 415, 1s & $=2290805$ & $52,43,5,\ 159s $   \\ \hline
	$(60,20,5)$ & $26701,2488,13,13s$ & 309, 1s & $\approx 5\cdot 10^7$ & $43,49,8,\ 198s $   \\ \hline
    $(60,20,5)$ & $26701,2488,13,13s$ & 309, 1s & $=50'109'682$ & $43,49,8,\ 5042s $   \\ \hline
	$(70,20,5)$ & $13577,12\cdot 10^4,14,8s$ & 256, 3s& $\approx (14\cdot 10^8)$ & $68,32,0,\ 44s $   \\ \hline
	$(70,20,6)$ & $41319,2078,12,21s$ & 730, 3s & $\approx (7\cdot 10^7)$ & $37,62,2,\ 776s $   \\ \hline
	$(70,20,8)$ & $323315,319,11,158s$ & 6885, 250s & $\approx (4\cdot 10^7)$ & $17,65,18,\ 14813s $   \\ \hline
	$(70,20,12)$ & $917377,158,10,1546s$ & --- & $\approx 42445(\frac{R}{1000})$&
	$33,60,7,\ 5s $   \\ \hline
	$(70,20,30)$ & $77448,36,5,39s$ & --- & $=658039$ & $13,62,25,\ 186s$   \\ \hline

	$(30,50,7)$ & $123584,5,10,\ 56s$ & 55538, 2564s & $=126349$ & $15,26,59,\ 66s$   \\ \hline
	$(30,80,7)$ & $217984,4,11,\ 180s$ & --- & $=214133$ & $17,26,58,\ 162s$   \\ \hline
	$(30,5000,7)$ & ${\bf 1000},2,18,103s$ & --- & $\approx 445(\frac{R}{1000})$ & $(23),14,(64),\ 19s$   \\ \hline\hline

	$(100,40,3)$ & $10367,3\cdot 10^{10},33,13s$ & 113, 0.4s & $> 319'986'284'352'327$ & $94,6,0,\ 87s$   \\ \hline
	$(100,80,3)$ & ${\bf 1000},10285,34,2s$ & 437, 2s & $\approx 3\cdot 10^6(\frac{R}{1000})$ & $6,73,21,\ 13s$   \\ \hline
	$(100,50,4)$ & ${\bf 1000},3303,23,1s$ & 673, 2s & $\approx (9\cdot 10^5)(\frac{R}{1000})$ & $5,89,6,\ 2169s$   \\ \hline

	$(100,25,6)$ & $16\cdot 10^5,17801,17,1267s$ & 1355, 5s & $\approx (44\cdot 10^5)(\frac{R}{1000})$ & $11,81,8,\ 74s$   \\ \hline

	$(1000,10,200)$ & $65828,3\cdot 10^{11},5,209s$ & --- & $\approx(13\cdot 10^{10})(\frac{R}{1000})$ & $(64),36,(0),\ 1s$\\ \hline
	$(10000,100,1000)$ & ${\bf 1000},13\cdot 10^5,14,158s$ & ---  & $\approx (10^{9})(\frac{R}{1000})$ & $(55),40,(5),\ 70s$\\ \hline
\end{tabular}

{\sl Table 15.  Numerical evaluation and extrapolation of the minhit algorithm}

{\bf 11.2} We come to extrapolation. For some hypergraphs $\mathbb{H}(w,h,k)$ we could compute  $MinNotMC(\mathbb{H})$, but not necessarily all $R$ semifinal rows. Even if all were computed, an evaluation of all semifinal rows within reasonable time was not always possible due to the size of $MinNotMC$.
We hence only classified the first\footnote{One may  object that the first  thousand rows need not be representative because they only represent the 'leftmost' 1000 nodes of the computation tree. This objection can be dismissed as follows. Whenever a top row of the LIFO stack (4.1.1)  gets removed because all hyperedges have been imposed on it, we switch the new top row with a random row further below. The effect is that the first 1000 semifinal rows are as random as any other sample of 1000 semifinal rows. }  thousand  semifinal rows. From this one can extrapolate $|MHS(\mathbb{H})|$. For instance,

$$|MSH(\mathbb{H}(100,25,6))|\approx  44\cdot 10^5\cdot (\frac{R}{1000})\approx 44\cdot 10^5\cdot 16\cdot 10^3\approx 7\cdot 10^{10}.$$

In contrast for $\mathbb{H}(100,50,4)$ the term $\frac{R}{1000}$ persists since $R$ is unknown.

{\bf 11.2.1} Without $MinNotMC(\mathbb{H})$ we currently\footnote{The alternative test in Section 6 would have been fit to do the job in some instances (all that matters is a small number of hyperedges, not their sizes), but it has not yet been implemented. There is another very-goodness-test, based on a matroid theorem of Rado, that awaits implementation. It doesn't rely on $\mathbb{H}$ but rather compares semifinal rows with {\it each other} (similar but more subtle than 7.1.1). It is fully described  in [W3].} can only test for very-goodness or badness in the naive way (which sometimes suffices), or we content ourselves with uniform sampling at random.
For instance, it took 19 seconds to find that the 1000 random semifinal rows triggered by $\mathbb{H}(30,5000,7)$ carried only 445 minimal hitting sets. Thus
$|MHS(\mathbb{H}(30,5000,7)|\approx 445(\frac{R}{1000})$, whatever $R$ may be. We use parentheses, i.e. (23),14,(64), to indicate that the percentages in the last column refer to {\it likely}-very-good, merely-good, {\it likely}-bad.

{\bf 11.2.2} It is illuminating (draw your own conclusions) how the stats change when two entries of a signature are fixed and the third increases. That concerns $(w,20,5)\ (w=50,60,70)$ and  $(70,20,k)\ (k=5,6,8,12,30)$ and  $(30,h,7)\ (h=50,80,5000)$. All other signatures are of a sporadic nature.

{\bf 11.3} Let us flesh out previous remarks  about badness-testing. First recall that a semifinal row $r$ has a superkiller iff $ones(r)$ is not a MC-set. This is easier to test than sophisticated badness which requires $MinNotMC(\mathbb{H})$. One does not need to calculate $MinNotMC(\mathbb{H})$ to see that sophisticated badness is rare; the likely-bad rows constitute a superset of the bad rows, and even in this larger set always more than 80\% of all rows were superkilled.
  As to the third badness-test (9.8),  for
 $\mathbb{H}(100,25,6)$ the likely-bad semifinal row $r$ that maximized $|Ki(r)|$
had 71 killers, namely 9,12,50 of cardinality 3,4,5 respectively. These 71 sets are {\it not}  random; to witness, the nine 3-sets among them were
$ \{2,46,53\},\{2,53,89\},\{2,53,90\},\{36,48,81\},\\ \{36,80,81\},
\{42,48,81\}, \{42,80,81\},\{48,81,98\},\{80,81,98\}.$
The similarities among the killers are the reason why the noncover n-algorithm applied to $Ki(r)$ delivered in 0.7 seconds a mere\footnote{ As is clear from our experiments, 71 {\it random} sets would have triggered an immense amount of 012e-rows (and similarly 012n-rows).  }  823  disjoint 012n-rows. Nevertheless, the second badness-test was competitive  since $min(r)$ was small. The situation is different for $\mathbb{H}(100,80,3)$. The indicated 13 seconds to classify 1000 semifinal rows $R$ are due to the following mix of badness-tests. For $|min(r)|\le 500$ the first badness-test was used, for $500<|min(r)|\le 5000$ the second, and for $|min(r)|> 5000$
the third. Because some $r$'s had large promise (the record being  $|min(r)|=1'119'744$) replacing the third badness-test by the second pushed the time to 456 seconds.

 We mention that using the third badness-test to convert merely-good rows to very-good rows (9.9) has not yet been implemented in the author's Mathematica program. Once this happens, also hypergraphs triggering semifinal rows with excessively large promise (such as $\mathbb{H}(1000,10,200)$) will enjoy a first grade minhit algorithm, provided $R$ is moderate. For large $R$, recur to parallelization, which leads us to 11.4.

{\bf 11.4} In [GV] nineteen methods to calculate $MHS(\mathbb{H})$ have been pitted against each other on a common platform, using a variety of real-life datasets.
 Our minhit algorithm does not post factum fit that platform. For one thing, it is implemented in high-level Mathematica code and so far only ran on the author's laptop (Dell Latitude 7410). Furthermore, much different from [GV], all hypergraphs in Table 15 have random and equicardinal hyperedges (which in view of 11.3 may be disadvantageous). Nevertheless, let us attempt a preliminary comparison  with two specific algorithms investigated in [GV]. First, the {\it [MU]-algorithm} like us (see  9.6) relies  on the MC-condition but proceeds one-by-one. Second, building on ideas of Knuth, the {\it [T]-algorithm} of Toda like us uses compression, but in  more implicite ways (BDD's). These two algorithms also happen to be the champions\footnote{Let us cite from [GV, Sec. 5.4] (using our acronyms [T] and [MU]):  {\it The algorithms of [MU] and [T] are far faster than their competitors across a variety of input set families. [T] is extremely fast on inputs for which it terminates (...). However it frequently exhausted the 32GB available memory on our workstation.}
In [GV,Sec. 5.4] the authors describe a collection of 128 million minimal transversals as '{\it enormous}'. This is true, but only if listed one-by-one. } in [GV]. Since the MC-condition has received  plenty attention in Sections 8 to 10, let us devote the remainder of 11.5 to the [T]-algorithm. Here come four aspects where the minhit algorithm seems to win out (but since talk is cheap  only direct confrontation can ultimately determine the pros and cons of both).

\begin{itemize}
	\item [(i)] As is well known (and repeated in [W2]), having the BDD of a Boolean function $f$ yields at once the cardinality of the model set $Mod(f)$. With a bit more effort (but in linear total time) one gets the model set of $f$ as a disjoint union of 012-rows. Unfortunately, when $Mod(f)=MHS(\mathbb{H})$, then the models are mutually incomparable, and so all 012-rows are necessarily 01-rows, i.e. no compression is achieved. Matters are  alleviated but not cured by Toda's use of zero-supressed BDD's (=ZDD's). Thus the ZDD provides an implicite compression of $MHS(\mathbb{H})$ which e.g. suffices to yield $|MHS(\mathbb{H})|$ at once, often faster than the 18 competitors in [GV]. But since $MHS(\mathbb{H})$ is only\footnote{If all hitting sets are encoded in a BDD then it follows from arXiv:1703.08511 that, if not the minimal, the transversals of fixed cardinality can be output in a compressed format (using $g$-wildcards).}   output one-by-one this didn't always mean overall victory.  The [T]-algorithm is probably faster than the minhit algorithm (even a future first grade version) whenever the compression-rate\footnote{The compression rate $|MHS(\mathbb{H})|/R$ not only depends on the structure of $\mathbb{H}$ but also on the {\it order} in which the hyperedges are imposed. No research in that direction has been undertaken.} is low, such as for the (30,5000,7) signature. With increasing compression-rate the tables begin to turn. Also keep in mind: A compressed representation of $MHS(\mathbb{H})$ may be desirable enough that spending extra time on it is worthwile.

	\item [(ii)] Even when the final BDD is moderate in size, intermediate BDD's can be excessively large, thus causing memory problems. In contrast, the LIFO stack used by the transversal $e$-algorithm can never contain more than $h$ rows (this is  a classic result about LIFO stacks). As we have seen, whatever problems  arise with the semifinal rows afterwards, they are not memory problems.

	\item [(iii)] In [T,p.101] Toda hopes to eventually parallelize one part of his algorithm, i.e. the calculation of a BDD that captures $HS(\mathbb{H})$. In contrast, parallelizing\footnote{Why parallelization (aka distributed computing) works smoothly in all LIFO-scenarios is e.g. explained in [W2,Sec. 6.5]. Thus the Achilles heel of the minhit algorithm, i.e. its  time-consuming creation of candidate sons which weighs in heavy when $|\mathbb{H}|$ is large, can in a sense be 'talked away' by imagining a distributed network that cuts total CPU-time by a factor 1000. }  our equivalent (the transversal e-algorithm)  is straightforward. In fact, the evaluation of all semifinal 012e-rows can be parallelized as well.

	\item [(iv)] Like the minhit algorithm some algorithms in [GV] have the potential for cut-off (4.3), but the [T]-algorithm seems not to be  among them since it does not appear in Table 9 or 10 of [GV].
\end{itemize}

\section*{References}
\begin{enumerate}

\item[{[E]}] Eiter T,
Exact transversal hypergraphs and application to Boolean $\mu$-functions. (English summary)
J. Symbolic Comput. 17 (1994), no. 3, 215–225.

\item[{[EGM]}] Eiter T, Gottlob G, Makino K, New results on monotone dualization and generating hypergraph transversals. SIAM J. Comput. 32 (2003), no. 2, 514–537.

\item[{[GV]}]  Gainer-Dewar A, Vera-Licona P, The minimal hitting set generation problem: algorithms and computation. SIAM J. Discrete Math. 31 (2017), no. 1, 63–100.

\item[{[MR]}] Motwani R, Raghavan P, Randomized Algorithms, Cambridge University Press 1995.

\item[{[MU]}] Murakami K, Uno T, Efficient algorithms for dualizing large-scale hypergraphs. Discrete Appl. Math. 170 (2014), 83–94.

\item[{[T]}] Toda T, Hypergraph transversal computation with binary decision diagrams, in: SEA 2013 Rome, Italy.

\item[{[U]}] Uno T, A fast algorithm for enumerating bipartite perfect matchings. Algorithms and computation (Christchurch, 2001), 367–379, Lecture Notes in Comput. Sci., 2223, Springer, Berlin, 2001.

\item[{[V]}]  Vazirani V, NC algorithms for computing the number of perfect matchings in K3,3-free graphs and related problems. Inform. and Comput. 80 (1989), no. 2, 152–164.

\item[{[W1]}]  Wild M, Counting or producing all fixed cardinality transversals. Algorithmica 69 (2014), no. 1, 117–129.

\item[{[W2]}] Wild M, ALLSAT compressed with wildcards: From CNF's to orthogonal DNF's by imposing
 the clauses one by one, The Computer Journal, doi: 10.1093/comjnl/bxaa142.

\item[{[W3]}] Wild M, arXiv:2008.08996v1. This 2020 version (with the same title)  of the present article  contains a lot of material not covered in the current version, and vice versa.

\end{enumerate}

\end{document}

\section{About detecting bad rows}

{\bf 7.5} For a set system ${\cal B}\subseteq {\cal P}(W)$ we say that $X\subseteq W$ is a
${\cal B}$-{\it noncover} if $B\not\subseteq X$ for all $B\in {\cal B}$. Obviously the family
${\cal N C}({\cal B})$ of all ${\cal B}$-noncovers is a set-ideal. The $n$-algorithm (see [W2] and the references therein) is the mirror image of the $e$-algorithm; essentially the roles of 0 and 1 are switched. It follows (see also 7.3.2) that feeding the members of ${\cal B}$ one by one to the $n$-algorithm renders ${\cal N C}({\cal B})$ as a disjoint union of 012n-rows.

{\bf 7.5.1} For a fixed hypergraph $\mathbb{H}\subseteq {\cal P}(W)$ let ${\cal A}$ be the family of all minimal sets in ${\cal P}(W)\setminus {\cal  M C}(\mathbb{H})$. In order to prove that

(29)\quad  ${\cal N C}({\cal A})={\cal  M C}(\mathbb{H})$

let $X\in {\cal N C}({\cal A})$. If we had $X\in {\cal P}(W)\setminus {\cal  M C}(\mathbb{H})$ then by definition of ${\cal A}$ there would be $A\in {\cal A}$ with $A\subseteq X$, contradicting $X$ being an ${\cal A}$-noncover. Conversely, if $Y\in {\cal  M C}(\mathbb{H})$ then $A\not\subseteq Y$ for all
$A\in {\cal A}$ because by (10) each subset of $Y$ belongs to ${\cal  M C}(\mathbb{H})$. Hence $Y\in {\cal N C}({\cal A})$. This proves (29).

It follows from (29) and the remarks above that feeding the $n$-algorithm with the sets from ${\cal A}$ yields ${\cal  M C}(\mathbb{H})$. To fix ideas, consider $\mathbb{H}=\mathbb{H}_2$. In 7.4 we will argue that the family of minimal sets outside ${\cal  M C}(\mathbb{H}_2)$ is

(30)\quad ${\cal A}(\mathbb{H}_2)=\{123,15,216,256,314,345,436,624\}.$

{\bf 7.5.2} Taking (30) for granted let us watch the $n$-algorithm digesting the first few sets
of ${\cal A}$ being fed to it. Because $\{1,5\}$ and $\{4,3,6\}$ in (30) are disjoint, they can be imposed
within just one 02n-row $s_1$, see below. Imposing $\{1,2,3\}$ upon $s_1$ induces once more a kind of Abraham-Flag (in boldface). Proceeding similar to the e-algorithm in Section 5 one eventually obtains the final 012n-rows $\sigma_1,...,\sigma_6$ in Table 12.

\begin{tabular}{l|c|c|c|c|c|c|c}

	$s_1=$ &  $n_1$ & 2 & $n_2$ & $n_2$ & $n_1$& $n_2$&    \\ \hline
	& & & & & & &  \\ \hline
	$s_2=$ &  {\bf 0} & {\bf 2} & ${\bf n_2}$ & $n_2$ & 2& $n_2$&   \\ \hline
	$s_3=$ &   {\bf 1} &  {\bf 0} & ${\bf n_2}$ & $n_2$ & 0& $n_2$&   \\ \hline
	$s_4=$ &   {\bf 1} &  {\bf 1} &  {\bf 0} & 2 & 0& 2&    \\ \hline

\end{tabular}

Def R3 als die Anzahl finaler 012n-Zeilen, produziert vom Verfuettern von MinNotMC an n-Algo. Zeige, dass komprimierte Erzeugung aller min hitting sets in poly(R1,R2,R3,h,w) geht.

Since the set-filter $HS(\mathbb{H})$ can be compressed with 012e-rows $\rho_1,\rho_2,\ldots$, by duality the set-ideal $MC(\mathbb{H})$ (see (11)) should be compressible with 012n-rows $\sigma_1,\sigma_2,\ldots$.  We hope to convince the reader in 7.1 that such a
$MC(\mathbb{H})$-representation would be immensly  useful.
Specifically 7.1.1 shows how part (a) of our Main Quest (defined in 6.1) would have an elegant solution. And 7.1.2 shows how part (b) can be tackled more systematically than in Section 6.
It gets more technical in 7.2 where we use inclusion-exclusion to calculate the cardinalities
$|\rho_i\cap\sigma_j|$.
The details of calculating the $MC(\mathbb{H})$-representation follow in Sections 7.3 to 7.5.

{\bf 7.2} For the time being we ask the reader to accept that $MC(\mathbb{H}_2)$ is the disjoint union of the final \footnote{Here 'final' means that the rows are the output of some algorithm to which we turn later. }012n-rows in Table 10. The $\sigma_j$-{\it maximal} sets $Y$ are written (in shorthand) to the right of $\sigma_j$. Each $Y$ is obtained by setting all 2's to 1 and, for each $n$-bubble, setting all but one $n$ to 1.

We define {\it bad, good, very-good} for final $012n$-rows as we did it for final $012e$-rows.
For instance, $\sigma_4$ in Table 10 is bad since $\sigma_4\cap MHS(\mathbb{H}_2)=\emptyset$;
all other rows happen to be very-good. (That this behaviour matches the behaviour of the $012e$-rows in Table 4 is coincidence.)

\begin{tabular}{l|c|c|c|c|c|c|c}
	& $1$ & $2$ & $3$ & $4$  &$5$  & $6$    & row-maximal sets \\ \hline
	& & & & & & &  \\ \hline
	$\sigma_1=$ &  0 & 2 & $n$ & $n$ & $n$& 0&  234,235,245  \\ \hline
	$\sigma_2=$ &  0 & $n$ & 1 & 0 & $n$& 1&  236,356  \\ \hline
	$\sigma_3=$ &  0 & 0 & 0 & 2 & 2& 1&  456  \\ \hline
	$\sigma_4=$ &  0 & 1 & 0 & 0 & 0& 1&  26, bad  \\ \hline
	$\sigma_5=$ &  1 & 0 & $n$ & $n$ & 0& 2&  136, 146  \\ \hline
	$\sigma_6=$ &  1 & 1 & 0 & 2 & 0& 0&  124  \\ \hline
\end{tabular}

{\sl Table 10: Representing $MC(\mathbb{H}_2)$ as disjoint union of  012n-rows}

In view of Table 4 and (18) we conclude that

$MHS(\mathbb{H}_2)=HS(\mathbb{H}_2)\cap MC(\mathbb{H}_2)\ =
(\rho_1\uplus\cdots \uplus \rho_6)\cap (\sigma_1\uplus\cdots \uplus \sigma_6)=
\biguplus \{\rho_i\cap\sigma_j:\ i,j\in [6]\}.  $

For instance, $\rho_5\cap\sigma_1=\{245\},\ \rho_5\cap\sigma_3=\{456\}$ and otherwise $\rho_5\cap\sigma_j=\emptyset$.

{\bf 7.2.1} We are now in a position to survey the remainder of the article. Letting $\mathbb{H}$ be arbitrary assume we have obtained a representation
$HS(\mathbb{H})=\rho_1\uplus\cdots \uplus\rho_p$ with final 012e-rows $\rho_i$ and a representation
$MC(\mathbb{H})=\sigma_1\uplus\cdots\uplus \sigma_q$ with final 012n-rows $\sigma_j$. Then
$MHS(\mathbb{H})=\biguplus\{\rho_i\cap\sigma_j :\ i\in [p],\ j\in [q]\}$, as argued above.
Because one can calculate swiftly the cardinalities $|\rho_i\cap\sigma_j|$ with inclusion-exclusion (7.3), this representation enables one to get the exact cardinality $|MHS(\mathbb{H})|$ of minimal transversals; some more numerical experiments will support the claim. But how to achieve the Main Quest (4.3), i.e. how to get $MHS(\mathbb{H})$ itself, preferably in compact format? Subsection 7.4 gives the answer. It remains to show (7.5)
how $MC(\mathbb{H})$ can be expanded as disjoint union of 012n-rows in the first place. In all of that numerical experiments hopefully follow in a future publication.

{\bf 7.3} Here we show how inclusion-exclusion can be used to calculate the cardinality
$N:=|\rho\cap\sigma|$, where $\rho$ and $\sigma$ are 012e- and 012n-rows of the same length. To fix ideas,
take $\rho:=(e_1,e_1,e_2,e_2,e_2,e_2)$ and $\sigma:=(n_1,n_2,n_1,n_2,n_3,n_3)$.
(The presence of entries 0,1,2 would only cause trivial changes in the sequel.)
Let (say) $N(\vec{e_1}\vec{n_3})$ be the number of bitstrings $x=(x_1,...,x_6)$ that simultaneously violate $e_1 e_1$
and $n_3 n_3$, these $x$'es being the four $x$'es having $x_1=x_2=0$ and $x_5=x_6=1$. It then follows from inclusion-exclusion that

(19)\quad $N=2^6-N(\vec{e_1})-N(\vec{e_2})-N(\vec{n_1})-N(\vec{n_2})-N(\vec{n_3})+N(\vec{e_1}\vec{e_2})+\cdots$

Unfortunately many of the $2^5=32$ summands $N(..)$ are zero, thus causing useless work. For instance $N(\vec{e_1}\vec{n_1})=0$ since no $x$ has $x_1=x_2=0$ and $x_1=x_3=1$.
To discard zero summands, consider the bipartite $\rho,\sigma$-{\it graph} $G$ whose five vertices are the $e$-bubbles $\{1,2\},\ \{3,4,5,6\}$ and the $n$-bubbles $\{1,3\},\ \{2,4\},\ \{5,6\}$. By definition two vertices are adjacent iff they intersect. Consequently a summand $N(..)$ in (19) is nonzero iff the vertices $\vec{e_i},\vec{n_j}$ appearing in $N(..)$ constitute an anticlique (=independent set) of $G$. For instance $N(\vec{e_1}\vec{n_3})\neq\emptyset$ because $\{\vec{e_1},\vec{n_3}\}$ "is" an anticlique since $\{1,2\}\cap\{5,6\}=\emptyset$. Since $G$ has only $11<32$ anticliques the calculation (19) boils down to

(20)\quad $N=2^6--N(e_1)-N(e_2)-N(n_1)-N(n_2)-N(n_3)+\\
\hspace*{1.7cm} N(e_1 e_2)+N(e_1 n_3)+N(n_1 n_2)+N(n_1 n_3)
+N(n_2 n_3)-N(n_1 n_2 n_3)=\\
\hspace*{1.7cm} 64-16-4-16-16-16+1+4+4+4+4-1=12.$

We mention in passing that apart from discarding zero terms, inclusion-exclusion can sometimes be accelerated (work in progress) by predicting the multiplicities of equal summands (enabling one to compute $4\cdot (-16)$ instead of $-16-16-16-16$).

{\bf 7.4} In 7.4.1 and 7.4.2 we deal with part (a) and (b) of the Main Quest respectively.

{\bf 7.4.1} Part (a) demands the following. Having used the transversal e-algorithm to represent $HS(\mathbb{H})$ as a disjoint union of $p$ many 012e-rows $\rho_i$, discard all bad $\rho_k$'s, i.e. the ones with $\rho_k\cap MHS(\mathbb{H})=\emptyset$! According to 7.2.1 we are in the position that dually $MC(\mathbb{H})$ has been represented as disjoint union of $q$ many 012n-rows $\sigma_j$. As previously argued $\rho_k$ is bad iff
$\rho_k\cap\sigma_j=\emptyset$ for all $1\le j\le q$. Fortunately it isn't necessary to invoke the inclusion-exclusion method 7.3 to decide whether or not $|\rho_k\cap\sigma_j|=0$. Due to Theorem? in [AntiHorn /\ Horn] this can be done much faster. Suffice it to say that the subtlety in Theorem? is to show that some easily verified necessary condition for $\rho_k\cap\sigma_j\neq\emptyset$ is also sufficient.

{\bf 7.4.2} By  the above we can assume that $MSH(\mathbb{H})$ has been represented as disjoint union of $p'$ many good 012e-rows $\rho_i$, i.e. $\rho_i\cap MSH(\mathbb{H})\neq\emptyset$ for all $1\le i\le p'$. Part (b) of the Main Quest asks us to further write each $\rho_i$ as a disjoint union of very-good 012e-rows.  Mach nur gutes konkretes Bsp statt den abstrakten Quark da unten.

Rest von 7.4 ausschlachten und weg:

Often  many intersections
$\rho_i\cap\sigma_j$ are empty (e.g. in the toy example above). Fortunately, the method of Section 8 decides emptyness  faster than inclusion-exclusion can tell  us $|\rho_i\cap\sigma_j|=0$, thus speeding up the calculation of $|MHS(\mathbb{H})|$.

This leads us to part (a) of the Main Quest, i.e. the pruning of bad rows.
Upon relabeling we can assume that $\rho_1,...,\rho_{p'}$ are exactly those $\rho_i$ which admit a $\sigma_j$ with $\rho_i\cap\sigma_j\neq\emptyset.$ Let $\Sigma(\rho_i)$ be the set of all these $\sigma_j$. It follows that $MHS(\mathbb{H})\subseteq\rho_1\uplus\cdots \uplus\rho_{p'}$ with exclusively {\it good} 012e-rows $\rho_i$.

AUSSCHLACHTEN fuer sec'Looking ahead':

The {\it duality-based} approach to sieve $MHS(\mathbb{H})$ from $HS(\mathbb{H})$ calls to help the $n$-{\it wildcard} $(n,n,...,n)$ which is dual to the $e$-wildcard and thus means 'at least one 0 here'. Thus by definition he 012n-row $(0,n,1,n,2)$ equals $(0,{\bf 0},1,{\bf 0},2)\uplus(0,{\bf 1},1,{\bf 0},2)\uplus(0,{\bf 0},1,{\bf 1},2)$.

A general 012e-row with $t$ many $e$-wildcards of lengths $\epsilon_1,...,\epsilon_t$ respectively expands in obvoius ways as a disjoint union of $\epsilon_1\cdots\epsilon_t$ many 012-rows. For instance, because of $(e,e)=(1,2)\uplus (0,1)$ and $(e,e,e)=(1,2,2)\uplus(0,1,2)\uplus (0,0,1)$,
$r$ in (16) expands into $\epsilon_1\epsilon_2=6$ rows:

(18)\hspace*{0.8cm} $(2,{\bf 1},e_2,0,1,e_2,0,{\bf 2},2,e_2)\uplus (2,{\bf 0},e_2,0,1,e_2,0,{\bf 1},2,e_2)\\
\hspace*{1cm} =\big(\ (2,1,{\bf 1},0,1,{\bf 2},0,2,2,{\bf 2})\uplus
(2,1,{\bf 0},0,1,{\bf 1},0,2,2,{\bf 2}) \uplus (2,1,{\bf 0},0,1,{\bf 0},0,2,2,{\bf 1})\ \big) \\
\hspace*{1cm} \uplus
\big(\ (2,0,{\bf 1},0,1,{\bf 2},0,1,2,{\bf 2})\uplus
(2,0,{\bf 0},0,1,{\bf 1},0,1,2,{\bf 2})\uplus (2,0,{\bf 0},0,1,{\bf 0},0,1,2,{\bf 1})\ \big)$

An expansion of $r$ like (18) is e.g. useful when the intersection of $r$ with another 012e-row is to be calculated. One then gets

$r \cap r'=\ (\ (2,1,1,0,1,2,0,2,2,2)\cap r')\uplus\cdots\uplus(\ (2,0,0,0,1,0,0,1,2,1)\cap r')$,

and all six intersections $\rho\cap r'$ are easily rewritten as 012e-rows. For instance:

\begin{tabular}{l|c|c|c|c|c|c|c|c|c|c}
	$\rho:=$ &  $2$ &  $1$ &  $1$ &  $0$ &  $1$ &  $2$ &   $0$&  $2$ &  $2$ &  $2$    \\ \hline

	$r':=$ &  $0$ &  $1$ &  $2$ &  $e_1$ &  $e_1$ &  $e_1$ &   $e_2$&  $e_2$ &  $e_2$ &  $e_2$    \\ \hline

	$\Rightarrow\rho\cap r'=$ &  $0$ &  $1$ &  $1$ &  $0$ &  $1$ &  $2$ &   $0$&  $e_2$ &  $e_2$ &  $e_2$    \\ \hline
\end{tabular}

COLD COFFEE (Eg Rado for very-good decision)

{\bf 8.3.2} We are now fit for a heuristic more systematic then the ad hoc arguments above, and  probably (tests  pending)  upgradable more efficiently than merely increasing the sampling taken from $min(r)$. Let us delve into details under the general assumption\footnote{It is an exercise to show that matters can always be reduced
	to this scenario.} that $ones(r)=twos(r)=\emptyset$ and that each member of $MinNotMC(\mathbb{H})$ extends to a member of $min(r)$, which hence is\footnote{Strictly speaking, $min(r)=\{\{z_1,..,z_t\}:\ (z_1,...,z_t)\in P_1\times\cdots\times P_t\}$.} the direct product of the position sets of the e-wildcards in $r$. We need to decide whether conversely each $Z$ in $P_1\times\cdots\times P_t$ contains some $Y$ in $MinNotMC(\mathbb{H})$ (which amounts to $r$ being bad). First suppose the fixed $Z=\{z_1,...,z_t\}$ in $P_1\times\cdots\times P_t$ does {\it not} contain any member of $MinNotMC(\mathbb{H})$ (so $Z\in MSH(\mathbb{H})$). Then $T:=(P_1\setminus\{z_1\})\uplus\cdots\uplus (P_t\setminus\{z_t\})$ cuts each $Y\in MinNotMC(\mathbb{H})$. In other words, $T$ is a transversal of $MinNotMC(\mathbb{H})$.
Conversely, any transversal $\Theta$ of $MinNotMC(\mathbb{H})$ of type $\Theta:=(P_1\setminus\{z_1'\})\uplus\cdots\uplus (P_t\setminus\{z_t'\})$ forces $\{z_1',...,z_t'\}$ to be in $MSH(\mathbb{H})$.

Whether a single set $\Theta$ of type $\Theta=Q_1\uplus\cdots\uplus Q_t\ (Q_i\subseteq P_i,|Q_i|=|P_i|-1)$ is a transversal can be tested fast with vertical layout. Trouble is the potentially large number $\epsilon_1\epsilon_2\cdots\epsilon_t$ of $\Theta$'s to be tested.
Therefore we content ourselves to {\it likely} find a transversal $\Theta$ (if one exists). The heuristic works as follows. Among all $\epsilon_1+\cdots+\epsilon_t$ many sets of type $Q=P_i\setminus\{z\}\ (1\le i\le t,\ z\in P_i)$ choose the one that cuts the most members of $MinNotMC(\mathbb{H})$. Say it is $Q'=P_3\setminus\{z'\}$. This gives rise to two index sets that will be updated repeatedly.
The first, $I_1:=\{1,...,t\}\setminus\{3\}$, contains the indices of the still pending e-wildcards. The second, $I_2$, contains the indices $j\in\{1,...,mnmc\}$ that belong to the $Y_j$'s cut by $Q'$. In the general step  among all sets $Q=P_i\setminus\{z\}\  (i\in I_1,\ z\in P_i)$ we pick the one that cuts the most {\it new} $Y_j$ (i.e. $j\not\in I_2$).
If the champion was $Q''=P_{i_0}\setminus \{z''\}$, then $I_1:=I_1\setminus \{i_0\}$ (using proramming syntax) and $I_2$ is augmented by all $j\not\in I_2$ with $Y_j\cap Q''\neq\emptyset$. Upon reaching $I_1=\emptyset$ one checks whether $I_2=\{1,2,\ldots,mnmc\}$. If yes, then $r$ is not bad. If no, then $r$ is 'likely bad'. The numerical experiments in Sec ? will estimate the error-probability of that message.

\section{Deciding  very-goodness using Rado's Theorem}

We call a final 012e-row $r_2$ {\it relevant} for a final 012e-row $r_1$ if $deg(r_2)<deg(r_1)$ and $ones(r_2)\cap (twos(r_1)\cup zeros(r_1))=\emptyset$. For instance in Table 9 below row $r_2$ (of degree 4) is relevant for $r_1$ (of degree 5).

(17)\quad  Suppose $HS(\mathbb{H})$ is represented as a disjoint union of final $012e$-rows, one of them being \\ \hspace*{1cm} $r_1$.   Then $r_1$ is {\it not} very-good iff  some row $r_2$ in the representation of $HS(\mathbb{H})$ is relevant  \\ \hspace*{1cm} for $r_1$ and is such that some $X\in min(r_2)$  is contained in some   $Y\in min(r_1)$.   \\ \hspace*{1cm} (We then call $(X,Y)$ a {\it witness-pair}.)

{\it Proof of (17).} Suppose first a witness-pair $(X,Y)$ exists. From $X\in min(r_2)$ follows that $X$ is a $\mathbb{H}$-transversal, minimal or not. Hence from $X\subseteq Y$ and $|X|=deg(r_2)<deg(r_1)=|Y|$ follows that $Y$ is {\it not} a minimal $\mathbb{H}$-transversal. So $r_1$ is not very-good.

Conversely, suppose $r_1$ is not very-good; say $Y'\in min(r_1)$ is not a minimal $\mathbb{H}$-transversal.
Let $X$ be any minimal $\mathbb{H}$-transversal contained in $Y'$. Let $r_2$ be the unique 012e-row to which $X$ belongs. Necessarily $X\in min(r_2)$, and so $deg(r_2)=|X|<|Y'|=deg(r_1)$. Further, from
$Y'\cap (twos(r_1)\cup zeros(r_1))=\emptyset$ (since $Y'\in min(r_1)$) and $ones(r_2)\subseteq X\subseteq Y'$ follows $ones(r_2)\cap (twos(r_1)\cup zeros(r_1))=\emptyset$. Thus $r_2$ is relevant for $r_1$ and $(X,Y')$ is a witness-pair. This proves (17).

\begin{tabular}{l|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
	&1 &2  &3  &4 & &5 & &6  &7 &8 & &9 &10 &11&  &12 &13 &14   \\ \hline

	& & & & & & & & & & & & & & & & & & \\ \hline

	$r_1=$ &  $0$ &  $0$ &  $2$ &  $1$ & & $1$ & & $e_1$ &$e_1$  & $e_1$& & $e_2$ & $e_2$ & $e_2$ & &$e_3$ & $e_3$ & $e_3$    \\ \hline

	$r_2=$ &  $e_1$ &  $e_2$ &  $e_3$ &  $e_2$ & & $1$ & & $e_2$ &$e_2$  & $e_3$ & & $e_3$ & $e_3$ & $e_2$ & &$e_1$ & $e_2$ & $e_2$    \\ \hline

	& & & & & & & & & & & & & & & & & & \\ \hline

	$c_1=$ &  $0$ &  $0$ &  $0$ &  $1$ & & $1$ & & $g_1$ &$g_1$  & $g_1$& & $g_2$ & $g_2$ & $g_2$ & &$g_3$ & $g_3$ & $g_3$    \\ \hline

	$c_2=$ &  $g_1$ &  $g_2$ &  $g_3$ &  $g_2$ & & $1$ & & $g_2$ &$g_2$  & $g_3$ & & $g_3$ & $g_3$ & $g_2$ & &$g_1$ & $g_2$ & $g_2$    \\ \hline

	& & & & & & & & & & & & & & & & & & \\ \hline

	$c_1'=$ &  $0$ &  $0$ &  $0$ &  $1$ & & $1$ & & $g_1$ &$g_1$  & $g_1$ & &$g_2$ & $g_2$ & $g_2$ & &$1$ & $0$ & $0$    \\ \hline

	$c_2'=$ &  {\bf 0} &  $0$ &  $0$ &  $g_2$ & & $1$ & & $g_2$ &$g_2$  & $g_3$ & & $g_3$ & $g_3$ & $g_2$ & &{\bf 1} & $0$ & $0$    \\ \hline

	& & & & & & & & & & & & & & & & & & \\ \hline

	$c_1''=$ &   &   &      &$1$ & & $1$&  & $g_1$ & $g_1$  & $g_1$ & &$g_2$ & $g_2$ & $g_2$ & &$1$ &  &     \\ \hline

	$c_2''=$ &   &   &      &$g_2$ & & $1$&  & $g_2$ & $g_2$   &$g_3$&  & $g_3$ & $g_3$ & $g_2$ & & $1$ &  &   \\ \hline

\end{tabular}

{\sl Table 9: Deciding the existence of a witness-pair with a Theorem of Rado}

Suppose in the representation of $HS(\mathbb{H})$ by $012e$-rows, $r_2$ is relevant for $r_1$. Is there a fast way to decide the existence of a witness pair $(X,Y)$? Yes there is, but it requires a modest knowlege of matroid theory, i.e. Rado's Theorem [R] which is phrased as statement (18) below. In order to illustrate it, let us return to the specific $r_1$ and $r_2$ in Table 9.
Because $min(r_1),\ min(r_2)$ is all that matters in (17), we write these set systems as $01g$-rows $c_1$ and $c_2$ in Table 9.

Notice that each witness-pair $(X,Y)$ for $c_2, c_1$ must have $X$ disjoint from $zeros(c_1)=\{1,2,3\}$. Thus we replace the first three components of $c_2$ by 0's. But this turns the wildcard $g_1g_1$ in $c_2$ to $(0,{\bf 1})$. Now ${\bf 1}$ in $c_2$ triggers a $1$ at the same location in $c_1$, which in turn transforms $g_3g_3g_3$ in $c_1$ to ${\bf 1}00$. The bottom line is, each witness-pair for $c_2,c_1$ necessarily is a witness-pair for $c_2',c_1'$. Generally $zeros(c_1')=zeros(c_2')$. Dropping the common 0's one gets two $g1$-rows $c_1'',c_2''$ with the same index set, in our case $E:=\{4,5,6,7,8,9,10,11,12\}$.

{\bf 7.1} That's when the matroid takes over. Namely, the partition $E=\{4\}\uplus\{5\}\uplus\{6,7,8\}\uplus\{9,10,11\}\uplus\{12\}$ determined by the 1's and $g$-wildcards of $c_1''$ defines a partition matroid $M=M(E)$. (By definition $X\subseteq E$ is $M$-independent iff $X$ cuts each part of the partition in at most one element.) In contrast,  the 1's and $g$-bubbles of $c_2''$ are not used for a second matroid but rather yield the set system $\{Q_i:\ i\in I\}$ in (18). In our case $I=\{1,2,3,4\}$ and
$Q_1=\{4,6,7,11\},\ Q_2=\{5\},\ Q_3=\{8,9,10\},\ Q_4=\{12\}$. Consequently, if $X$ is an $M$-independent transversal of $\{Q_i:\ i\in I\}$, then $X$ extends to a witness-pair $(X,Y)$ of $c_2'',c_1''$ (and each witness-pair arises this way). The existence of such witness-pairs is handled by the rank condition in statement (18). Take say $J=\{2,3,4\}$. Then

$|J|=3\le 4=rank(Q_2\cup Q_3\cup Q_4)=rank(\{5,8,9,10,12\})$.

One sees that generally the cardinality of $I$ in (18) equals $deg(r_2)$ which,  even for large hypergraphs $\mathbb{H}$,  often is a modest number (and whence all $J\subseteq I$ can be evaluated).

(18)\quad [Edmonds, Schrijver??] Consider any matroid $M$ on a set $E$  and any family $\{Q_i:\ i\in I\}$ of
subsets of $E$. Then  this family has a transversal which is $M$-independent iff\\
\hspace*{0.8cm} $|J|\le rank\Big(\bigcup\{Q_j:\ j\in J\}\Big)$ for all $J\subseteq I$.

redpajama_set_name: RedPajamaArXiv