Which hypergraphs can be simplified by alternatively removing a hyperedge and an isolated vertex?

Question

Let $H = (V, E)$ be a hypergraph, with $V$ the set of vertices and $E \subseteq 2^V$ the set of hyperedges. An elimination sequence on $H$ consists of alternatively removing hyperedges. Specifically, first remove an arbitrary hyperedge $e \in E$, then remove a vertex $v$ which must be an isolated vertex (i.e., it occurs in no edges, meaning it was isolated in the original hypergraph or only occurred in $e$), then remove a hyperedge, then remove an isolated vertex, and so on, until all hyperedges have been removed (you do not need to remove all vertices). (Unlike this earlier post, removing a hyperedge does not remove the vertices it contains.)

What is the complexity of deciding, given a hypergraph, if it admits an elimination sequence? It is clearly in NP; is it PTIME, or NP-hard?

For instance, the triangle (hyper)graph $(\{a, b, c\}, \{\{a, b\}, \{b, c\}, \{a, c\}\})$ does not have an elimination sequence: whatever the (hyper)edge you remove, there will be no isolated vertex and you are stuck. However, the same hypergraph when adding an additional vertex $d$ now has an elimination sequence. Any acyclic graph also has an elimination sequence, obtained by iteratively removing the parent edges of leaves and then the corresponding leaf, until only the root remains.

I believe that the problem is PTIME when restricted to graphs: first eliminate the edges of acyclic connected components, then for each remaining connected component with $n$ vertices and $m$ edges you must remove $m-n+1$ edges to make it acyclic and be able to eliminate it, and I believe you can greedily try an arbitrary order on the connected components. However, for hypergraphs I do not know how to generalize this, e.g., removing a hyperedge may make multiple vertices available for later steps. I do not know the complexity even if hyperedges are required to have a maximal arity of 3.

An alternative way to think about the problem is by reversing the direction of time: a hypergraph with an elimination sequence is one that can be obtained by starting from a set of vertices without hyperedges and alternatively adding isolated vertices and hyperedges. It is not clear to me how to characterize the hypergraphs that can be obtained in this way.

(The source of the question is an open problem on constrained topological sorts; see this page and look for "In particular". The specific problem, which is almost equivalent to the question here, is the following: given a directed bipartite graph $G = (U \sqcup V, E)$ with $E \subseteq U \times V$, can you find a topological sort of $G$ which alternates between vertices of $U$ and vertices of $V$, starting with $U$ and ending with $V$. Here $U$ corresponds to the hyperedges and $V$ to the vertices. To be precise the problem on topological sorts is equivalent to the problem in the question here, but posed on multigraphs, where the same hyperedge may occur multiple times.)

Answer 1

It is NP-complete to decide if a hypergraph admits an elimination sequence.

The reason is that it can be seen to be equivalent to the following problem: given $n$ subsets of $\{1,2,\dots, n\}$ (intuitively corresponding to the hyperedges), can we find an ordering of these subsets $S_1, S_2, \dots, S_n$ such that for all $1 \leq j\leq n$ we have $|\cup_{i > j}S_i| < n - j$. (Intuitively, for any $j$, after removing the first $j$ hyperedges, the number of vertices that are still covered by one of the remaining hyperedges is strictly less than $n-j$, i.e., there must be at least $j$ vertices available at that point).

In this paper by Fertin, Rusu and Vialette (ISAAC 2015), this specific problem is studied: it is called finding a stepwise bounded labeling of a collection of subsets, and it is used as an intermediate step in the NP-hardness proof of their main result. Specifically, the paper shows that the problem of finding a stepwise bounded labeling of a collection of subsets is NP-complete: this follows from Lemma 1 establishing that the problem is equivalent to that of deciding if a matrix is a pet matrix (i.e., has a permutation equivalent upper triangular matrix), and the latter is NP-hard by Theorem 1 of the paper (their main result).