2
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.