<p><strong>It is NP-complete to decide if a hypergraph admits an elimination sequence.</strong></p>
<p>The reason is that it can be seen to be equivalent to the following problem: given <span class="math-container">$n$</span> subsets of <span class="math-container">$\{1,2,\dots, n\}$</span> (intuitively corresponding to the hyperedges), can we find an ordering of these subsets <span class="math-container">$S_1, S_2, \dots, S_n$</span> such that for all <span class="math-container">$1 \leq j\leq n$</span> we have  <span class="math-container">$|\cup_{i &gt; j}S_i| &lt; n - j$</span>. (Intuitively, for any <span class="math-container">$j$</span>, after removing the first <span class="math-container">$j$</span> hyperedges, the number of vertices that are still covered by one of the remaining hyperedges is strictly less than <span class="math-container">$n-j$</span>, i.e., there must be at least <span class="math-container">$j$</span> vertices available at that point).</p>
<p>In <a href="https://www.researchgate.net/publication/281471293_Obtaining_a_Triangular_Matrix_by_Independent_Row-Column_Permutations" rel="nofollow noreferrer">this paper</a> by Fertin, Rusu and Vialette (ISAAC 2015), this specific problem is studied: it is called finding a <em>stepwise bounded labeling</em> 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).</p>

CC BY-SA 4.0
2023-08-06T09:57:08.280Z
I have discussed separately with Niranjan Kumar and this conclusively settles the question. Again, thanks a lot! This also establishes that the problem on topological sorts which is the initial motivation for the question is NP-hard as well.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-08-01T04:07:16.230Z
2023-08-06T09:56:07.163Z
2023-08-06T09:56:07.163Z
Niranjan Kumar
<p>Let <span class="math-container">$H = (V, E)$</span> be a hypergraph, with <span class="math-container">$V$</span> the set of vertices and <span class="math-container">$E \subseteq 2^V$</span> the set of hyperedges. An <em>elimination sequence</em> on <span class="math-container">$H$</span> consists of alternatively removing hyperedges. Specifically, first remove an arbitrary hyperedge <span class="math-container">$e \in E$</span>, then remove a vertex <span class="math-container">$v$</span> 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 <span class="math-container">$e$</span>), 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 <a href="https://cstheory.stackexchange.com/questions/16228/winning-strategy-of-an-edge-or-isolated-vertex-deletion-game">this earlier post</a>, removing a hyperedge does <em>not</em> remove the vertices it contains.)</p>
<p><strong>What is the complexity of deciding, given a hypergraph, if it admits an elimination sequence?</strong> It is clearly in NP; is it PTIME, or NP-hard?</p>
<p>For instance, the triangle (hyper)graph <span class="math-container">$(\{a, b, c\}, \{\{a, b\}, \{b, c\}, \{a, c\}\})$</span> 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 <span class="math-container">$d$</span> 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.</p>
<p>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 <span class="math-container">$n$</span> vertices and <span class="math-container">$m$</span> edges you must remove <span class="math-container">$m-n+1$</span> 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.</p>
<p>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.</p>
<p>(The source of the question is an open problem on constrained topological sorts; see <a href="https://paperman.name/prob/dag_page/" rel="nofollow noreferrer">this page</a> and look for &quot;In particular&quot;. The specific problem, which is almost equivalent to the question here, is the following: given a directed bipartite graph <span class="math-container">$G = (U \sqcup V, E)$</span> with <span class="math-container">$E \subseteq U \times V$</span>, can you find a topological sort of <span class="math-container">$G$</span> which alternates between vertices of <span class="math-container">$U$</span> and vertices of <span class="math-container">$V$</span>, starting with <span class="math-container">$U$</span> and ending with <span class="math-container">$V$</span>. Here <span class="math-container">$U$</span> corresponds to the hyperedges and <span class="math-container">$V$</span> 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.)</p>

CC BY-SA 4.0
2022-04-22T23:32:48.923Z
Always going for the minimum degree vertex seems to work?
Laakeri
CC BY-SA 4.0
2022-04-23T06:59:07.847Z
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
CC BY-SA 4.0
2022-04-23T08:22:13.517Z
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).
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2022-04-27T22:45:51.607Z
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
CC BY-SA 4.0
2022-05-05T15:54:13.750Z
@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.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2022-05-06T00:29:01.660Z
Ah, indeed. I suspected as much but couldn't come up with a counter-example right away.
mhum
<cc.complexity-theory><np-hardness><hypergraphs>
Which hypergraphs can be simplified by alternatively removing a hyperedge and an isolated vertex?
Antoine Amarilli 'a3nm'
# Which hypergraphs can be simplified by alternatively removing a hyperedge and an isolated vertex?

(Asked by: username_0 on 2022-04-22)

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](https://cstheory.stackexchange.com/questions/16228/winning-strategy-of-an-edge-or-isolated-vertex-deletion-game), 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](https://paperman.name/prob/dag_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.)

**Tags:** cc.complexity-theory, np-hardness, hypergraphs
> **Comments:**
> **username_1**: Always going for the minimum degree vertex seems to work?  
> **username_2**: 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.  
> **username_0**: 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).  
> **username_3**: 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?  
> **username_0**: @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.  
> **username_3**: Ah, indeed. I suspected as much but couldn't come up with a counter-example right away.  

---

## 1 answers

### Answer by username_4 on 2023-08-01. Score: 2 | Accepted answer

**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](https://www.researchgate.net/publication/281471293_Obtaining_a_Triangular_Matrix_by_Independent_Row-Column_Permutations) 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).

> **Comments:**
> **username_0**: I have discussed separately with Niranjan Kumar and this conclusively settles the question. Again, thanks a lot! This also establishes that the problem on topological sorts which is the initial motivation for the question is NP-hard as well.  

---

