Fpt algorithm for hypergraph basis problem

Question

While working through the book Parameterized Complexity Theory of Flum and Grohe, I encountered exercise 1.42:

Let $H = (V, E)$ be a hypergraph. A basis of $H$ is a set $S$ of subsets of $V$ with the property that for all $e \in E$ there are $s_1, \dots, s_\ell \in S$ such that $e = s_1 \cup \dots \cup s_\ell$. The parameterized hypergraph basis problem is the following: Given a hypergraph $H$ and $k \in \mathbb{N}$ as an input ($k$ is also the parameter), decide whether $H$ has a basis of cardinality $k$.

The task is to show that this problem is fpt. For this, note that if $|E| > 2^k$, it follows immediately that we have a no-instance. If $|E| \leq 2^k$, we may assume that every vertex appears in at least one edge, otherwise we delete it. Therefore the number of vertices is bound by $2^k$ too. Now we are able to brute-force through the number $k$-element subsets of $\mathcal{P}(V) = \{ V' \subseteq V \}$ and test if this is a basis of $H$. This has running time $ O \left( { 2^{2^k} \choose k } \cdot |E| \cdot 2^k \right) $, which is quite bad, but it is fpt.

Edit: I recognized that this is not correct. You cannot bound the number of vertices like this as the hypergraph may not be uniform.

Is there a better solution? I found nothing alike in a quick google search.

Answer 1

Let's call two vertices $x,y\in V$ equivalent, if they aren't discerned by any hyperedge: For all $e\in E$ we have $x,y\in e$ or $x,y\not\in e$.

It does not make sense to discern equivalent vertices by basis sets. Thus, when searching for candidate bases, one can constrain oneself to unions of equivalent classes. You have already bounded $|E|$ by $2^k$. There are at most $2^{|E|}$ equivalence classes.