What we shall call the Major Unsolved Problem (MUP) is this: Given a hypergraph (=set system) H ⊆ P(W ), is it possible to enumerate the set minT r(H) of all minimal H-transversals in polynomial total time, i.e. polynomial in N := |minT r(H)|, w := |W |, and h := |H|? For the time being (more details in a later version of our draft) we content ourselves to refer to [GV] , [H1] , [EGM] for the history and the state of the art concerning the MUP. It is well known that the answer to the enumeration problem MUP is 'yes' iff this decision problem has the answer 'yes': (*) Given two hypergraphs H, G ⊆ P(W ), can one decide in poly(h, g, w)-time whether G consists of all minimal H-transversals?
Compare with this decision problem:
(**) For any hypergraph H ⊆ P(W ), can one decide in poly(h, w)-time whether any subset of W extends to a minimal H-transversal?
Again the answer to (**) is 'yes' iff the answer to MUP is 'yes'. Yet (**) is a bit crisper than (*) and, as will be seen, it affects MUP more directly. To glimpse why, we say a subset T of W is MC if each a ∈ T admits at least one 'critical' hyperedge H ∈ H in the sense that T ∩ H = {a}.
In [MU] it is shown that the set filter T r(H) of all H-transversals and the set ideal MC(H) of all MC-sets are such T r(H) ∩ MC(H) = minT r(H). This led to our condition (15) which pinpoints what property (technical but nicely concrete) T must have, apart from MC, to be extendible to a minimal transversal. To recap, the answer to the MUP is 'yes' iff (15) can be verified in polynomial time.
However, our main objective in this article is to initiate progress on a novel variant of the MUP. In the classic MUP 'enumeration' means 'one-by-one enumeration'. Our variant is happy to trade the badge 'polynomial total time' for a compressed enumeration of minT r(H) because this is what counts in practise. Our essential compression tools are 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 ∈ {0, 1} 8 satisfying x 1 = x 7 = 0, x 5 = 1, as well as |{i ∈ {2, 3, 4} : x i = 1}| = 1 and |{i ∈ {6, 8} : x i = 1}| = 1. We shall henceforth silently identify a bitstring like x = (0, 0, 0, 1, 1, 0, 0, 1) (incidently a member of c) with the set X = {4, 5, 8} in the usual way.
Here comes the Section break-up. Section 2 deals with exact hitting sets X ⊆ W , i.e. satisfying |X ∩ H| = 1 for all hyperedges H in H. The class EHS(H) of all hitting sets is a subclass of minT r(H) that is easier to handle (at least in our setting) than the whole of minT r(H). Call the 01g-row c feasible if c ∩ EHS(H) = ∅. A straightforward adaption of Knuth's Dancing-Links algorithm suggests itself as feasibility test. By Iterative Imposition of Hyperedges (IIH) we mean 1 that we keep on splitting feasible 01g-rows c into other 01g-rows c 1 , . . . , c t (called 'candidate sons') in a way that c = c 1 · · · c t . (Always means disjoint union.) Only the feasible candidate sons get promoted to 'sons', which are themselves processed likewise. In the end EHS(H) emerges in a compressed format, i.e. as a disjoint union of 01g-rows (Theorem 1). Consequently (Corollary 2) all perfect matchings of a K 3,3 -free graph can be enumerated (necessarily one-by-one here) in polynomial total time. Accepting randomization one can dispense with K 3,3 -freeness. Last not least, Section 2 introduces an equivalence relation on W which is induced by H ⊆ P(W ). Factoring out this equivalence relation is the first step in all our compression efforts, whether they target exact or minimal hitting sets.
All remaining Sections focus on the larger class minT r(H) ⊇ EHS(H), yet 01g-rows continue to play an important role.
Section 3 sets the stage for Section 4 by briefly reviewing the transversal 012-algorithm that represents the family T r(H) of all H-transversals as a disjoint union of 012-rows. Here '2' is the usual don't-care symbol. Section 4 targets minT r(H) in two ways. Either by sieving it from T r(H), or by targeting minT r(H) directly. The second way begs to check the feasibility (i.e. the non-emptiness of r i ∩ minT r(H)) of the intermediate 012-rows r. Whereas for exact hitting sets Dancing-Links was the default feasibility test, now condition (15) is called for help.
Sections 5 and 6 relate to each other the same way as Sections 3 and 4, but on a higher level. Namely, Section 5 reviews the transversal e-algorithm that represents T r(H) as a disjoint union of 012e-rows. Here e refers to the wildcard ee...e which demands 'at least one 1 here'. For instance the 012e-row r 1 = (0, e, e, e, 1, e , 2, e ) consists of all bitstrings x ∈ {0, 1} 8 satisfying x 1 = 0, x 5 = 1, as well as 1 ∈ {x 2 , x 3 , x 4 } and 1 ∈ {x 6 , x 8 }. The family of all inclusion-minimal X ∈ r, denoted as min(r), is easy to pinpoint. For instance min(r 1 ) consists of all sets Y ∪ {5} where Y ranges over the six transversals of {{2, 3, 4}, {6, 8}}. Section 6 targets the subfamily minT r(H) ⊆ T r(H). One way is to sieve minT r(H) from T r(H). Another way is to keep on splitting feasible 012e-rows r into candidate sons and picking the feasible ones. Feasibility testing on the 012e-level being no easier than on the 012-level (condition (15)), we postpone that issue to the entirely new framework of Section 7. Trouble also is, even a feasibilit test which is 'perfect' (=sufficient, necessary, and fast) would not deliver minT r(H) as nicely compressed as EHS(H) in Section 2. It just delivers a disjoint union r 1 · · · r R of 012e-rows that contains minT r(H) and is such that each r i is good in the sense that min(r i ) ∩ minT r(H) = ∅. If only each r i was very good in the sense that min(r i ) ⊆ minT r(H)! This is because r 1 = (0, e, e, e, 1, e , 2, e ) being very good implies min(r 1 ) = c 1 := (0, g, g, g, 1, g , 0, g ). Consequently, if all r 1 , . . . , r R are very good then minT r(H) = c 1 · · · c R is optimally compressed.
Our 'Main Quest' in the last three Sections 6 to 8 is (a) designing a decent (albeit nonpolynomial) feasibility test for 012e-rows, and (b) replacing good 012e-rows by very good 012erows. In Section 6 we make progress on part (b) by identifying very good rows (e.g. using Rado's Theorem) but it remains to make good rows very good. As to Section 7, the n-wildcard is dual to the e-wildcard and thus demands 'at least one 0 here'. One can use 012n-rows elegantly to accomplish both parts of the Main Quest. Unfortunately, creating these 012n-rows requires effort. In doing so we run into the problem of calculating minimal transversals of auxiliary hypergraphs H , i.e. the problem we started out with in the first place. The good news is, these H are smaller than the original hypergraph H. The technical reason for the abilities of our 012n-rows is the fact that their disjoint union equals MC(H). Recall, this set system has the property that MC(H) ∩ T r(H) = minT r(H). Hence it comes in handy that the emptiness of the intersection of a 012e-row with a 012n-row can be decided fast, although the proof of the method's correctness is nontrivial (Section 8). (4) and (8).) For instance, finding a solution to a Sudoku puzzle amounts to find an exact hitting set. See Corollary 2 for a graph-related occurence of exact hitting sets.
From the introduction recall the definition of g-wildcards and 01g-rows. The set Γ of positions occupied by the g-symbols of one fixed g-wildcard will be called a g-bubble. Thus the g-bubbles in the 01g-row c 1 := (0, g, g, g, 1, g , 0, g ) are Γ 1 = {2, 3, 4} and Γ 2 = {6, 8}. We also put ones(c 1 ) := {4} and zeros(c 1 ) = {1, 7}. Recall that we identify bitstrings x ∈ c with subsets X ⊆ [w] in the usual manner. Consider the hypergraph H 1 consisting of the three hyperedges (1) K 1 = {2, 3, 4, 6}, K 2 = {1, 2, 3, 4, 5, 7},
The family EHT (H 1 ) of all exact hitting sets with respect to H 1 can be rendered in a compressed format as
(2) EHT (H 1 ) = (g, 0, 0, 0, g, 1, g, g , g ) (0, 0, g, g, 0, 0, 0, g , g ) (0, 1, 0, 0, 0, 0, 0, 0, 0). It follows that EHS(H 1 ) houses precisely 3 · 2 + 2 · 2 + 1 = 11 exact hitting sets.
2.2 Let us explain how a type (2) compression is achieved. In order to impose an exact hitting set (say K = {1, 2, 3, 4, 5, 6}) on a given 01g-row (say 2 c 0 in Table 1 ), we employ a decomposition method whose accompanying pattern we like to call 3 an Abraham 0g0-Flag. Specifically, the Abraham 0g0-Flag in Table 1 is the boldface 4 × 6-rectangle whose 'diagonal' consists of gwildcards, with the understanding that each g-wildcard of length one "degenerates" to a 1-bit. 1 2 3 4 5 6 7 8 9 10 11 12 · · · 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 · · · The bitstrings (=sets) X ∈ c 0 that hit K in exactly one element i ∈ K come in four flavors dictated by the structure of c 0 ; either i ∈ {1, 2}, or i ∈ {3, 4}, or i = 5, or i = 6. Pleasantly, the corresponding mutually disjoint sets of bitstrings, call them c 1 to c 4 , can themselves be written as 01g-rows in obvious ways. Thus e.g. (g 1 , g 1 , .., g 1 , g 1 ) in c 0 becomes (g 1 , g 1 , .., 0, 0) in c 1 , and (.., g 2 , g 2 , .., g 2 ) in c 0 becomes (.., 0, 0, .., 1) in c 1 .
Adhering to previous terminology we call c 1 to c 4 the candidate sons of c 0 (that arise upon imposing K on c 0 ). When K is just one among many hyperedges in H pending to be imposed, we need to know which of the candidate sons c i are feasible in the sense that c i ∩ EHS(H) = ∅. Infeasible candidate sons should be cancelled because they can 4 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. Proof. In the next Section we carry out in detail the imposition of hyperedges in a broader context. We will find that for our particular problem the general formula becomes O(Rhwf eas (h, w) ).
An important kind of EHS 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 H := {star(v) : v ∈ V } ⊆ P(E), then the EHSes of H are exactly the perfect matchings 5 of G.
Corollary 2: All perfect matchings of a K 3,3 -free graph G can be enumerated in polynomial total time.
Proof. In our context each feasibility test performed by the EHS g-algorithm de facto on a 01grow c 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 e 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 -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 f eas(h, w) in Theorem 1 is bound by a polynomial in h, w, causing the overall algorithm to run in total polynomial time.
One can dispense with K 3,3 -freeness if one allows for randomization because deciding the existence of a perfect matching is in RNC [MR, p.347 ]. The case of bipartite graphs has been dealt with before [U] .
If this equivalence relation is the identity relation, then H is called thin, otherwise fat. For instance, if H is the hypergraph in Corollary 2 whose exact hitting sets are the perfect matchings of a graph, then H is easily seen to be thin.
For each index set I ⊆ [h] let H(I) be the set of x ∈ W which are in all K i 's (i ∈ I) and nowhere else. Formally 2.4 Suppose for some hypergraph H we managed (in whatever way) to write EHS(H) as a disjoint union of 01g-rows. Fix any g-bubble Γ = {a, b, . . .} of any 01g-row c and any X ∈ c. Then |X ∩ Γ| = 1 (by definition of g-wildcard), say X ∩ Γ = {a}. Let Y be the EHS obtained from X by substituting a with b. It then holds for all K i ∈ H that
Therefore a and b are H-equivalent. One concludes that each g-bubble of each final row is contained in an H-class.
Suppose the representation of EHS(H) via 01g-rows originated from the g-algorithm. Then, we claim, each g-bubble actually is an H-class. Indeed, inducting on the number of imposed hyperedges one sees that throughout the algorithm each g-bubble is a union of H-classes. The claim follows in view of the first part.
In particular, when applying the g-algorithm to a thin hypergraph, each final 01g-row must be a 01-row (=bitstring). For instance, applying the EHS g-algorithm to the thin hypergraph H 1 would give these final 01-rows:
1 2 3 6 8 1 0 0 1 1 0 0 1 0 1 0 1 0 0 0 One retrieves the right hand side of (2) from Table 2 by inflating each 1 at position k to a g-bubble as large as the class k (with the understanding that 1 stays 1 if k is a singleton).
What is the bottom line in all of that? A devil's advocate might argue: For thin hypergraphs the EHS g-algorithm offers no compression, and for fat hypergraphs H the compression can also be achieved by enumerating the EHSes of H with any algorithm, and then inserting g-bubbles in a trivial manner.
Here is the counter-argument. As elementary as it is, the whole concept of thin and fat hypergraphs seems to be new. Concerning 'any algorithm', again the author could not google any publication concerning the enumeration of all exact hitting sets of a general hypergraph. Actually the algorithm in [U] seems to be the only one that adresses the question for specific hypergraphs. The imposition of hyperedges via 0g0-Abraham-Flags and the Dancing-Link feasibility test go in tandem well. The a posteriori insertion of g-wildcards can be viewed as the icing on the cake. (A more subtle use of g-wildcards follows in later Sections.)
By way of a toy example in 3.1 we walk the reader through the (transversal) 012-algorithm 7 that generates the set T r(H) of all H-transversals. A cost analysis, in a somewhat broader framework, follows in 3.2. Only in Section 4 do we turn to the article's core, i.e. the minimal H-transversals.
3.1 Consider the hypergraph H 2 ⊆ P[6] with these h = 5 hyperedges
Akin to Section 2 we will produce T r(H 2 ) by imposing the hyperedges one after the other. We start with the powerset r 0 := P[7] = (2, 2, . . . , 2), see Table 3 . Here and in all 012-rows below '2' is a don't care symbol, i.e. it can freely be replaced by 0 or 1. Imposing H 1 upon r 0 yields the three disjoint candidate sons r 1 , r 2 , r 3 . Akin to Table 1 notice the boldface 3 × 3 Abraham 012-Flag (indexed by the rows r 1 , r 2 , r 3 and columns 1, 2, 5). In the present scenario feasibility testing, i.e. checking whether T r(H) ∩ r is empty, is much easier than later because it boils down to this condition which is testable in time O(wh):
(5) H ⊆ zeros(r) for all H ∈ H.
For H = H 2 all candidate sons r 1 , r 2 , r 3 are feasible and hence they survive. For all of them the hyperedge pending to be imposed is H 2 .
1 2 3 4 5 6 r 0 = 2 2 2 2 2 2 r 1 = 1 2 2 2 2 2 pending H 2 r 2 = 0 1 2 2 2 2 pending H 2 r 3 = 0 0 2 2 1 2 pending H 2 r 4 = 1 2 1 2 2 2 pending H 3 r 5 = 1 2 0 1 2 2 pending H 5 r 2 = 0 1 2 2 2 2 pending H 2 r 3 = 0 0 2 2 1 2 pending H 2 r 6 = 1 2 1 1 2 2 pending H 5 r 7 = 1 2 1 0 1 2 pending H 5 r 8 = 1 2 1 0 0 1 final r 5 = 1 2 0 1 2 2 pending H 5 r 2 = 0 1 2 2 2 2 pending H 2 r 3 = 0 0 2 2 1 2 pending H 2 Table 3 : Snapshots of the working stack of the transversal 012-algorithm applied to H 2 7 This is a unpublished 'baby' version of the e-algorithm discussed in Section 5. The theoretical issues in Section 4 are better discussed on the 012-level.
Always focusing on the top row of the LIFO (=Last In First Out) stack, imposing H 2 upon r 1 is governed by a 2×2 Abraham Flag and yields the candidate sons r 4 , r 5 , all of which happen to be feasible. Since r 5 happens to satisfy H 3 and H 4 , it has H 5 as pending hyperedge. Imposing H 3 upon r 4 yields the candidate sons r 6 , r 7 , r 8 . One of them, r 8 , happens to be final, i.e. it satisfies all H i ∈ H 3 . All bitstrings in r 9 being H 2 -transversals we store r 9 , like all final rows, in Table 4 (ignore its last column for the time being). When the transversal 012-algorithm terminates, i.e. when the working stack gets empty, T r(H 2 ) is represented as a disjoint union of the thirteen 012-rows in Table 3 , i.e. T r(H 2 ) = r 8 r 9 · · · r 23 . It follows that |T r(H 2 )| = 2+4+· · ·+1 = 29. 1 2 3 4 5 6 row-minimal sets r 23 = 0 0 0 1 1 1 456 r 22 = 0 0 1 2 1 1 356 r 20 = 0 1 0 1 1 2 245 r 19 = 0 1 1 0 0 1 236 r 18 = 0 1 1 0 1 2 235 r 17 = 0 1 1 1 2 2 234 r 14 = 1 0 0 1 2 1 146 r 13 = 1 1 0 1 2 2 124 r 12 = 1 0 1 0 1 1 1356, bad r 11 = 1 1 1 0 1 2 1235, bad r 10 = 1 0 1 1 2 1 1346, bad r 9 = 1 1 1 1 2 2 1234, bad r 8 = 1 2 1 0 0 1 136 Table 4 : The final rows obtained by feeding H 2 to the transversal 012-algorithm 3.2 Throughout the 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 τ = τ (H) := max{|H| : H ∈ H} candidate sons r i of r (by way of Abraham-Flags) costs O(τ w). Each set ones(r i ) is compared with all H ∈ H in order to find the pending hyperedge of r i . That costs O(τ hw).
Letting f eas(h, w) be any time bound for checking the feasibility of a 012-row we conclude that imp(h, w) = O(τ w + τ hw + τ f eas(h, w)). Therefore: the overall complexity of imposing the hyperedges of H in order to enumerate types of H-transversals is (6) The overall complexity of imposing the hyperedges of H in order to enumerate all H-transversals of specific type is O(Rh imp(h, w)) = O(Rhτ (hw + f eas(h, w))).
Thus (6) is a common 8 hat (allowing a variety of functions f eas(h, w)) for the enumeration, via R disjoint rows, of many kinds of transversals. Some kinds follow later, and two kinds we met already. Namely, if we look at all unrestricted H-transversals with respect to an unrestricted hypergraph H, then τ can only be bound by w, and f eas(h, w) = O(hw) by (5). Hence (6) implies:
(7) The 012-algorithm that enumerates all H-transversals runs in time O(Rh 2 w 2 ).
Second, for the EHS g-algorithm (and all subsequent algorithms) certainly feas(h, w) ≥ hw and again τ ≤ w is best possible here. Hence the bound in (6) becomes O(Rhwf eas(h, w)), which completes the proof of Theorem 1.
Although sometimes the whole of T r(H) is required (e.g. when calculating the expected trial length in Coupon-Collector problems), in many applications only the subset minT r(H) ⊆ T r(H) of all minimal transversals is desired. In 4.1 we establish that from T r
There are two ways to check each row-minimal set ones(r i ). In 4.2 we return to H for help, whereas in 4.3 the row-minimal sets are compared with each other.
Tackling minT r(H) has a long history. In 4.4 we formally state the Major Unsolved Problem (MUP, cf Introduction) and survey some results. We then define a supreme feasibility test (SFT) as one that goes beyond (5) by telling us whether any 012-row contains a minimal transversal. It is easy to see that a polynomial-time supreme feasibility test (PSFT) would settle the MUP affirmatively. Theorem 3 in 4.5 exhibits a PSFT for some natural class of MC-hypergraphs. Theorem 4 in 4.6 showcases a (non-polynomial) SFT for arbitrary hypergraphs which sparks Corollaries 5 and 6. The latter states that all minimal edge-covers of a graph can be enumerated in fixed-parameter polynomial total time. Table 4 is any good for sieving minT r(H 2 ). Notice that each 012-row r i in Table 4 has ones(r i ) as its unique row-minimal set. Because each X ∈ minT r(H 2 ) is contained in some final row r i , one has X = ones(r i ). It follows that the H 2 -minimal transversals are among these r i -minimal sets. For any hypergraph H we call a final row r i good if ones(r i ) ∈ minT r(H), and bad otherwise. For H = H 2 fourteen rows are good and four bad as indicated in Table 4 . For instance r 13 is bad because ones(r 13 ) = {1, 3, 5, 6} can be shrunk to the smaller transversal {3, 5, 6}. Using shorthand notation it follows that If one could prove that the number R of final rows r i generated by the 012-algorithm is bound by a polynomial p 1 (w, h, N ) then the MUP would be settled affirmatively. Indeed, as previously seen, checking the minimality of a fixed transversal ones(r i ) takes O(hw 2 ) time. In view of (7) one could hence enumerate minT r
Unfortunately experiments indicate that R cannot be polynomially bound by w, h, N . A con-clusive statement is however difficult 11 because the outcome strongly depends on the order in which the hyperedges are fed to the 012-algorithm.
Another way to tackle MUP attempts to upgrade the feasibility test (5) for 012-rows r to a supreme feasibility test that tells us whether r contains any minimal transversal. But when bad rows can be avoided, the number R of final 012-rows equals N = |minT r(H)|. Consequently the bound O(Rhτ (hw + f eas(h, w))) = O(Rhwf eas(h, w)) in (6) becomes O(N hwf eas(h, w)).
To summarize:
(10) With a supreme feasibility test of complexity f eas(h, w) one can enumerate (one-by-one) all N minimal H-transversals in time O(N hwf eas(h, w)).
Notice O(N hwf eas(h, w)) is polynomial total time whenever 12 f eas(h, w) is polynomial in h and w.
This prompts the following terminology adopted from [MU] .
It is evident that a subset of a MC-set is again a MC-set. Hence the family We stress that being a MC-set, even a maximal one, is not sufficient for being a minimal transversal, only necessary. For instance take H := {{1, 3}, {2, 4}, {3, 4}}. Then T = {1, 2} is a maximal MC-set yet not an H-transversal. The following was observed in [MU] but the phrasing (13) is particularly crisp:
For instance, consider the candidate sons r 7 , r 8 , r 9 of r 4 in Table 2 . The set T := ones(r 7 ) = {1, 3, 4} is not MC because crit(3, T ) = ∅ (check (4)). If r 7 had been cancelled right away, it would not have fathered the bad rows r 10 and r 11 . Similarly the non-MC set ones(r 8 ) is responsible for the bad rows r 12 and r 13 . As to (12), one can tackle minT r(H) from 'below' or from 'above'. Makurami and Uno [MU] tackle it from below by generating the facets of MC(H) one-by-one and discarding (or avoiding) the ones not in T r(H). In contrast we tackle minT r(H) from above; in the present Section on the 012-level, afterwards on the fancier 012e-level. We leave it to the reader to verify that (14) is equivalent to (15). Each phrasing has its benefits.
In the proof of Theorem 4 we stick to (15). (15)) is necessary and sufficient for the existence of a minimal H-transversal T containing T .
Proof. As to the sufficiency of (15), let T be as in (15) Case 2: Let x ∈ T . By assumption (15) there is H x ∈ D (picked from crit(x, T )) with
As to the necessity of (15), let T be any minimal H-transversal with T ⊆ T . Then T satisfies MC because of (10). Put T := T \ T . Then T is an H -transversal because for all H ∈ H it follows from T ∩ H = ∅ and T ∩ H = ∅ (since T is an H-transversal) that
Moreover T is a minimal H -transversal because otherwise T was no minimal H-transversal. In order to establish the existence of D in condition (15) let a ∈ T be arbitrary. It suffices to derive a contradiction from the assumption that T cuts each hyperedge in crit(a, T ). The contradiction will be that T \ {a} is an H-transversal (remember that T is a minimal H-transversal). In order to show that (T \ {a}) ∩ H = ∅ for all H ∈ H we make a case distinction according to the location of H.
Case I: H ∈ crit(a, T ). By assumption T cuts H and clearly Proof. By assumption, condition (14) can be met by a candidate son r i at most when T := ones(r i ) has ≤ k elements. 
. By (10) the overall complexity of our algorithm is O(N hwf eas(w, h)) = O(N h 2 w 2 d k ).
A small maximum degree d = d(H) does not force h to be small compared to w. It is e.g. easy to construct hypergraph families {H w : w > 0} such that for h(w) = |H w | one has lim w→∞ (h(w)/w) = ∞ yet d(H w ) = O(logw).
The hypergraph in Corollary 6 below has d = 2 and here h is small compared to w. Nevertheless the hypergraph is interesting, and we will best the bound O(Rh 2 w 2 2 k ) guaranteed by Corollary 5. Recall that a vertex-cover of a graph G is a vertex set S such that each edge of G is incident with a vertex in S. An edge-cover of G is an edge set X such that each vertex of G is incident with an edge in X. It is long known that all minimal vertex-covers of G can be enumerated in polynomial total time. Yet an analogous result for edge-covers does not 13 follow 'by duality'. Actually, the author could not google any publication concerning the enumeration of minimal edge-covers of a graph. To state Corollary 6 let m = m(G) be the cardinality of a maximum matching in G. If G has v vertices then m ≤ v/2 and the exact value of m can be found in polynomial time [NR] .
Corollary 6: Putting m = m(G) the N minimal edge-covers of G can be enumerated in time O(N 2 m v 6 ).
Proof. Again we work with the variant (14) (γ)). It follows that 'not a 3-path set' is necessary for being a MC-set. One easily verifies that it is sufficient as well.
How to decide whether a MC-set T admits a special choice D of critical hyperedges? Let G be the subgraph of G whose edge set is T (and whose vertices are the ones incident with T ). Because T is not a 3-path set, the t connected components of G are subsets S(α) of certain stars rooted at α. So the occuring α's form a t-element subset of the vertex set of G . Consider any S(α) and any edge {α, β} in it. There are at most two critical hyperedges for {α, β} ∈ T , namely star(α) and star(β). Case 1: S(α) is not a singleton, i.e. contains other edges apart from {α, β}. Then |T ∩ star(α)| = |S(α)| ≥ 2, and so star(α) is not critical for {α, β} ∈ T . But of course star(β) is critical for {α, β} ∈ T (otherwise T was a 3-path set). Let D 1 be the set of all these unique critical hyperedges star(β). Case 2: S(α) is a singleton, i.e. S(α) = {{α, β}}. Then {α, β} ∈ T has exactly two critical hyperedges, i.e. star(α) and star(β).
Since all edges {α, β} occuring in Case 2 constitute a matching in G, there are at most m of them; let's say exactly m for ease of notation. It follows that there are 2 m ways to extend D 1 to a choice D of criticals. Each fixed D has |D| ≤ v, and so it costs O(vw) to calculate D. Calculating all sets H \ ( D) in condition (14) also costs O(vw). It follows that checking the feasibility of a 012-row costs f eas(v, w) = O(2 m vw). By (10) the algorithm's overall complexity
One can speed up our algorithm as follows. If V is the set of vertices of G which are not vertices of G , then the stars rooted at the vertices in V are exactly the hyperedges of H . Consider now the graph G induced by V within G. If G happens to have no isolated vertices then T extends to a minimal transversal because every choice D of criticals satisfies H \ ( D) = ∅ for all H ∈ H . More generally, from the viewpoint of condition (15), it suffices to look at the minimal transversals of the hypergraph H ⊆ H corresponding to the isolated vertices of G .
As in Corollary 5 we have the option to additionally bound the cardinality of the edge-covers 13 Specifically, there are two common ways to dualize a graph. One can look at (a) the line-graph of G. Unfortunately the edge-covers of G are not the vertex covers in its line graph. Or one looks at (b) the hypergraphdual of G. While vertices and edges switch roles in the dual hypergraph, trouble is, the hypergraph-dual of a graph is no longer a graph. by k. For k < m there are no k-bounded edge-covers. For k = m = v/2 all N perfect matchings get enumerated in time O(N 2 m v 6 ). Although this is not polynomial total time, other than in Corollary 2 here we do not rely on K 3,3 -freeness, nor on randomization. (15) suggests to use again the 012-algorithm (and its supreme feasibility test) to find the minimal transversals of H . The feasibility test then incurs plenty other auxiliary hypergraphs, and so forth. For hypergraphs of bounded 'depth' (defined accordingly 14 ) this will lead to a third fixed-parameter polynomial total time enumeration of minT r(H). To recap, apart from fixed depth, in Corollary 6 we had fixed matching size, and in Corollary 5 fixed degree. Notice that fixed degree tractability has been handled before [H1, Sec.7 .3], albeit on the more distant level of (*) (see Introduction).
The e-wildcard (e, e, . . . , 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, . . . , 0). The so obtained 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. Thus (16) r = (2, e 1 , e 2 , 0, 1, e 2 , 0, e 1 , 2, e 2 ) by definition is the set of bitstrings (x 1 , . . . , x 10 ) which have x 4 = x 7 = 0 and x 5 = 1 and 1 ∈ {x 2 , x 8 } and 1 ∈ {x 3 , x 6 , x 10 }. The values of x 1 , x 9 being free the cardinality of r is (17) |r| = 2 2 · (2 2 − 1) · (2 3 − 1) = 84.
A general 012e-row with t many e-wildcards of lengths 1 , ..., t respectively expands in obvoius ways as a disjoint union of 1 · · · t many 012-rows. For instance, r in (16) splits into 1 2 = 6 rows:
(2, 1, e 2 , 0, 1, e 2 , 0, 2, 2, e 2 ) (2, 0, e 2 , 0, 1, e 2 , 0, 1, 2, e 2 ) = ( (2, 1, 1, 0, 1, 2, 0, 2, 2, 2) (2, 1, 0, 0, 1, 1, 0, 2, 2, 2) (2, 1, 0, 0, 1, 0, 0, 2, 2, 1) ) ( (2, 0, 1, 0, 1, 2, 0, 1, 2, 2) (2, 0, 0, 0, 1, 1, 0, 1, 2, 2) (2, 0, 0, 0, 1, 0, 0, 1, 2, 1) )
The row-cardinalities add up to 32+16+8+16+8+4=84, which matches (17). 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 ∩ r = ( (2, 1, 1, 0, 1, 2, 0, 2, 2, 2) ∩ r ) · · · ( (2, 0, 0, 0, 1, 0, 0, 1, 2, 1) ∩ r ), and all six intersections ρ ∩ r are easily rewritten as 012e-rows. For instance:
ρ := 2 1 1 0 1 2 0 2 2 2 r := 0 1 2 e 1 e 1 e 1 e 2 e 2 e 2 e 2 ρ ∩ r = 0 1 1 0 1 2 0 e 2 e 2 e 2 5.2 We now push the transversal 012-algorithm to the e-level. Applied to H 2 the (transversal) e-algorithm works as follows (more details in [W1] ). 1 2 3 4 5 6 r 1 = e 1 e 1 e 2 e 2 e 1 2 pending H 3 r 2 = e 1 e 1 2 1 e 1 2 pending H 4 r 3 = 2 2 1 0 1 2 pending H 5 r 4 = e 1 e 1 1 0 0 1 final r 5 = 1 2 2 1 2 2 pending H 5 r 6 = 0 e 1 1 e 2 pending H 5 r 7 = 0 2 0 1 1 2 pending H 5 r 3 = 2 2 1 0 1 2 pending H 5 It is evident that the top 012e-row r 1 in Table 5 satisfies H 1 and H 2 in the sense that each bitstring x ∈ r 1 (viewed as subset of [6]) cuts H 1 and H 2 . Since this is not the case for H 3 , the imposition of H 3 is pending. One verifies that the subset r 2 r 3 r 4 of r 1 consists of all x ∈ r 1 cutting H 3 . Akin to Tables 1 and 3 the splitting is governed by a kind of Abraham-Flag (in boldface). In r 2 the hyperedge H 4 is pending, in r 3 it is H 5 . But r 4 is final, i.e. r 4 ⊆ T r(H 3 ). We store ρ 1 := r 4 , like all final rows, in Table 6 and turn to the top row r 2 of the LIFO stack. One verifies that the subset r 5 r 6 r 7 of r 2 contains exactly the bitstrings that cut the pending hyperedge H 4 . We leave it to the reader to see how the current LIFO stack (consisting, from top to bottom, of r 5 , r 6 , r 7 , r 3 ) gives way to the final rows ρ 2 to ρ 6 in Table 6 ; for the time being ignore its last column.
1 2 3 4 5 6 row-minimal sets ρ 6 = 2 e 1 0 1 e 235, 356 ρ 5 = 0 e 0 1 1 e 245, 456 ρ 4 = 0 0 1 1 1 1 3456, bad ρ 3 = 0 1 1 1 2 2 234 ρ 2 = 1 e 2 1 2 e 124, 146 ρ 1 = e e 1 0 0 1 136, 236 Table 6 : Representing T r(H 2 ) as disjoint union of 012e-rows Table 6 represents T r(H 2 ) in a more compressed format than Table 3 . One gets again |T r(H 2 )| = |ρ 1 | + · · · + |ρ 6 | = 3 + 12 + 4 + 1 + 3 + 6 = 29, replicating the result in 3.1. Table 6 cannot be obtained by staring at Table 3 and trying to condense suitable groups of 012-rows into single 012e-rows. In short, there is no converse to the expansion of 012e-rows in Section 5.1.
If ρ is any final row produced by the e-algorithm fed with a hypergraph H, we write min(ρ) for the set of all ρ-minimal sets. Hence min(ρ) can be compactly represented by the 01g-row c obtained from ρ by replacing each 2 by 0, and each e-wildcard by a c-wildcard. In particular
As in Section 4 one argues that each minimal H-transversal is ρ-minimal for a unique ρ. Keeping the terminology of 4.1 call ρ bad if min(ρ) ∩ minT r(H) = ∅, and good otherwise. We additionally say that ρ is very good if min(ρ) ⊆ minT r(H). Therefore 'very good ⇒ good'. For instance, if ρ contains one minimum transversal, then all ρ-minimal sets are minimum transversals, and so ρ is very good.
6.1 In Section 4 it was enough to remove the bad final 012-rows from the likes of Table 4 . The remaining rows were automatically very good (which is equivalent to good in the 012-case). On the new 012e-level the matter bifurcates. Thus the Main Quest in the remainder of our article will be to (a) prune the bad rows, (b) replace each good row by a disjoint union of very good rows (without loosing minimal transversals).
For the final rows in Table 6 we can do (a) and (b) ad hoc: The bad row ρ 4 is dropped and all the others are very good because they happen to consist of minimum transversals. Recall, once all final rows are very good, one can switch from 012e to 01g. This yields a compact representation of minT r(H) as disjoint union of 01g-rows. For H = H 2 this is exemplified in Table 7. 1 2 3 4 5 6 c 6 = 0 g 1 0 1 g c 5 = 0 g 0 1 1 g c 3 = 0 1 1 1 0 0 c 2 = 1 g 0 1 0 g c 1 = g g 1 0 0 1 In the remainder of Section 6 we focus on part (b) of the Main Quest by finding two quite different criteria for a final 012e-row to be very good. The first is a sophisticated H-based way (as opposed to 4.2 it is based on inclusion-exclusion) which is discussed in 6.4. The second is akin to the comparison-based way of 4.3. It involves a Theorem of Rado about matroids and comes in Section 6.5. Sections 6.2 and 6.3 prepare the stage. Namely, 6.2 returns to thin/fat hypergraphs in the context of minimal transversals, and 6.3 presents preliminary numerical data, that hopefully wet the appetite to digest 6.4 and 6.5.
6.2 If the hypergraph H ⊆ P[w] is thin, then by 2.4 the EHS g-algorithm necessarily outputs EHS(H) one-by-one (Table 2 ). In contrast, the adapted e-algorithm has the potential to render minT r(H) in a compressed format even when H is thin. A case in point is minT r(H 2 ) in Table  7 .
What about enumerating minT r(H) when H is fat? To fix ideas, consider H 3 := {K 1 , ..., K 6 } defined by are any disjoint sets. In view of (4) it is evident that H 3 H 2 . A compressed representation of minT r(H 3 ) is immediately obtained from the compressed enumeration of minT r(H 3 ) minT r(H 2 ) above: 1a 1b 1c 2a 2b 3a 3b 3c 4a 5a 5b 6a 6b 6c c 6 = 0 0 0 g 1 g 1 g 2 g 2 g 2 0 g 3 g 3 g 1 g 1 g 1 c 5 = 0 0 0 g 1 g 1 0 0 0 1 g 2 g 2 g 1 g 1 g 1 c 3 = 0 0 0 g 1 g 1 g 2 g 2 g 2 1 0 0 0 0 0 c 2 = g 1 g 1 g 1 g 2 g 2 0 0 0 1 0 0 g 2 g 2 g 2 c 1 = 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 Table 8 : Getting minT r(H 3 ) from minT r(H 3 ) (in Table 7 ) by spreading the g-symbols
For general (fat) hypergraphs H we thus suggest to first build H; recall from 2.3 that this takes time O(hw 2 ). Then represent minT r(H) as a disjoint union of 01g-rows by your method of choice (be it H-based, comparison-based, or duality-based). Then, akin to the transition from Table 7 to Table 8 , inflate the result by replacing some g-symbols (or 1's) by new g-wildcards.
6.3 About two years ago the author sampled r-minimal sets in final 012e-rows r at random and checked whether they happened to be minimal H-transversals. For instance, a hypergraph H ⊆ P[1000] with 9 random hyperedges, each of size 200, gave rise to 15267 final 012e-rows with a total number of 162'397'626'819'255 (about 162 trillion) row-minimal sets. Of these 15267 rows 4948 were provably very good, and none was bad. As to the 10319 good rows r, taking random samples the approximated density d of minimal transversals among the r-minimal sets was as follows: 0.75 ≤ d < 1 for 8579 rows, 0.5 ≤ d < 0.75 for 1644 rows, 0.25 ≤ d < 0.5 for 96 rows. Thus there were more than 100 trillion minimal transversals.
Due to Covid-19, problems with Mathematica, but also due to new insights (e.g. speeding up the creation of candidate sons), fresh and systematic numerical experiments are postponed to the near future. The first step will be to evaluate how fat random 15 hypergraphs tend to be and how densely the minimal transversals are packed in the final 012e-rows when the hypergraph is thin. (Recall, different from exact hitting sets, minimal hitting sets can be compressed even for thin hypergraphs.) Afterwards the gadgets in 6.4 and 6.5 will be implemented and evaluated. The biggest effort will be to implement the ideas of Section 7. (Volunteer programmers are welcome!) A few benefits are obvious already. Like [T] , but unlike all other algorithms investigated 16 in [GV] , our algorithm can (i) compress its output (beyond the 012-level of Toda's BDD's) and it can (ii) count (like BDD's) all minimal transversals without generating them (see 7.1.1). Furthermore, different from [T] we support cut-off, i.e one can opt to only generate the minimal transversals of cardinality ≤ k. What is more, to the author's best knowledge, BDD's do not support distributed (=parallel) computing; but the e-algorithm does. In [GV, Sec. 5.4 ] the authors describe a collection of 128 million minimal transversals as 'enormous'. Well, using compression one can handle a million times that amount (see above). The reader too impatient to verify these claimed 'compression stunts' of wildcards is referred to [W1] , [W2] , to the article about Coupon Collecting (with Laurie, Svanson, Wagner), and to the most recent compression of all spanning trees of a graph (in the arXiv). They feature numerical experiments with wildcards in other contexts.
In order to state a criterion for a final 012e-row r to be very good (and thus to be replacable by a 01g-row), we say that X ⊆ [w] is a potential r-spoiler if there is a Y ∈ min(r) with X {a} = Y . Different r-minimal sets Y and Y can yield the same potential r-spoiler Y \ {a} = Y \ {b}, but only if a, b belong to the same e-bubble. We thus conclude that:
(20) The number of potential r-spoilers is P ot = ( 2 · · · t ) + ( 1 3 · · · t ) + · · · + ( 1 · · · t−1 ) + |ones(r)| · 1 · · · t .
For instance r in Table 9 has 12 + 8 + 6 + 2 · 24 = 74 potential r-spoilers. For later use the set system of potential r-spoilers is represented explicitely as c 1 · · · c 5 in Table 9 . For general r we define an r-spoiler as a potential r-spoiler that happens to be a H-transversal. The following is obvious:
(21) The 012e-row r is very good (with respect to some fixed hypergraph) iff there are no r-spoilers.
1 2 3 4 5 6 7 8 9 10 11 12 13 r = e 1 e 1 0 e 2 e 2 e 2 2 e 3 e 3 e 3 e 3 1 1 c 1 = g 1 g 1 0 g 2 g 2 g 2 0 g 3 g 3 g 3 g 3 0 1 c 2 = g 1 g 1 0 g 2 g 2 g 2 0 g 3 g 3 g 3 g 3 1 0 c 3 = 0 0 0 g 2 g 2 g 2 0 g 3 g 3 g 3 g 3 1 1 c 4 = g 1 g 1 0 0 0 0 0 g 3 g 3 g 3 g 3 1 1 c 5 = g 1 g 1 0 g 2 g 2 g 2 0 0 0 0 0 1 1 Table 9 : Counting r-spoilers by inserting 0's into 01g-rows and applying inclusion-exclusion
We can compute the number Sp of r-spoilers with inclusion-exclusion as
Here h = |H| as usual, and say N (i, j) is defined as the number of potential r-spoilers X with X ∩H i = X ∩H j = ∅. According to (21) row r is very good iff Sp = 0. Calculating 2 h terms N (..) may seem inefficient but when min(r) is large and h is moderate it beats spending O(hw 2 ) time on each X ∈ min(r) (as the naive H-based way in 4.2). Furthermore, based on the first three Bonferroni inequalities (google) these implications often alleviate full-blown inclusion-exclusion:
To illustrate (B1), suppose H 4 = {H 1 , · · · , H 4 } ⊆ P[13] has 12 ∈ H 1 , 13 ∈ H 2 , 12, 13 ∈ H 3 and H 4 := {5, 6, 7, 8, 9}. Then for all i = 1 we have 12 ∈ H 1 ∩ X for all X ∈ c i . Hence N (1) ≤ |c 1 | = 24. Similarly N (2) ≤ |c 2 | = 24. Further N (3) = 0 since H 3 ∩X ⊇ {12, 13}∩X = ∅ for all X ∈ c i and i ∈ [5]. As to N (4), see Table 9 for a compressed representation of the set systems c i := {X ∈ c i : X ∩ H 4 = ∅} for 1 ≤ i ≤ 5. It follows that N (4) = 4 + 4 + 2 + 4 + 2 = 16, and so
Therefore (B1) and (21) imply that r is not very good.
6.4.1 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 1 ≤ · · · ≤ t . Then each r-spoiler X can prevent at most t many r-minimal sets from being transversals. Therefore:
(23) If 1 ≤ · · · ≤ t−1 ≤ t and the number Sp of r-spoilers is smaller than 1 · · · t−1 , then r is good.
Although the bound 1 · · · 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) = ∅ and 1 = 2 = 3 = 4 = 3. The probabilities 'prob(good)' for r being good despite Sp being larger than 1 · · · t−1 = 27 were approximated by computer simulation 17 and are as follows: As to Sp = 105 in Table 10 , one has P ot = 1 2 3 + 1 2 4 + 1 3 4 + 2 3 4 = 108 because of ones(r) = ∅ and (20). Hence Sp ≤ 108. If Sp = 104 then the four missing r-spoilers could be the 3-element subsets of some X ∈ min(r). In this case X is a minimal H-transversal, and so r is good. Thus r is guaranteed to be bad only when 105 ≤ Sp ≤ 108.
It will also be interesting to see the applicability of (B2) because it is a cheap sufficiency test for very-goodness.
6.5 In order to elevate the comparison-based approach from 4.3 we define the degree of a 012erow as the common cardinalty of each member of min(r), thus deg(r) := |ones(r)| + t where t, as usual, is the number of e-bubbles. We call a 012e-row r 2 relevant for a 012e-row r 1 if deg(r 2 ) < deg(r 1 ) and ones(r 2 ) ∩ (twos(r 1 ) ∪ zeros(r 1 )) = ∅. For instance in Table 11 below row r 2 (of degree 4) is relevant for r 1 (of degree 5).
(24) Suppose T r(H) is represented as a disjoint union of 012e-rows, one of them being r 1 .
Then r 1 is not very good iff some row r 2 in the representation of T r(H) is relevant for r 1 and is such that some X ∈ min(r 2 ) is contained in some Y ∈ min(r 1 ).
(We then call (X, Y ) a witness-pair.)
Proof of (24). Suppose first a witness-pair (X, Y ) exists. From X ∈ min(r 2 ) follows that X is a H-transversal, minimal or not. Hence from X ⊆ Y and |X| = deg(r 2 ) < deg(r 1 ) = |Y | follows that Y is not a minimal H-transversal. So r 1 is not very good.
Conversely, suppose r 1 is not very good; say Y ∈ min(r 1 ) is not a minimal H-transversal. Let X be any minimal H-transversal contained in Y . Let r 2 be the unique 012e-row to which X belongs. Necessarily X ∈ min(r 2 ), and so deg(r 2 ) = |X| < |Y | = deg(r 1 ). Further, from Y ∩ (twos(r 1 ) ∪ zeros(r 1 )) = ∅ (since Y ∈ min(r 1 )) and ones(r 2 ) ⊆ X ⊆ Y follows ones(r 2 ) ∩ (twos(r 1 ) ∪ zeros(r 1 )) = ∅. Thus r 2 is relevant for r 1 and (X, Y ) is a witness-pair. This proves (24). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 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 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 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 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 c 1 = 0 0 0 1 1 g 1 g 1 g 1 g 2 g 2 g 2 1 0 0 c 2 = 0 0 0 g 2 1 g 2 g 2 g 3 g 3 g 3 g 2 1 0 0 c 1 = 1 1 g 1 g 1 g 1 g 2 g 2 g 2 1 c 2 = g 2 1 g 2 g 2 g 3 g 3 g 3 g 2 1 Suppose in the representation of T r(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 (25) below. In order to illustrate it, let us return to the specific r 1 and r 2 in Table 11 . Because min(r 1 ), min(r 2 ) is all that matters in (24), we write these set systems as 01g-rows c 1 and c 2 in Table 11 .
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 1 g 1 in c 2 to (0, 1). Now 1 in c 2 triggers a 1 at the same location in c 1 , which in turn transforms g 3 g 3 g 3 in c 1 to 100. 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}. That's when the matroid takes over. Namely, the partition E = {4} {5} {6, 7, 8} {9, 10, 11} {12} determined by the 1's and g-bubbles of c 1 defines a partition matroid M = M (E). (By definition X ⊆ 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 ∈ I} in (25). In our case I = {1, 2, 3, 4} and Q 1 = {4, 6, 7, 11},
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 (25). Take say J = {2, 3, 4}. Then , 8, 9, 10, 12}) .
One sees that generally the cardinality of I in (25) equals deg(r 2 ) which, even for large hypergraphs H, often is a modest number (and whence all J ⊆ I can be evaluated) . More details will be given in the numerical part of a future version of our article.
(25) Consider any matroid M on a set E and any family {Q i : i ∈ I} of subsets of E. Then this family has a transversal which is M -independent iff |J| ≤ rank {Q j : j ∈ J} for all J ⊆ I.
The duality-based approach to sieve minT r(H) from T r(H) calls to help the n-wildcard nn...n which is dual to the e-wildcard and thus means 'at least one 0 here'. Since the set-filter T r(H) can be compressed with 012e-rows ρ 1 , ρ 2 , . . ., by duality the set-ideal MC(H) (see (11)) should be compressible with 012n-rows σ 1 , σ 2 , . . .. We hope to convince the reader in 7.1 that such a MC(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 |ρ i ∩ σ j |. The details of calculating the MC(H)-representation follow in Sections 7.3 to 7.5.
7.1 For the time being please accept that MC(H 2 ) is the disjoint union of the 012n-rows in Table  12 . The σ j -maximal sets Y are written (in shorthand) to the right of σ 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 bad, good, very good for final 012n-rows as we did it for final 012e-rows. For instance, σ 4 in Table 21 is bad since σ 4 ∩ minT r(H 2 ) = ∅; all other rows happen to be very good. (That this behaviour matches the behaviour of the 012e-rows in Table 6 is coincidence.) 1 2 3 4 5 6 row-maximal sets σ 1 = 0 2 n n n 0 234,235,245 σ 2 = 0 n 1 0 n 1 236,356 σ 3 = 0 0 0 2 2 1 456 σ 4 = 0 1 0 0 0 1 26, bad σ 5 = 1 0 n n 0 2 136, 146 σ 6 = 1 1 0 2 0 0 124 In view of Table 6 and (12) we conclude that
For instance, ρ 5 ∩ σ 1 = {2, 4, 5}, ρ 5 ∩ σ 3 = {4, 5, 6} and otherwise ρ 5 ∩ σ j = ∅.
7.1.1 Letting H be arbitrary assume we have obtained a representation T r(H) = ρ 1 · · · ρ p with 012e-rows ρ i and a representation MC(H) = σ 1 · · · σ q with 012n-rows σ j . Then minT r(H) = {ρ i ∩ σ j : i ∈ [p], j ∈ [q]}, as argued above. Because one can calculate swiftly the cardinalities |ρ i ∩σ j | with inclusion-exclusion (7.2), this representation enables one to get the exact number |minT r(H)| of minimal transversals. For some purposes that may be sufficient. Often many intersections ρ i ∩ σ 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 |ρ i ∩ σ j | = 0, thus speeding up the calculation of |minT r(H)|.
This leads us to part (a) of the Main Quest, i.e. the pruning of bad rows. Upon relabeling we can assume that ρ 1 , ..., ρ p are exactly those ρ i which admit a σ j with ρ i ∩ σ j = ∅. Let Σ(ρ i ) be the set of all these σ j . It follows that minT r(H) = ρ 1 · · · ρ p with exclusively good 012e-rows ρ i .
7.1.2 Persuing part (b) of the Main Quest we next strive to expand each of these good ρ i 's into a disjoint union of very good rows. Evidently (26) ρ i = {ρ i ∩ σ j : σ j ∈ Σ(ρ i )} and each set system ρ i ∩ σ j , say ρ 1 ∩ σ 1 , consists entirely of minimal transversals. One may be tempted to get them explicetely like this. Similar to (18) write σ 1 as a disjoint union of 012-rows τ k . As in 5.1 all intersections ρ 1 ∩ τ k are easily recast as 012e-rows τ k . Unfortunately, because τ k consists entirely of mutually incomparable sets, it necessarily is a 01-row, i.e. only 'packs' one member of minT r(H).
Here comes a better method which has the potential to compress ρ 1 ∩ minT r(H). Suppose ρ 1 features three e-bubbles E 1 , E 2 , E 3 , each of length 1 = 2 = 3 = 5. We first expand each E i independently. Assume these three representations are obtained:
ρ 1 = ρ 1,1 · · · ρ 1,5 = ρ 1,6 · · · ρ 1,10 = ρ 1,11 · · · ρ 1,15 .
The first five ρ 1,j lack E 1 , the middle five E 2 , and the last five E 3 . Among the three expansions we pick the one which presumably leads to the fewest further branchings. In order to do so we use Σ(ρ 1 ) and inclusion-exclusion (details in 7.2) to determine |ρ 1,k ∩ minT r(H)| for all 1 ≤ k ≤ 15. This classifies each ρ 1,k as either very good, good, or bad. To fix ideas, say
• ρ 1,1 and ρ 1,2 are very good, and ρ 1,3 , ρ 1,4 , ρ 1,5 are just good.
• ρ 1,6 is very good, ρ 1,7 , ρ 1,8 are good, and ρ 1,9 , ρ 1,10 are bad.
• ρ 1,11 to ρ 1,14 are good, and ρ 1,15 is bad.
If we began to process ρ 1 by expanding E 1 then the three rows ρ 1,3 , ρ 1,4 , ρ 1,5 need to be further processed. If we expand E 2 , the two rows ρ 1,7 , ρ 1,8 need further processing. Expanding E 3 demands to look at four rows in the sequel. It thus makes sense to handle ρ 1 by first expanding E 2 . In the next step the e-bubbles of ρ 1,7 (and afterwards ρ 1,8 ) are inspected in likewise manner, and so forth. In the end one arrives at a representation of ρ 1 as a disjoint union of very good rows.
7.2 Here we show how inclusion-exclusion can be used to calculate the cardinality N := |ρ ∩ σ|, where ρ and σ are 012e-and 012n-rows respectively. To fix ideas, take ρ := (e 1 , e 1 , e 2 , e 2 , e 2 , e 2 ) and σ := (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 (e 1 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 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 · (−16) instead of −16 − 16 − 16 − 16).
7.3 For a set system B ⊆ P(W ) we say that X ⊆ W is a B-noncover if B ⊆ X for all B ∈ B.
Obviously the family N C(B) of all 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 B one by one to the n-algorithm renders N C(B) as a disjoint union of 012n-rows. (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 σ 1 , ..., σ 6 in Table 12 .
s 1 = n 1 2 n 2 n 2 n 1 n 2 s 2 = 0 2 n 2 n 2 2 n 2 s 3 = 1 0 n 2 n 2 0 n 2 s 4 = 1 1 0 2 0 2
Similarly the fact that 3 ∈ S e needs to be covered triggers e e in r 1 . Covering 4 ∈ S e amounts to impose the set {S a , S c } upon r 1 , which yields te final rows r 2 and r 3 . 8 The intersection of a 012e-row with a 012n-row
Recall 7.1 for the relevance of the problem stated in the title. We mention in passing that the result in Theorem 7 below also helps to compress the model set of Boolean functions of type 'Horn ∧ Anti-Horn'.
It is easy to see that the intersection of two 012-rows r and r is empty iff there is a 0-1-clash, i.e. either zeros(r) ∩ ones(r ) = ∅ or zeros(r ) ∩ ones(r) = ∅. The topic in Section 8 is to decide the emptiness of ρ ∩ σ when ρ is a 012e-row and σ a 012n-row. Apart from 0-1-clashes each of the following trivial reasons is sufficient for ρ ∩ σ = ∅:
• There is an e-bubble of ρ which is contained in zeros(σ)
• There is an n-bubble of σ which is contained in ones(ρ)
8.1 Yet the emptyness of ρ 0 ∩ σ 0 can have non-trivial reasons. For instance ρ 0 ∩ σ 0 := (1, 1, e, e) ∩ (n, n , n, n ) = (1, 1, e, e) ∩ (1, 1, 2, 2) ∩ (n, n , n, n ) = (1, 1, e, e) ∩ (1, 1, 2, 2) ∩ (n, n , n, n ) = (1, 1, e, e) ∩ (1, 1, 0, 0) = ∅ Setting ρ 1 := ρ 0 and σ 1 := (1, 1, 0, 0) ⊆ σ 0 we see that ρ 0 ∩ σ 0 = ρ 1 ∩ σ 1 , yet now ρ 1 ∩ σ 1 = ∅ by trivial reasons.
8.2 For general ρ 0 ∩σ 0 the trick above (associativity of set intersection) won't get us far. Instead we will reduce ρ 0 to ρ 0 ⊇ ρ 1 ⊇ · · · ⊇ ρ t and σ 0 to σ 0 ⊇ σ 1 ⊇ · · · ⊇ σ t such that either ρ t ∩ σ t = ∅ by trivial reasons, or ρ t ∩ σ t = ∅ by not-so-trivial reasons. To explain what we mean by 'reduce', consider ρ 0 and σ 0 in Table 13: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ρ 0 = 0 0 1 1 2 e 1 e 1 e 1 e 3 e 2 e 2 e 3 e 4 e 4 e 4 σ 0 = 2 n 1 n 4 n 3 n 3 n 2 n 1 n 2 n 3 0 n 3 1 n 4 n 4 n 3 ρ 1 = 0 0 1 1 2 e 1 e 1 e 1 e 3 e 2 e 2 e 3 e 4 e 4 e 4 σ 1 = 0 0 1 1 n 3 n 2 2 n 2 n 3 0 n 3 1 n 4 n 4 n 3 ρ 2 = 0 0 1 1 2 e 1 e 1 e 1 2 0 1 1 e 4 e 4 e 4 σ 2 = 0 0 1 1 n 3 n 2 2 n 2 n 3 0 n 3 1 n 4 n 4 n 3 ρ 3 = 0 0 1 1 2 e 1 e 1 e 1 2 0 1 1 e 4 e 4 e 4 σ 3 = 0 0 1 1 n 3 n 2 2 n 2 n 3 0 1 1 n 4 n 4 n 3 We obtain σ 1 by enforcing 20 the 0's and 1's of ρ 1 := ρ 0 upon σ 0 . Although σ 1 σ 0 , the reader should convince himself that ρ 1 ∩ σ 1 = ρ 0 ∩ σ 0 . Likewise we obtain ρ 2 by enforcing the 0's and 1's of σ 2 := σ 1 upon ρ 1 . Again ρ 2 ρ 1 yet ρ 2 ∩ σ 2 = ρ 1 ∩ σ 1 . After one more step we get ρ 3 ⊆ ρ 2 and σ 3 ⊆ σ 2 such that ρ 3 ∩ σ 3 = ρ 2 ∩ σ 2 = · · · = ρ 0 ∩ σ 0 .
8.3 In the example above, and in general, the reduction process stops as soon as ones(ρ t ) = ones(σ t ) and zeros(ρ t ) = zeros(σ t ), or because we find (as in 8.1) a trivial reason for ρ i ∩ σ i = ∅, and hence ρ 0 ∩ σ 0 = ∅. One of the two must eventually occur. Let us analyze the cost of this algorithm. As to imposing all 0's and 1's of ρ i upon σ i−1 , we first deal with the 0's. Determining whether a fixed 0 clashes with a 1 of σ i−1 (in which case we stop and announce that ρ 0 ∩ σ 0 = ∅ ) costs O(w). Otherwise the 0 meets a companion 0 in σ i−1 , or it switches a 2 to 0 in σ i−1 , or it lands within a n-bubble of σ i−1 whose other members it turns to 2. All of this again costs O(w). Doing this for all members of zeros(ρ i ) costs O(w 2 ). Imposing all 1's of ρ i upon σ i−1 works similarly except that additionally we check whether some n-bubble of σ i−1 falls into ones(ρ i ) (in which case ρ 0 ∩ σ 0 = ∅). Nevertheless, the total cost of imposing all 1's of ρ i remains O(w 2 ). By duality it also costs O(w 2 ) to impose all 0's and 1's of σ i upon ρ i−1 . Doing all of the above for all 1 ≤ i ≤ t costs t · O(w 2 ) = O(w 3 ). A more careful analysis would probably trim that bound.
Theorem 7: Given any 012e-row ρ 0 and any 012n-row σ 0 of the same length w, one can decide in time O(w 3 ) whether or not ρ 0 ∩ σ 0 = ∅.
Proof. For starters reduce the pair ρ 0 , σ 0 to the pair ρ 1 , σ 1 , and so forth, by mutually imposing 0's and 1's as shown in 8.2. In the process we might find trivial reasons for ρ i ∩ σ i to be empty (as in 8.1), in which case also ρ 0 ∩ σ 0 = ∅. Otherwise one arrives at ρ t , σ t satisfying ρ t ∩ σ t = ρ 0 ∩ σ 0 , as well as ones(ρ t ) = ones(σ t ) and zeros(ρ t ) = zeros(σ t ). As shown above, all of that costs O(w 3 ). Cutting off the common 0's and 1's shrinks ρ t to a 2e-row ρ t and σ t to a 2n-row σ t . For instance t = 3 in 8.2 and (upon re-indexing) ρ 3 = (2, e 1 , e 1 , e 1 , 2, e 4 , e 4 , e 4 ) and σ 3 = (n 3 , n 2 , 2, n 2 , n 3 , n 4 , n 4 , n 3 ).
The proof of Theorem 7 now reduces to showing ρ t ∩ σ t = ∅. We do this by inducting on the 20 Therefore (n1, n1) in σ0 becomes (0, 2) in σ1, and (n3, n3, n3, n3) becomes (1, n3, n3, n3), and (n4, n4, n4) becomes (1, n4, n4).
As usual let ρ be the 2e-row obtained by cutting off the first α − 1 components of ρ t . Similarly let σ be obtained from σ t . This is a well defined 2n-row because the assumption |N | ≥ 3 implies that the part n ..n has length ≥ 2. Further let r := (0, .., 0, 1) be of length α − 1. Let ρ be the concatenation of r and ρ. The 1 in r implies that ρ ⊆ ρ t . Similarly one obtains σ from r and σ. Notice that the part .... to the left of the first n in σ t may intersect several other n-bubbles. Fortunately the 0's in r ensure σ ⊆ σ t . By induction ρ ∩ σ = ∅, hence ρ ∩ σ = ∅. From ρ t ∩ σ t ⊇ ρ ∩ σ follows ρ t ∩ σ t = ∅.
Subcase B: All e-bubbles in ρ t and all n-bubbles in σ t have length 2. Since we exclude Case 1 each connected component C of the ρ t , σ t -graph (see 7.2) has cardinality ≥ 2, i.e. both e-bubbles and n-bubbles occur. If C contains at least two e-bubbles then, governed by the locations of the 2's) exactly four kinds of intersection patterns (a) to (d) arise; we shall illustrate the case of three e-bubbles. (If there is merely one e-bubble, then only cases (a),(b) occur). ρ t = 2 e 1 e 1 e 2 e 2 e 3 e 3 2 * .... * (a) σ t = n 1 n 1 n 2 n 2 n 3 n 3 n 4 n 4 #....# ρ t = 2 e 1 e 1 e 2 e 2 e 3 e 3 * .... * (b) σ t = n 1 n 1 n 2 n 2 n 3 n 3 2 #...# ρ t = e 1 e 1 e 2 e 2 e 3 e 3 * .... * (c) σ t = 2 n 1 n 1 n 2 n 2 2 #....# ρ t = e 3 e 1 e 1 e 2 e 2 e 3 * .... * (d) σ t = n 1 n 1 n 2 n 2 n 3 n 3 #....#
In all variants (a) to (d) let ρ be the 2e-row * ..... * and σ the 2n-row #.....#. Let ρ be the concatenation of (0, 1, 0, 1, ...) with ρ, and σ be the concatenation of (0, 1, 0, 1, ...) with σ. According to (a),(b),(c),(d) the length of the alternating 0, 1-pattern (0, 1, 0, 1, ...) is 8,7,6,6 respectively. One checks that ρ ⊆ ρ t and σ ⊆ σ t in all four variants. By induction ρ ∩ σ = ∅, hence ρ ∩ σ = ∅. From ρ t ∩ σ t ⊇ ρ ∩ σ follows ρ t ∩ σ t = ∅. This proves Theorem 7.