I am interested in the complexity of a problem involving spanning hyperforests (a union of hypertrees, which covers all of the vertices) of a $k$-hypergraph. I describe the relevant definitions for hypergraphs below, but the following is the problem on
SPANNING HYPERFOREST ROOT SET. For a directed hypergraph $D$ and an integer $k \geqslant 1$, determine whether there exists a spanning hyperforest for $D$ which has a root-set of size at most $k$.
Remarks.
- It is not difficult to show that SPANNING HYPERFOREST ROOT SET is in NP: in particular, if a root-set of the suitable size is provided, then a spanning hyperforest with that root-set can be found in polynomial time.
- It is also trivial to find a value of $k$ for which $(D,k)$ is a YES instance: for instance $k = \lvert V(D) \rvert$ (in which case the empty hypergraph is a spanning hyperforest with root set $k$).
- Considered as an optimisation problem, it is usually easy to find values $k < \lvert V(D) \rvert$ for which $(D,k)$ remain YES instances, though it is not clear how easily one can find the optimum.
Question.
Is SPANNING HYPERFOREST ROOT SET also NP-hard? Is this true in the special case where the input hypergraph is "symmetric", in the sense that for any edge $e = (t(e), h(e))$ and for any $v \in s(e) := t(e) \cup h(e)$, there is also an edge $e' = (s(e) {\,\smallsetminus\,} \{v\}, v)$?
Relevant definitions.
In the following, I am broadly following the definitions of "Flows on hypergraphs" [free PDF link] by Cambini, Gallo, and Scutellà.
- A hypergraph is a pair $G = (V,E)$, where $E \subseteq \mathcal P(V)$. If each $e\in E$ has the same cardinality $k$, we call $G$ a $k$-uniform hypergraph (or $k$-hypergraph).
- A directed hypergraph is a pair $D = (V,E)$, where in our setting we let $E \subseteq \mathcal P(V) \times V$ be the set of hyper-edges. For each edge $e \in E$, we let $t(e) = \pi_1(e) \subseteq V$ be the "tail" of the edge, and $h(e) = \pi_2(e) \in V \smallsetminus t(e)$ be the "head" of the edge. Thus we consider hypergraphs where each edge has exactly one head (more general definitions are common).
- We may associate a "symmetric" directed hypergraph $D_G = (V,E')$ of this sort to any hypergraph $G = (V,E)$, by replacing each undirected edge $e \in E$ with a collection of directed variants $E'_e = \{ (e{\,\smallsetminus\,} v, v) \,\vert\, v \in e \}$ and letting $E' = \bigcup_{e \in E} E'_e$.
A directed cycle in a directed hypergraph $D = (V,E)$ is just a vertex sequence $(v_0,v_1,\ldots,v_\ell)$ for which $v_{i+1} \ne v_i$ for $0 \leqslant i < \ell$, $v_0 = v_\ell$, and for which for each $0 \leqslant i < \ell$ there is an edge $e_\ell$ for which $v_i \in t(e_i)$ and $v_{i+1} = h(e_i)$.
A hyperforest is a directed hypergraph in which all vertices have in-degree either zero or one, and which has no cycles in the above sense. (N.B. I am diverging here from the terminology in my reference above, which does not explicitly consider whether the hypergraph is connected; but this cannot be taken for granted in my setting.) The set of nodes of in-degree zero we call the "root set" of the hyperforest.
A spanning hyperforest $T$ for a directed hypergraph $D = (V,E)$, is simply a subgraph $T \subseteq D$ of the hypergraph which contains all of the vertices $V$ and which is a hyperfohrest.