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

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.)

• Always going for the minimum degree vertex seems to work? Apr 22, 2022 at 23:32
• I do not think so, aiming at edges with higher degree may "liberate" a great number of isolated vertices to be used later. Take the disjoint union of : $3$ isolated vertices, a $4$-clique, an $n$-clique, and the hypergraph with edges $e_i=\{x_i, y_1, \dots, y_{n^2}\}$ for $i=1,...,4$, and $4$-clique on $x_1, \dots, x_4$. By your strategy, you first remove edges in the isolated $4$-clique and at some point you do not have isolated vertices anymore to remove the rest. If instead you remove $e_1,\dots,e_4$ first by using the initial isolated vertices, you get $n^2$ isolated vertices to finish.
– holf
Apr 23, 2022 at 6:59
• Agreed with @holf, greedily removing edges adjacent to vertices of minimum degree does not work in general for the reasons he outlines (though I think it works in the case of graphs).
– a3nm
Apr 23, 2022 at 8:22
• Is it known if the basic necessary condition on the degree sequence (i.e.: if $v_1, v_2, \ldots, v_n$ are the vertices ordered so that $deg(v_i) \leq deg(v_{i+1})$, then $deg(v_i) \leq i$) is sufficient or not?
– mhum
Apr 27, 2022 at 22:45
• @mhum thanks for the idea, I agree that your condition is necessary, but it seems it is not sufficient. Take $V = \{a, b_1, b_2, b_3\}$ and the hyperedges $\{a\}$, $\{b_1, b_2\}$, $\{b_2, b_3\}$, $\{b_1, b_3\}$. Then $a$ has degree 1 and each $b_i$ has degree 2, satisfying your condition. However, there is no solution: either you remove hyperedge $\{a\}$, remove vertex $a$, and then you remove another hyperedge and are stuck; or you start by removing another hyperedge and you are stuck immediately.
– a3nm
May 5, 2022 at 15:54

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).