Exact algorithms for finding minimum transversals in rank-3 hypergraphs.
We present two algorithms for the problem of finding a minimum transversal in a hypergraph of rank 3, also known as the 3-Hitting Set problem. This problem is a natural extension of the vertex cover problem for ordinary graphs. The first algorithm runs in time O(1.6538n) for a hypergraph with n vertices, and needs polynomial space. The second algorithm uses exponential space and runs in time O(1.6316n).
INTRODUCTION
Hypergraphs are a generalization of graphs, where the edges (called
hyperedges) may consist of 1, 2, or more vertices. A hypergraph is of rank
k if the largest hyperedge contains k vertices. A transversal, also known
as a hitting set or a vertex cover, is a subset T ' V of the vertices that
includes at least one vertex from every hyperedge.
Minimum Transversal, the problem of finding a transversal of minimum
cardinality for a hypergraph, is NP-complete, both in the general case
and for hypergraphs of maximum rank k ? 1 [6]. In this article, we will
only consider the problem when the hypergraph is of rank 3. Finding a
transversal of minimum cardinality is equivalent to finding an independent
set of maximum cardinality, but transversals are much more widely studied
for hypergraphs than independent sets.
Finding hypergraph transversals has applications in many areas, for
example artificial intelligence and database theory [4]. The particular situation
of finding a small transversal in a large rank-3 hypergraph is encountered
in computational biology, when computing evolutionary phylogenies
[3]. There is a close connection between computing the set of all minimal
transversals T r(H) of a hypergraph H and the data mining problem of
This research is partially supported by CUGS - National Graduate School in Computer
Science, Sweden.
finding maximally specific sentences that are interesting in a database [8].
Furthermore, the Minimum Transversal problem is a natural generalization
of the Vertex Cover problem for ordinary graphs.
Our algorithm is the first exact algorithm that we are aware of that
solves this problem in a time which is provably lower than O(2 n ). Some
algorithms for related problems could be used to solve Minimum Transver-
sal, but they do not provide any such guarantee. In particular, Niedermeier
and Rossmanith [13] have constructed an algorithm for the parameterized
version of our problem, where one tries to find a transversal smaller than a
given parameter k, which runs in time O(2:270 k +n). We will take a closer
look at the applicability of this and other previous algorithms in Section 3.
As for other related results, beyond the ones mentioned in Section 3,
there is an approximation algorithm for Minimum Transversal in [10], and
[5] deals with the Transversal Hypergraph problem in its most general form.
In the main part of the paper, we present two algorithms for Minimum
Transversal: one using polynomial space which runs in O(1:6538 n
and one which uses exponential space and runs in O(1:6316 n ) time. To
achieve these bounds, we do two things. First, we use a parameterized
algorithm, in this case the previously mentioned algorithm by Niedermeier
and Rossmanith [13], in an important subcase of our algorithm where a
low value for the parameter is proven to be possible. Second, we use a
method of analysis that takes the number of edges of cardinality 2 into
consideration without making the analysis overly complicated. Both of
these tricks may be useful in the construction of other algorithms as well.
This article is structured as follows. Section 2 contains various definitions
and minor results needed for the algorithm. Section 3 deals with
the topic of previous algorithms for our problem. Section 4 contains our
algorithms and their analyses. Finally, Section 5 contains our conclusions.
2. PRELIMINARIES
2.1. Basic definitions
A hypergraph is a generalization of a graph,
where the edges E i are arbitrary sets called hyperedges. The vertices of H
are
Sometimes H is given as a tuple (V; E) where V are the
vertices and E are the hyperedges, but for our purposes, our definition is
simpler.
n(H) is the number of vertices and jHj is the number of edges of H.
Usually, we will use just n and let the hypergraph be implied.
The rank of a hypergraph is defined as
In an r-uniform hypergraph, We will call an edge
of cardinality k a k-edge. An edge of cardinality 1 is called a loop.
The degree of a vertex d(x) is the number of edges E such that x 2 E.
We write the hypergraph under consideration is not clear from
the context. We define d k (x) or d k (x; H) to be the number of k-edges E
such that x 2 E.
A hypergraph is simple if, for all edges . Min(H) is
the hypergraph with edges Eg. In other words, it
is the hypergraph of all minimal hyperedges in H. Obviously, it is simple.
n is the complete r-uniform hypergraph with n vertices. Its edges are
all combinations of r of its vertices.
2.2. Transversals and independent sets
is a transversal of H if
transversal if no other transversal T 0 of H exists such that T 0 ae T . The
equivalent of a transversal in ordinary graphs is a vertex cover.
is an independent set of H if E 6' S for all edges
complement of an independent set is a transversal. S is maximal
if S is minimal.
The set of all minimal transversals T i of H is called the transversal
hypergraph T r(H). It is itself a hypergraph, and T
For proofs of these statements see [1]. -(H) is the size of the smallest
transversal of H, defined as
The Transversal Hypergraph problem is the problem of generating T r(H)
for a given hypergraph H. Naturally, if we know T r(H) we can solve the
Minimum Transversal problem by searching through T r(H) for the smallest
transversal, in O(jT r(H)j time. However, jT r(H)j may be exponential,
and potentially as large as O(2 n ).
2.3. Tur'an numbers
The Tur'an number T (n; p; r) is the minimum jHj for r-uniform hypergraphs
H with
Theorem 1. If H is a 3-uniform hypergraph with
l 6k+1\Gamma
Proof. Given that 1 - r - p - n (which is always true in a hypergraph),
de Caen [2] has shown:
r
If we set is an integer and 2=n - q -
(2)
In other words, if jHj ! 1\Gammaq
qn is an integer, then -(H) ?
not possible (by the definition of a Tur'an number), so
k. Solving for q, we get
one positive solution, and using this solution we get:
6k , and note that the condition that qn is an integer is
equivalent to the condition that f(k)\Deltan is an integer. Now, f(k) is a function
which for positive values of k is continous, monotonously increasing, and
assumes all values from 0 to 1, exclusively. Therefore, if f(k)
then there exists a k 0 - k such that f(k 0 )
then the theorem makes a trivial statement since
true for every 3-uniform hypergraph H.
3. OTHER ALGORITHMS
In this section, we will take a look at some algorithms for related problems
that could be applied to the Minimum Transversal problem.
3.1. Parameterized 3-Hitting Set
3-Hitting Set is equivalent to the Minimum Transversal problem for 3-
uniform hypergraphs. A nice algorithm for a parameterized version of this
problem, where one seeks a transversal T such that jT j - k for a given
parameter k, is presented by Niedermeier and Rossmanith in [13]. Their
algorithm runs in time O(2:270 k +n), and can easily be modified to return
a minimum hitting set.
By its parameterized nature, this algorithm is slower than ours when
k is large, and faster when k is low. In the general case, when k may be
as large as (for the hypergraph K 3
only achieves a
running time of O(2:270 n ), but when jHj is limited, Theorem 1 guarantees
better limits for -(H) and thus a better running time for their algorithm.
We use this in our algorithm to take care of an otherwise difficult case.
The details can be found in Section 4.
3.2. Transversal Hypergraph
Most applicable algorithms that we have found solve the Transversal
Hypergraph problem (defined in Section 2.2). These algorithms include
the classic algorithm by Berge [1], an improvement on it by Kavvadias and
Stavropoulos [9] which seems to behave well in experiments but for which
no theoretical results exist, and algorithms of theoretical interest by Eiter
and Gottlob [4] and Mishra and Pitt [12].
For these algorithms, there is either no proven upper bound on the
running time at all, or the best known upper bound is O(2 n ). This is
mainly due to the fact that these algorithms were designed with other
properties than a low total running time in mind, e.g. a low and predictable
delay between the output of the transversals. Another reason is that the
maximum size of jT r(H)j when H is a rank-3 hypergraph is unknown, and
may be as high as O(2 n ).
Note also that except for the algorithm by Kavvadias and Stavropoulos,
these algorithms usually require an exponential amount of memory.
4. THE ALGORITHMS
In this section, we will present our algorithm for the Minimum Transversal
problem. First we present the basic algorithm MinTr(H) (which needs
polynomial space) and its analysis, and then we show how it can be modified
to use exponential space for a lower running time.
In the algorithm, for a vertex x is the hypergraph fE 2
is the hypergraph Hg. Intuitively,
is the hypergraph that remains to be covered if x is included in the
transversal, and is the remaining hypergraph if x is not included
in the transversal. Sometimes we will say to mean that x is included
in the transversal, and vice versa.
A vertex x is dominated by another vertex y if x
every edge E 2 H. Note that if is in a loop or x
is dominated by some other vertex. This observation will be useful when
analyzing the algorithm.
4.1. The polynomial space algorithm
The algorithm MinTr(H) is basically a binary tree search, which uses
the algorithm by Niedermeier and Rossmanith [13] as a base case. It is
presented as a list of cases in Figure 1. The first applicable case is used
and the algorithm returns the smallest transversal. Note that there are two
different uses of min: min(A; B) for sets A; B returns the set of lowest car-
dinality, while Min(H) for a hypergraph H is the hypergraph minimization
operation defined in Section 2.1.
Algorithm: MinTr(H)
input: Hypergraph H
output: Smallest transversal of H
If H is empty, return ;.
1. If H is not simple, return MinTr(Min(H)).
2. If there exists some loop fxg 2 H, return fxg [
3. If some vertex x is dominated by some other vertex, or if
return
4. Let x be a vertex with maximum d(x) among all vertices with maximum
5. If there exists at least one 2-edge in H, pick a vertex x with maximum
d 2 (x) and a 2-edge fx; yg and return
6. If the maximum degree of any vertex in H is at most 4, use Nieder-
meier and Rossmanith's algorithm.
7. Finally, pick a vertex x with maximum d(x) and return
FIG. 1 Our polynomial space algorithm for Minimum Transversal
The algorithm uses three reductions, listed as cases 1-3, and the order
and manner in which a vertex is chosen for branching is designed to
maximize the creation of loops and 2-edges. The number of 2-edges is an
important feature in the analysis of the algorithm, given in the next section.
We will now prove the correctness of the algorithm, case by case.
The correctness of cases 0 and 1 should be apparent from Section 2.
For case 2, note that unless the edge fxg cannot be covered.
The correctness of case 3 follows from the following observation: If x is
dominated by y then every edge that is covered by can be covered by
1. This means that if there exists some minimum transversal T with
there exists another minimum transversal T 0 with x 62 T 0 and
For case 6, we refer to Niedermeier and Rossmanith's paper [13]. Every
remaining case tries both vertex v, which is clearly
an exhaustive search, and the last case catches all remaining situations.
Finally, note that since assignments are only done to one vertex at a
time, and since case 2 takes care of loops, the empty edge will never occur
in H.
4.2. Analysis of the algorithm
In this section, we will perform the analysis of the algorithm and show
that its running time is in O(1:6538 n ). For the analysis, a method by
Kullmann [11] is used. Consider the branching tree that the algorithm
implicitly constructs when applied to a problem instance. Let every edge
in the tree be labelled with a real, positive number t, representing the
reduction of complexity that occurs along that edge. If a node v in the
tree has d branches, labelled t 1 through t d , then the branching tuple for v
is and the associated branching number is the positive solution
of
d
The branching number is denoted -(t We consider any reduc-
tions, meaning cases which require only one branch to be examined and
thus can be implemented without any actual recursion, to occur locally
within a node of the tree, so that each node of the branching tree has at
least two children. In our algorithm, cases 1-3 are reductions. A hyper-graph
where none of the cases 1-3 apply is said to be maximally reduced.
The hypergraph which is associated with a node v of the branching tree is
the maximally reduced hypergraph dealt with in that node.
In our analysis, we use a real-valued function F (H) to derive the the
labels of the edges of the branching tree. Specifically, the label of an edge
linking a node v, with associated hypergraph H, to a child w of v, with
associated hypergraph H 0 , is F exact definition of F (H)
will be given in a moment, but for now, we only need to know that F (H) - 0
and that F (H) all labels of our branching
tree are guaranteed to be positive.
Under the conditions that 0 - F (H) - n(H) and that every label of the
branching tree is positive, the running time of the algorithm is O(poly(n) \Delta
is the highest branching number of the tree and poly(n) is a
polynomial in n. A proof of this, and further discussion of the method, can
be found in [11].
As F (H) we use a function that takes both n(H) and the number of
2-edges of H, henceforth named k, into consideration. Specifically, F
real-valued function such that
In other words,

The vales of \Psi(k)
we use a more fine-grained measure of complexity than the usual n, with
six sub-divisions between
One motivation for using this particular F (H) is that if the worst-case
running time of the algorithm is modelled using a two-variable recursion
then the values of T (n; settle into a pattern similar to c n\Gamma\Psi(k)
for some function \Psi(k) and constant c. Another motivation is that it seems
natural that having n variables and no 2-edges is slightly more difficult than
having n variables and one 2-edge, which is in turn more difficult than two
2-edges, and so on, and that no matter how many 2-edges we have, it is
always possible that they are all removed by the single assignment
which might lead to a maximally reduced hypergraph with
and no 2-edges. It is important to note, however, that the correctness of
the bounds given in this section does not rely upon either the optimality of
or any similarities between F (H), T (n; real-world worst-case
running times. For any \Psi(k) obeying the given rules you get a worst-case
branching number c such that the running time of MinTr(H) is O(c n ),
but if you use a non-optimal \Psi(k) then the constant c will be higher than
necessary.
For ease of presentation, the values of \Psi(k) are given here in Table 1.
Technically, numerical optimization is required to find these values, but
having them available beforehand simplifies the proof and makes it easier
to verify the claims. The process through which they were found will be
explained after the proof.
A note on the similarities and differences between our approach and
that of Kullmann in [11] might be in order, since the problems we solve are
related. A detailed comparison can of course not be given without a more
thorough review of his paper and the problem he is solving, but expressed
roughly, where we account for 2-edges according to a non-linear function
and have a complexity analysis where only local analysis of each
recursion is performed, Kullmann accounts for short clauses (corresponding
to our 2-edges) linearly, and instead uses a complicated non-local analysis
to get a good upper bound. While Kullmann's method might provide a
tighter bound, in exchange, the proof of this bound is complex and very
lengthy.
The main part of this section is Theorem 2, where we give a proof for the
time complexity of MinTr(H), but first we give a small lemma concerning
the time complexity of Niedermeier and Rossmanith's algorithm.
Lemma 1. Niedermeier and Rossmanith's algorithm runs in O(1:6484 n )
time for a 3-uniform hypergraph H of maximum degree 4 or less.
Proof. Since the maximum degree of H is at most 4, we have jHj -
")n=3. By setting Theorem 1 from Section 2.3
gives us -(H) ! d0:60962ne, where the ceiling function can be ignored for
a sufficiently large n. With this parameter, Niedermeier and Rossmanith's
algorithm has a running time of O(2:270 0:60962n
Theorem 2. MinTr runs in O(1:6538 n ) time.
Proof. Let k be the number of 2-edges in H. We will give the branching
numbers for the various cases of the algorithm, using the measure F
with the values for \Psi(k) given above.
Cases 0-3: Case 0 does not use recursion. Cases 1-3 are reductions,
as previously mentioned, and the value of F (H) is decreased when all applicable
reductions have been applied: The only situation which might
temporarily increase F (H) is when some 2-edges are removed by case 1,
but this can only occur if H contains at least one loop, and if so, then case
will reduce n(H) afterwards, resulting in a reduction of F (H) by at least
Case 4: In this case, we need to examine in detail how n and k change
in each branch of the branching. Assume that d 3
and for each branch examined let n 0 and k 0 be the number of variables and
2-edges remaining, respectively, after all reductions have been applied. We
will assume that no dominated vertices occur, as this would lead to easier
branchings. There are two branches.
In the H[x = 1] branch, q 2-edges are removed. No loops or new 2-edges
are created, so we have
In the H[x = 0] branch, p 3-edges are turned into 2-edges and q 2-edges
are turned into loops. Since H is minimal, the p 2-edges are new (i.e., do
not occur in H), unique, and disjoint from the loops, so k 0 - p. This also
guarantees that for every loop fvg 2
Thus, the maximum number of 2-edges removed by cases 1 and 2 is q \Delta q.
In total, n the worst case
for a particular q is always the case with a minimum k 0 .
k Formula for branching number Branching number

Cases for case 4, subcase d 2
k Formula for branching number Branching number

Cases for case 4, subcase d 2
The resulting branchings can be divided into 3 cases. First, if
then in the in the
branch. There is one worst case branching for this case for every
value of k, which is achieved when k 0 is minimal. This branching has the
using the values
in

Table

1 we find that all these branchings have a branching number of at
most 1:6538. For instance, if then the worst-case branching number
is
Note that if k ? 6 then the branching number is just -(1;

Table

2 contains the formulas for calculating the branching numbers for
these cases, along with the actual branching numbers.
Second, if in the
in the Once again, we have one
worst case with minimal k 0 for each value of k, and these are given in Table
3, both as formulas for calculating the branching numbers and as actual
branching numbers. Cases when k ? 6 are dominated by the worst case
since both parts of the tuple increase with increasing k.
Finally, if q - 3, then the worst case for each value of k is when
with in the in the
The branching formulas and branching numbers for values of q and k up
branching number Branching number

Cases for case 4, subcase d 2 (x) - 3
to 6 are listen in Table 4. d 2 (x) ? 6 or k ? 6 brings no worse cases, since
Case 5: For this case there are two subcases: d 2
Both will be proven to have a branching number less than 1:4143. Note that
vertex v with d 2 (v) ? 0, because otherwise domination or
case 4 would apply.
If d 2 assume that the edges containing x are fx; yg and fx; zg.
We know that 2. In
dominated by z. Both x and z will be taken care of by reductions. In
0] there is a loop fxg, and after it has been removed we have d(z) - 1. In
both cases at least 3 variables will be removed, so the branching number
is overestimated by -(3 \Gamma
Otherwise, d 2 In both branches
the variables x; y and the 2-edge fx; yg are removed and exactly one new
2-edge is created. Thus, k is unchanged and the branching number is
Case this case has a running time of O(1:6484 n ).
Case 7: Since d(x) - 5, the worst branching for this case is
1:6538. This is the final case of the algorithm, so
the proof is now completed.
On finding the values for \Psi(k). When the case analysis of the algorithm
is first performed, the precise values of \Psi(k) are not known but
have to be found by numerical optimization. We will now explain how this
optimization is performed.
For each branching B and each set of values for \Psi(k), we can calculate
the value of the branching number of B with the given - formula, so
given a branching B and a vector be the
corresponding branching number.
Enumerate the branchings occuring in the case analysis as
and let (x). For any vector x containing values for
\Psi(k) such that the running time of MinTr(H)
is in O(c(x) n ), so we want to find the x which minimizes c(x) under the
given conditions on \Psi(k).
Of course, for some branchings B i , such as those found in case 5 of
the algorithm, the value of B i (x) is good enough regardless of x. These
branchings do not have to be included in the optimization.
Note that for the particular algorithm we are analyzing in this section,
each B i (x) is continous as long as the conditions on x hold, so c(x) is
continous, which is a sufficient condition for standard algorithms to achieve
at least a local optimum.
4.3. The exponential space modification
By using an idea by Robson [14], we can lower the time bound to
we allow the algorithm to use exponential space. The idea is
to remember the result of the recursive algorithm for subsets V 0 ae V such
that jV 0 j - ff \Delta jV j for some ff and store them in some quickly accessible
data structure (like a balanced tree) so that these solutions only have to
be calculated once.
In [14], Robson did this for ordinary graphs, where there is exactly one
subgraph for each V 0 ae V . With hypergraps, however, several different
hypergraphs using the same vertices V 0 may be reached during the course
of the algorithm. If we start from a hypergraph H with vertices V and
an edge fx; reach a hypergraph H 0 with vertices
either the assignment
and or the assignment been made and there is a
possibility that fy; zg 62 H 0 .
One way to handle this is to take care of 2-edges and loops separately,
and only remember the results for 3-uniform hypergraphs. Suppose we
have a hypergraph H 0 with vertices . Any edges in H 0
that are not in H come from setting some vertex are therefore
smaller than 3. The edges of cardinality 3 in H 0 are exactly the edges of
cardinality 3 in H that use only vertices from V 0 , so there is exactly one
3-uniform hypergraph for every V 0 ae V .
Unfortunately, this method is not trivially extended to the algorithm
of Niedermeier and Rossmanith in a useful way, as the running time of
their algorithm depends on the value of the parameter k, not the size of

The vales of \Psi 0 (k)
the graph. Consequently, their algorithm potentially takes O(1:6484 n ) in
running time, regardless of caching, and if we want to find a better bound
for the running time than this, we cannot use their algorithm in this version
of our algorithm. The net result of not using their algorithm and instead
using this caching trick is, as stated, a running time in O(1:6316 n ).
Let MinTrNoNR(H) be MinTr(H) with the subcase calling Niedermeier
and Rossmanith's algorithm removed. The algorithm is still correct after
this modification, as the final case remains as a catch-all case. First, we
give the bound on the running time of MinTrNoNR(H), then we proceed
to give the details of the modification to use exponential space.
Lemma 2. MinTrNoNR(H) takes O(1:6737 n ) time for a hypergraph
with n vertices.
Proof. As the case analysis performed in Theorem 2 is valid for the
modified algorithm as well, for all but the final case, we give only a brief
version of the proof here.
The values for the new \Psi(k), called are given in Table 5.
Cases 0-3 are still valid, and are not affected by the change from \Psi(k)
to \Psi 0 (k).
For case 4, the case analysis is still valid and we need not repeat it
here, but the branchings get new branching numbers. Tables 6-8 give the
branching formulas and the new values for the branching numbers for this
case.
For case 5, the case analysis is still valid and the branching number is
still smaller than 1:4143 for the same reasons.
The old case 6 has been removed, and for the final case, the new worst
case is -(1; 1+ \Psi 0 now possible.
The values of \Psi 0 (k) were of course derived using the same method as
\Psi(k).
For a simpler way to look upon Robson's idea, imagine that the algo-
k Formula for branching number Branching number

Cases for case 4, subcase d 2 using \Psi 0 (k)
k Formula for branching number Branching number

Cases for case 4, subcase d 2 using \Psi 0 (k)
branching number Branching number

Cases for case 4, subcase d 2 (x) - 3, using \Psi 0 (k)
Algorithm: MinTrExp(H)
input: Hypergraph H
output: Smallest transversal of H, possibly taken from a lookup tree
If H is empty, return ;.
1. If we have a loop fxg 2 H, return fxg [
2. If some vertex x lies in more than one 2-edge, return
3. If 2-edges exist but no vertex lies in more than one, pick some edge
fx; yg of them. Return
4. If the solution has been previously calculated, return it.
5. Otherwise, pick some 3-edge fx;
and remember the result.
FIG. 2 Helper function for MinTr when n - ffn 0
rithm first fills the tree with all subsets V 0 such that jV
then starts working on H, halting the recursion whenever it has reached a
hypergraph with a pre-calculated solution.
The tree can be filled in time polynomial in n times its size. For a
certain 3-uniform H 0 with vertices pick an edge fx;
the branches H 0 Note that no assignment
is made to x in the second and third branches, or to y in the first and third
branches, etc. This branching is equivalent to looking up
in the tree. This way, only polynomial local work is needed
for every V 0 ae V in the tree.
Now, the rest of the algorithm. Let H 0 with n 0 vertices be the hypergraph
given in the initial call and let MinTr 0 (H) be MinTrNoNR(H)
modified to call MinTrExp(H), given in Figure 2, whenever
uses two different types of branchings: On the one hand,
those with branches
1], and on the other hand the standard branching with branches
0]. The correctness of the former branchings follows
from the definition of a transversal, and the correctness of the latter
branchings should be obvious.
Theorem 3. MinTr 0 (H) uses both time and space O(1:6316 n ) for a
hypergraph H with vertices V; jV
Proof. For the analysis, we view the algorithm as being split into one
tree-filling part and one search part.
Filling the tree uses time and space O(poly(n) \Delta
ffn
There is one
entry for every V ffn and there are
different
with we know that max 0-k-ffn
ffn
\Delta so the
number of entries in the tree is
ffn
ffn
We have already noted that the tree can be filled with only polynomial
local work for each entry.
To get a bound on the form O(- n ), we need some asymptotics for
ffn
We use Stirling's approximation (see [7]):
2-n
e
Ignoring the details of the polynomial factors, we have
ffn
e
e
e
poly(n) \Delta(ff ff
where, again, poly(n) is a part that grows polynomially. This is an asymptotic
bound on both the time and the space needed for this part of the
algorithm.
The search part of the algorithm is further divided into time spent
in MinTr 0 and time spent in MinTrExp. The time spent in MinTr 0 is
O(1:6737 (1\Gammaff)n ). The whole search tree for the MinTrNoNR algorithm
can be viewed as one search tree of depth (1 \Gamma ff)n with a search tree of
depth ffn attached to each leaf. The size of each of these lower search
trees is O(1:6737 ffn ). Since the total time for the MinTrNoNR algorithm
is O(1:6737 n ), we can see that the upper search tree has O(1:6737 (1\Gammaff)n )
leaves.
The time spent in MinTrExp is O(1:4656 ffn ). When MinTrExp is used,
at most ffn vertices remain. In this algorithm, case 1 is a reduction and
case 4 takes only polynomial time. Case 2 has a branching tuple of (1;
or better after case 1 is applied (with edges fx; yg; fx; zg, we get loops
fyg; fzg in branching number 1:4656. Case 3, finally,
leads to total work at most O(1:4143 n 0
if it is reached with n 0 remaining
vertices. If we reach case 3 then no further small edges will be created,
and case 3 will be used until case 4 is met. If the number of 2-edges is
b, we reach O(2 b ) leaves with polynomial work in each leaf. Since these
2-edges are all pairwise disjoint, b - n 0 =2 and the time needed is at most
ffn. The worst case of MinTrExp is
case 2.
Combining these two times, we have O(1:6737 (1\Gammaff)n ) calls to MinTr-
Exp, each of which spends O(1:4656 ffn ) time in a search tree. In total,
we have the time O(1:6737 (1\Gammaff)n 1:4656 ffn ) for the searching part of the
algorithm.
Now, we have two expressions to balance. The total running time of
MinTr 0 (H) is a sum of O((ff ff
where the first part increases with a growing ff (up to and the
second part decreases. The sum is of course dominated by the biggest term,
so we want to find the point of balance. We solveff ff
and get 0:19228. With this parameter, both the running time and the
memory usage for the whole algorithm are O(1:6316 n ).
5. CONCLUSIONS
We have constructed two algorithms for the Minimum Transversal prob-
lem. One needs polynomial space and runs in O(1:6538 n ) time, and one
needs both space and time O(1:6316 n ). To the best of our knowledge, these
are the first exact algorithms for this problem with a running time in O(2 n )
or better.



--R

North Holland
Extensions of a theorem of Moon and Moser on complete subgraphs.
Parameterized complexity: A framework for systematically confronting computational intractabil- ity
Identifying the minimal transversals of a hypergraph and related problems.
On the complexity of dualization of monotone disjunctive normal forms.
Computers and Intractability: A Guide to the Theory of NP-Completeness
Concrete mathematics: a foundation for computer science.
Data mining
Evaluation of an algorithm for the transversal hypergraph problem.
Approximating coloring and maximum independent sets in 3-uniform hypergraphs
New methods for 3-sat decision and worst-case analysis
Generating all maximal independent sets of bounded-degree hypergraphs
An efficient fixed parameter algorithm for 3-hitting set
Algorithms for maximum independent sets.
--TR
Identifying the Minimal Transversals of a Hypergraph and Related Problems
On the complexity of dualization of monotone disjunctive normal forms
Data mining, hypergraph transversals, and machine learning (extended abstract)
Generating all maximal independent sets of bounded-degree hypergraphs
New methods for 3-SAT decision and worst-case analysis
Approximating coloring and maximum independent sets in 3-uniform hypergraphs
Concrete Mathematics
Computers and Intractability
Evaluation of an Algorithm for the Transversal Hypergraph Problem
An efficient fixed-parameter algorithm for 3-hitting set

--CTR
Peter Damaschke, Parameterized enumeration, transversals, and imperfect phylogeny reconstruction, Theoretical Computer Science, v.351 n.3, p.337-350, 28 February 2006
minimum transversal;exact algorithm;hypergraph;3-hitting set