Minimising the root-set of a spanning hyperforest of a hypergraph

Question

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.

Answer 1

This answer addresses the NP-hardness of the SPANNING SYMMETRIC HYPERFOREST ROOT SET (SSHRS) problem (given an undirected hypergraph $G$ and a number $k$, is there a spanning hyperforest with root set of size at most $k$ in the symmetric directed hypergraph $D_G$).

We prove that this problem is hard by reduction from the MAXIMUM UNIQUELY RESTRICTED BIPARTITE MATCHING (MURBM) problem (see https://link.springer.com/article/10.1007/s00453-001-0004-z for hardness). A uniquely restricted matching in a graph $B$ is a matching $M$ such that the induced subgraph of $B$ over the vertices of $M$ has exactly one perfect matching ($M$ itself). The MURBM problem asks for a given bipartite graph $B$ and a given number $n$ whether there exist a uniquely restricted matching in the graph with at least $n$ edges.

Note that a matching is uniquely restricted if and only if there exists no cycle in the graph whose edges alternate between being in the matching and not being in the matching. (This is easy to show, so the proof will not be included here).

The reduction from MURBM to SSHRS is simple: we are given a MURBM instance consisting of bipartite graph $B$ and number $n$. Suppose $B$ has vertex parts $V_1$ and $V_2$. Define $N(v)$ to be the set of neighbors of $v$ in $B$. Then define a hypergraph $G = (V, E)$ with vertices $V = V_1$ and edges $E = \{N(v)~|~v\in V_2\}$. Next, define $k = |V_1| - n$. In other words, construct the hypergraph $G$ whose bipartite graph model is $B$. Output $G$ and $k$ as the SSHRS instance output of the reduction.

The logic behind the reduction is this:

Choosing a spanning hyperforest in $D_G$ is equivalent to choosing a set of edges in $D_G$ subject to certain constraints. But choosing a set of edges in $D_G$ (subject to certain constraints) is equivalent to choosing a set of edges in $G$ and choosing a vertex to be the head from each (subject to certain constraints). Since a hyperforest allows no cycles, the same edge of $G$ directed in different ways cannot be used (as two such "duplicate" edges form a cycle). Since in a hyperforest the vertices have max in-degree one, the same vertex cannot be chosen as the head of multiple different edges. In other words, the choice of edges in $G$ and heads of those edges that comprises a choice of spannning hyperforest is equivalent to the choice of a matching in the bipartite graph model of $G$ (subject to certain constraints). But by construction, the bipartite graph model of $G$ is exactly the bipartite graph $B$, so choosing a spanning hyperforest in $D_G$ is equivalent to choosing a matching in $B$ subject to certain constraints.

What are those constraints? Well a hyperforest cannot have any cycles, and must have vertex in-degrees of at most 1. The vertex in-degree constraint is already met by any matching, so the only constraint is to have no cycles. But a cycle in the hyperforest corresponds to a cycle in the bipartite graph model of $G$ such that every second edge is in the corresponding "matching". Thus, the cycle-free condition of the hyperforest is equivalent to the condition that there exists no cycle in the graph whose edges alternate between being in the matching and not being in the matching.

Thus, hyperforests in $G$ correspond to uniquely restricted matchings in $B$. All that's left is to show that the parameters also match: that having a hyperforest with root set size at least $k$ corresponds to having a matching of size at least $n$. Every vertex in a spanning hyperforest has in-degree either 0 or 1, so the number of in-degree-1 vertices is equal to the total in-degree in the spanning hyperforest. But the total in-degree is also equal to the number of edges since each edge has exactly one head. Thus, the number of in-degree-1 vertices in the spanning hyperforest is equal to the number of edges. We also know that the size of the matching equals the number of edges in the hyperforest. Thus the size of the matching equals the number of in-degree-1 vertices in the hyperforest. Furthermore, the number of roots is by definition the number of in-degree-0 vertices. Thus, the size of the root set plus the size of the matching is equal to the number of vertices $|V| = |V_1|$. Therefore, the hyperforest has root set size at most $k = |V_1| - n$ if and only if the matching has size at least $n$.

Answer 2

This answer is wrong (question has changed)

This answer shows that the Spanning Hypertree Root Set problem is NP-hard, whereas the question now asks about the Spanning Hyperforest Root Set problem.

Answer

The $n$-uniform Hypergraph Spanning Tree Problem, which asks for a given undirected $n$-uniform hypergraph whether there exists a spanning hypertree, is NP-hard for any $n \ge 4$ (see The Steiner tree problem: a tour through graphs, algorithms, and complexity by Hans Jürgen Prömel and Angelika Steger).

An undirected hypergraph has a spanning hypertree if and only if the corresponding symmetric directed hypergraph has a spanning hypertree. Furthermore, any spanning hypertree has a number of roots that is at most the number of vertices. Thus, there is an easy reduction from the $n$-uniform Hypergraph Spanning Tree Problem to the $n$-uniform Spanning Hhypertree Root Set problem: given an undirected hypergraph, set $D$ to be the corresponding symmetric directed hypergraph and set $k$ to be the number of vertices in the hypergraph.

Thus, your problem is NP-hard, even if the hypergraph is restricted to be be $n$-uniform for some $n \ge 4$.