# Fpt algorithm for hypergraph basis problem

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.

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.