2
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Always going for the minimum degree vertex seems to work? $\endgroup$
    – Laakeri
    Apr 22, 2022 at 23:32
  • $\begingroup$ 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. $\endgroup$
    – holf
    Apr 23, 2022 at 6:59
  • $\begingroup$ 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). $\endgroup$
    – a3nm
    Apr 23, 2022 at 8:22
  • $\begingroup$ 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? $\endgroup$
    – mhum
    Apr 27, 2022 at 22:45
  • $\begingroup$ @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. $\endgroup$
    – a3nm
    May 5, 2022 at 15:54

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – a3nm
    Aug 6, 2023 at 9:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.