The Power of Bidegeneracy for Hypergraph Data Structures

The Power of Bidegeneracy for Hypergraph Data Structures Marco Bressan University of Milan marco.bressan@unimi.it

arXiv:2611.04900v1 [cs.DS] 3 Nov 2026

Giacomo Fumagalli University of Milan giacomo.fumagalli@unimi.it

Stefano Clemente University of Milan stefano.clemente@unimi.it Daniel Paul-Pena∗ The University of Sydney daniel.paulpena@sydney.edu.au

C. Seshadhri† University of California, Santa Cruz sesh@ucsc.edu

Abstract A hypergraph H = (V, E) describes a set system over a vertex universe V . It is increasingly popular in the network science community to store data as hypergraphs, instead of graphs, as hypergraphs can represent interactions between subsets of vertices. A natural challenge is to design a data structure for H to quickly answer basic questions about it. For example, one may ask how many neighbors a vertex v has, whether two hyperedges e and f intersect, or whether there exists a hyperedge containing a vertex subset S. The equivalent questions are trivial for graphs and can be answered by inspecting the adjacency list. The gold standard, from a data structures perspective, would be near-linear time preprocessing and query answering in (poly)logarithmic time. Since this is unlikely for arbitrary H, we ask for well-motivated hypergraph properties that can make such a goal possible. We introduce bidegeneracy, a measure of hypergraph sparsity that strictly generalizes many other measures, including bounded degree, bounded rank, and bounded ∞-degeneracy. While these parameters were exploited to accelerate specific tasks such as subgraph counting, we show that bounded bidegeneracy leads to fast hypergraph data structures. For a large set of fundamental queries like the ones above, we get near-linear time preprocessing and query answering in (poly)logarithmic time, even for the listing and sampling versions. Moreover, direct reductions from assumptions like the Orthogonal Vectors Conjecture suggest that these data structures require an almost-quadratic preprocessing or an almost-linear query time if one makes no assumptions on the input. Even if these conjectures may be false, it would only lead to tiny polynomial improvements over these bounds. On the technical level, we use bidegeneracy to compute a compressed representation of H and then perform careful reductions to stabbing and searching problems in Rd . Our framework significantly extends the well-studied “partial matching” problem of finding entries in database using a wildcard search. It also uncovers an intriguing connection between hypergraph sparsity, compression, and the computational complexity of hypergraph primitives. We also find that hypergraph datasets from the literature have remarkably low bidegeneracy, thus our results might have practical consequences.

∗ †

Work partially completed while the author was at the University of California, Santa Cruz Supported by NSF DMS-2023495, CCF-1740850, 2402572.

Contents 1 Introduction 1.1 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Main ideas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Manuscript organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 2 5 6 8

2 Hypergraph bidegeneracy and interval representations 2.1 Interval representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 From bidegeneracy to interval representations . . . . . . . . . . . . . . . . . . . . . .

8 9 10

3 Answering EdgeSat queries 17 3.1 Converting to a question on intervals . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 The algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.3 Proof of Theorem 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.4 Sat queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4 EdgePartialMatch and EdgeSat with fixed query size 22 4.1 The algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.3 Running time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.4 The special case N = ∅ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 5 Answering VertexNeigh queries 26 5.1 Computing N0 (v) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.2 Computing N1 (v) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 6 Lower Bounds 35 6.1 Reductions from Orthogonal Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 6.2 Reductions from SetDisjointness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 6.3 Reductions from Boolean Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . 37 A Auxiliary Proofs 39 A.1 Implications in Figure 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 A.2 Implementing primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 B Results on Orthogonal Range Searching

40

C Results on Stabbing 42 C.1 Segment tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 C.2 Proof of Theorem C.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 C.3 Proof of Theorem 5.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

2

1

Introduction

AI Methodology: All the main ideas were developed by the authors without the use of AI. AI was used to discover some basic lower bound arguments, verify the definitions, review existing proofs, and search for related literature. The authors also used AI for fixing typos and notation. All the writing was done solely by the authors, who stand by every line of this document. A hypergraph H = (V, E) is a representation of a set system, where each hyperedge e ∈ E is an arbitrary subset of the vertex set V . While set systems are studied extensively throughout combinatorics, there is an increasing trend in network science and data mining towards thinking of data in terms of hypergraphs [9, 18, 61, 62] (the recent survey [34] has hundreds of papers on this topic). By allowing for arbitrary hyperedge sizes, we can represent interactions beyond pairs. Many instances of real-world graphs are actually hypergraphs, where hyperedges are replaced by cliques. For example, while a coauthor network is represented as a graph, the raw data is a hypergraph. The vertex set consists of researchers and a hyperedge corresponds to the authors of a publication. Hypergraphs are a faithful model of the original data and practitioners suggest they should be analyzed directly. There are numerous software packages developed to process hypergraphs [40, 53, 58]. It is natural to view hypergraphs from a data structures perspective. Given a hypergraph H, we wish to preprocess and store H to answer basic hypergraph primitives. Consider the following natural primitives, many of which are used in practical algorithms. • Adj: given vertices u, v, decide whether there exists a hyperedge containing both u and v. The dual version, Int, asks to decide whether two given hyperedges e, f intersect. • Contain: given hyperedges e, f ∈ E, decide whether e ⊆ f . (We think of e, f as identifiers/pointers for the corresponding sets.) • EdgeNeigh: given hyperedge e, return the number of hyperedges intersecting it. The sampling version returns a uniform random hyperedge intersecting e and is a core primitive for hypergraph random walks [6, 23, 39]. • Superset: given a subset S of vertices, count the number of hyperedges f ⊇ S. In hypergraph mining, it has been used to show that the hypergraph structure can improve link prediction [11]. • SubH: return the subhypergraph induced by S. Specifically, list out all distinct, non-empty sets e ∩ S (over hyperedges e). Such operations are common in subhypergraph counting [16, 50]. S • Union: given a subset F of hyperedges, compute the union size | f ∈F f |. This quantity is used to measure the “density” of a set of hyperedges F [35]. • Venn: given three hyperedges, compute the “Venn diagram” of all intersection patterns between them. This specific structure is called a “hypertriangle” and is a core operation in practical algorithms for hypergraph motifs [36, 51, 63]. • VertexNeigh: given a vertex v, return the number of its neighbors. The listing version can be used to obtain the Gaifman graph of H, which is a key preprocessing step in many hypergraph algorithms. • EdgePartialMatch: given a set P of “positive” vertices and a set N of “negative” vertices, count the number of hyperedges that contain P and have no vertex of N . This classic problem was first posed 50 years ago in the context of database search [55] and has been heavily studied since [8, 19, 25, 32, 42, 47, 48]. We note that some of these operations are related and could be considered the dual of another one; many primitives are known under different names, such as set disjointness or subset containment. Nevertheless, we state them separately to see the rich landscape of basic primitives on set systems and their utility in practice. For graphs, these primitives are either trivial or vacuous. For bounded 1

rank hypergraphs (hyperedges have bounded size), these primitives can be solved by indexing each hyperedge e over all S ⊆ e. At the other end of the spectrum, for arbitrary hypergraphs, fine-grained complexity conjectures suggest that we can only get slight improvements over trivial algorithms. The trivial algorithms either (i) precompute and store solutions, or (ii) for each query, compute the answer by a full scan over the vertices/hyperedges. Even if these complexity conjectures are falsified [7, 44], it would only suggest small polynomial improvements over the trivial algorithms. The gold standard for such data structures is to achieve near-linear preprocessing time and (poly)logarithmic time to answer queries. Are there natural conditions on hypergraphs and a data structure framework that allows for quickly answering all these hypergraph primitives? These natural conditions should contain graphs and bounded rank hypergraphs and, if possible, contain properties currently used to accelerate hypergraph algorithms (such as the various hypergraph degeneracies used to list and count subhypergraphs). We would like to discover practically motivated classes of hypergraphs that contain non-trivial hypergraphs with unbounded rank.

1.1

Results

A new sparsity measure. One of our primary contributions is the notion of hypergraph bidegeneracy. We give a short overview of this concept and expand on it in §2. We can represent a hypergraph H = (V, E) as a Boolean incidence matrix MH ∈ {0, 1}n×m indexed by V and E, where MH [u, e] = 1 iff u ∈ e. The size of H, denoted ∥H∥, is the number of non-zeroes of MH . Definition 1.1 (Simplified version of Definition 2.3). A hypergraph H is κ-bidegenerate if every submatrix of MH with unique rows and columns contains a row or a column of Hamming weight at most κ. The inspiration for bidegeneracy comes from the classic notion of graph degeneracy. The degeneracy of a graph is the largest minimum degree of any subgraph and is a common measure of sparsity [22, 41, 43]. However, bounded bidegeneracy is a more general notion, as it looks at both rows and columns of MH . Every graph is 2-bidegenerate, and in general every rank r (the maximum cardinality of a hyperedge) hypergraph is r-bidegenerate. (Note that graphs can have unbounded degeneracy.) Several notions of hypergraph degeneracy have recently been proposed, including hypergraph l-degeneracy [50], hyperedge degeneracy [51], and (k, q)-cores [38]. As shown by the implication graph of Fig. 1, all these notions are subsumed by Definition 1.1. Since their parameters are typically small for real-world datasets [17], so is bidegeneracy (as we indeed find, see the remark below Theorem 1.4). One distinguishing feature of Definition 1.1 is that seemingly “dense” hypergraphs can have bounded bidegeneracy. Consider the hypergraph H with hyperedges e1 ⊂ e2 ⊂ . . . ⊂ en , where ei = {1, . . . , i}. The incidence matrix has Ω(n2 ) nonzeros, so ∥H∥ = Ω(n2 ). But H is 1-bidegenerate, since in every submatrix with unique rows and columns, the row of largest id has weight 1. All definitions of degeneracy mentioned above, instead, basically bound the sparsity of submatrices of MH , which is (mostly) equivalent to bounding the Hamming weight of rows/columns in all submatrices of MH . Another notable feature of bidegeneracy is that it is dual-invariant: if H is κ-bidegenerate, then so is H ⊤ , the hypergraph obtained by transposing MH . This means that running time bounds for a primitive, say Adj, transfer automatically to its dual, Int. For many previous notions of hypergraph degeneracy, this does not hold. Solving the primitives. We define two core primitives, called EdgeSat and VertexNeigh. We show in §A.2 that many common queries, including all those mentioned so far, can be easily solved 2

Graphs

Bounded degree

Bounded rank

Bounded hyperedge degeneracy

Bounded degeneracy of incidence graph

Bounded niceness

Bounded ∞-degeneracy

Bounded (k, q)-cores

Bounded bidegeneracy

Figure 1: We give strict implications between various notions of sparsity defined in the literature. Bounded bidegeneracy, introduced in this paper, is implied by all of them. See Section A.1. by these core primitives and their duals. These primitives are described as a Boolean condition over hyperedges (or vertices). The output is the number of solutions, that is, the number of hyperedges (or vertices) that satisfy the condition. We also consider the stronger version of weighted counting, sampling, and constant-delay enumeration. The weighted counting problem is to output the sum of weights of the solutions. The sampling problem is to output a solution with probability proportional to its weight. The constant-delay enumeration problem requires listing all distinct solutions with constant delay, after some setup computation (abusing notation, we simply say that the query takes time T , if the setup takes time T ). We show that both EdgeSat and VertexNeigh admit fast algorithms over bidegenerate hypergraphs. This implies fast algorithms for all the primitives mentioned above. For bounded bidegeneracy hypergraphs, we can answer (weighted) Adj queries in logarithmic time after a Õ(∥H∥) preprocessing. We give complementary conditional lower bounds suggesting that our dependence on the parameters (the bidegeneracy of H and the size of the query) cannot be reduced without blowing up the running time from near-linear to quadratic, or the query time from polylogarithmic to linear. The EdgeSat primitive. A vertex formula is defined as a Boolean formula φ over variables {xv : v ∈ V }; we denote by |φ| the size of φ. A hyperedge e can be represented by an incidence vector where the v-th coordinate is 1 iff v ∈ V (e). A hyperedge satisfies φ if the corresponding incidence vector satisfies the formula. Let φ(H) denote the set of satisfying edges. The primitive EdgeSat takes in input a vertex formula φ and outputs the size of φ(H). The dual VertexSat primitive is defined by edge formulas that are satisfied by vertices. This primitive generalizes the well-studied “partial match” problem. Our main result for EdgeSat follows. Theorem 1.2. For every t ≥ 1 there is an algorithm for EdgeSat with the following preprocessing and query time guarantees. Given an input a κ-bidegenerate hypergraph H: • Preprocessing: The algorithm constructs a data structure in time O(∥H∥κt−1 logt+2 ∥H∥). • Query time: Subsequently, the counting, sampling, and constant-delay enumeration of any EdgeSat query on t variables can be answered in time O(κ logt+2 ∥H∥). Note that the dependence on κ of Theorem 1.2 is only polynomial. Thus, as long as κ = ∥H∥o(1) , we have preprocessing time ∥H∥1+o(1) and query time ∥H∥o(1) . Therefore we can expect the algorithm to be effective in practice (it also does not hide large hidden factors). By some further optimization of Theorem 1.2, we can solve many basic primitives even faster. For example, we can solve the counting version of Adj(u, v), Int(e, f ), Diff(e, f ), Union(e, f ) in 3

p
O ∥H∥(κ + log∥H∥) log∥H∥ preprocessing time and O(κ log∥H∥) query time. Bounds only slightly higher hold for Venn(e, f, g). See Table 1 for a more complete list. We give also a second result for EdgeSat. The strength of this result is that the data structure can now answer EdgeSat queries of any length. The price to pay is a significantly worse dependence on κ, which makes the algorithm useful only as long as κ = o(log∥H∥/ log log∥H∥). Theorem 1.3 (Simplified version of Theorem 3.5). There is an algorithm for EdgeSat with the following preprocessing and query time guarantees. Given an input a κ-bidegenerate hypergraph H: • Preprocessing: The algorithm constructs a data structure in time ∥H∥ logO(κ) ∥H∥. • Query time: Subsequently, the counting, sampling, and constant delay enumeration of any EdgeSat query φ can be answered in time κO(|φ|) logO(κ) ∥H∥. The VertexNeigh primitive. The neighborhood of a vertex v is N (v) = {u |E(u) ∩ E(v) ̸= ∅}, where E(u) is the set of edges incident with u. The primitive VertexNeigh asks, given v, to compute |N (v)|. For hypergraphs, this problem is substantially harder than computing the degree (which is the number of incident hyperedges). For graphs, this problem is trivial. The dual query, EdgeNeigh, asks for the number of hyperedges that intersect with a given e. Theorem 1.4 (Simplified version of Theorem 5.1). There is an algorithm for VertexNeigh with the following preprocessing and query time guarantees. Given a κ-bidegenerate hypergraph H: • Preprocessing: The algorithm constructs a data structure in time ∥H∥ logO(κ) ∥H∥. • Query time: Subsequently, the counting, sampling, and O(log∥H∥)-delay enumeration of any VertexNeigh query can be answered in time (κ log∥H∥)O(κ) . Remark. The exponential dependence on κ of Theorem 1.3 and Theorem 1.4 may appear excessive for any real application. However, this is not the case. The full definition of bidegeneracy, Definition 2.3, actually uses a pair of parameters (κv , κe ), one for vertices and one for edges; and the full versions of our theorems, Theorem 3.5 and Theorem 5.1, depend exponentially in only one of them. For example, the bounds for VertexNeigh are exponential in κv , but only linear in κe (and only in the preprocessing!). We ran some preliminary experiments on the six real-world datasets used in [17], one of which has ∥H∥ ≃ 70M, maximum degree ≃ 30K, and maximum edge size ≃ 10K, and we found that in no case κv or κe exceeds 1477 when the other is 0. This suggests that the algorithms above can be fast in practice too. Lower bounds. Assuming the Orthogonal Vectors Conjecture, the bounds of Theorem 1.2, Theorem 1.3 and Theorem 1.4 are close to optimal: algorithms for these primitives have an exponential dependence on the bidegeneracy, or quadratic preprocessing time, or linear query time. Even if the conjecture fails (so there are, say O(n2−α ) time algorithms for Orthogonal Vectors), it would only mean that the lower bounds are worse by an nα factor. Theorem 1.5. If for some ε, δ > 0 there exists an algorithm for EdgeSat or VertexNeigh with 2o(κ) ∥H∥2−δ preprocessing time and 2o(κ+t) ∥H∥1−ε query time, where t = |φ| for EdgeSat and t = 0 for VertexNeigh, then the Orthogonal Vectors Conjecture fails. In particular, for VertexNeigh the dependence on κ cannot be improved beyond exponential (assuming truly subquadratic preprocessing and sublinear query time). The upper bounds for VertexNeigh cannot be extended to formulas, such as computing N (u) ∩ N (v), since by computing neighborhood intersections on graphs one can solve Set Disjointness; see Section 6. Thus, VertexNeigh is substantially harder than EdgeSat. 4

Further applications. We give some concrete applications of our results. The partial match problem: As mentioned earlier, the EdgePartialMatch problem has been studied in the context of database search [8, 19, 25, 32, 42, 47, 48, 55]. We think of the m hyperedges as vectors in {0, 1}n that form a database. The queries are vectors in {0, 1, ∗}n (where ∗ are wildcards) and our aim is to find a database vector matching the query. The vertices/dimensions labeled by 1 (resp. 0) form the positive set P (resp. negative set N ). Somewhat confusingly for hypergraph notation, in the partial match literature, our m is called n, while our n is called d. There is a rich literature of cell probe and communication lower bounds showing that we cannot get significant improvements in the worst-case over the trivial algorithms [32, 47, 48]. Significant effort has gone into just getting sublinear query time and near-linear storage with restrictions on the query [19, 25, 55], and a recent result gives an improvement for the limited wildcard setting [8]. In contrast, if the bidegeneracy is bounded, we get (log n)O(t) query time for t-sized queries with a near-linear sized data structure. Computing the Gaifman graph. The Gaifman graph of a hypergraph H (also known as projection graph, primal graph, or clique expansion graph) is the graph GH obtained by replacing every hyperedge by a clique, so that two vertices are adjacent in G if and only if they are in a common hyperedge of H. Computing GH is a fundamental step in many hypergraph mining applications. The naive approach to compute GH takes time O(∥H∥2 ), although it can be accelerated through fast matrix multiplication. If H is O(1)-bidegenerate, we can use VertexNeigh to list the neighbors of every vertex v and compute the adjacency list representation of GH in time Õ(∥H∥) + ∥GH ∥. Alternatively, we can use Adj to compute GH in time Õ(|V |2 ). We can also perform other operations on GH , such as power iteration by weighting vertices and collecting neighbor weights using VertexNeigh. More in general we can access GH through primitives such as Adj and VertexNeigh, without explicitly computing it. Hypergraph mining algorithms. Several hypergraph mining algorithms can be immediately rewritten or accelerated using our primitives. For instance, the hypergraphlet counting algorithm of [17] was carefully designed to bypass the quadratic lower bounds of Orthogonal Vectors by exploiting the so-called niceness of the hypergraph. However, that algorithm can be written entirely in terms of Adj, VertexNeigh, SubH and so on, and bounded niceness implies bounded bidegeneracy. In the hypertriangle counting algorithms of [37, 51], the expensive check of the intersection pattern of three edges takes O(κ log2 ∥H∥) time by a call to Venn. In hypergraphs with low bidegeneracy, random walks can be simulated efficiently [6, 23, 39]: for example, start from a hyperedge e1 , move to an intersecting edge e2 uniformly at random, and so on. The same holds for random walks over vertices. More in general one can efficiently perform walks over small connected subsets of vertices or hyperedges.

1.2

Related work

Graph degeneracy was first defined in the context of graph coloring and the seminal paper of Chiba-Nishizeki showed the relevance for clique counting [22]. There is a long history of exploiting degeneracy for subgraph counting [4, 12, 13, 14, 15, 22, 28, 31, 33, 45, 46, 52]. Refer to the short survey [57] for details. There are many notions of graph and hypergraph degeneracy. Closest to Definition 1.1 are the notions of ℓ-degeneracy [50], hyperedge degeneracy [51], and (k, q)-cores [38]. The term “bidegeneracy” has already been used, but only for graphs [10, 21]. All these notions are strictly contained in ours; refer to Figure 1 and Section A.1. At a first glance, the twin-width of a graph may seem related to our peeling procedure via the incidence graph of H. However, the twin-width of the incidence graph √ of H = Kn is Ω( n), see [5], but the bidegeneracy is just 2. 5

There are numerous software packages to process hypergraphs [40, 53, 58], underscoring the importance of having efficient data structures for storing hypergraphs. Currently, these packages do not support the rich primitives defined earlier. We believe that it would be quite influential to have practical implementations of the bidegeneracy ideas and primitives from this paper. Hypergraphs can be seen as databases, for which there is a large literature on query answering. On hypergraphs that are nowhere dense,1 every (Boolean) first-order query can be tested in constant time after a pseudo-linear-time preprocessing [56]. Unfortunately, nowhere density rules out even the class of all graphs, and it is too harsh a requirement to be useful in practice. The same issue is shared by many other measures of sparsity, such as treewidth or expansion [60]. The interval representation of Section 2 can be seen as a labeling scheme that assigns labels of O(κ log n) bits to vertices and edges; one can then decide whether v and e are incident by looking only at their labels. However, the relation with labeling schemes seems to end there; existing labeling schemes require H’s incidence graph to satisfy strong conditions, such as bounded cliquewidth [26].

1.3

Main ideas

Peeling the hypergraph. Starting from the seminal work of Matula and Beck [41] and Chiba and Nishizeki [22], graph degeneracy and vertex orderings have been shown to be tightly related. The classic algorithm to compute the graph degeneracy produces a “peeling” order of the vertices, wherein a vertex of currently minimum degree is repeatedly deleted. This ordering can be used to orient the input graph as a DAG of low outdegree. This DAG is the primary object that is algorithmically exploited for fast algorithms for bounded degeneracy graphs [13, 14, 24, 49, 52, 57]. The central fact is that, at the time of removal, a vertex has degree at most the degeneracy. There are a multitude of hypergraph degeneracy definitions. But all the corresponding algorithms go via a peeling procedure by minimum degree and use the central degree fact described above. When one thinks of bidegeneracy as a peeling procedure, things get complicated, because deleting a vertex can produce a hypergraph with multiple copies of the same hyperedge. To comply with the definition of bidegeneracy, one must now remove those copies, even though they may not have small size. Moreover, removed copies cannot be just forgotten, as they were distinct hyperedges in the starting hypergraph, and one would throw away information about the vertices they contain. The same holds for vertices (removing a hyperedge can create more vertices of the same type). These deduplication steps can interleave with the removal of vertices and hyperedges, cascading into a chain of operations. We handle these issues by constructing two directed binary auxiliary forests, one for vertices and one for hyperedges, that record the deletions of copies by the peeling process. The hyperedge forest TE has one leaf Xe for every hyperedge e, and the same for the vertex forest TV . To delete from the hypergraph the copy f of a hyperedge e, we actually delete both e, f and replace them with a new hyperedge ef containing the same vertices. This “merge” operation is then recorded in the hyperedge forest by adding one node Xef with Xe and Xf as child. When a hyperedge is deleted because it has size at most κ, instead, the corresponding node of TE is frozen—it remains forever the root of its subtree. The two forests are then used to construct the special representation of the hypergraph that is at the heart of our results. Note also that the process just described requires, upon any cancellation, to immediately detect whether new duplicated vertices or edges have been produced. By a careful choice of data structures, we can show that the whole procedure, including the construction of TV and TE , can be implemented deterministically in only O(∥H∥ ln1.5 ∥H∥). Compressing H via interval representations. Our main discovery is the notion of interval representa1

Formally, with an incidence graph coming from a nowhere-dense graph family.

6

tion of hypergraphs. The vertices and hyperedges of the hypergraph H are stored as ordered lists of identifiers, V and E . Then, we have a function I (resp. J ) that maps each vertex (resp. hyperedge) to a disjoint collection of intervals in E (resp. V ). The key property is that, if e and v are incident, then this incidence is certified by either e being in one of the intervals of I(v), or vice versa (but not both). In all this, the bidegeneracy κ bounds from above the number of intervals in each of the mappings I(v) and J (e). We can show that an interval representation of H can be obtained from the forests TV and TE . This entails performing a postorder traversal to determine the order of the leaves, which yields precisely V and E . Afterwards, for every vertex v of the hypergraph we locate at most κ subtrees in TE . A symmetric procedure yields the intervals for the hyperedges. Definition 2.4 gives the formalism for interval representations and §2 gives the details on efficiently computing them. The matrix viewpoint leads to the following deeper observation. The interval representation implies that, under a suitable permutation of indices, we can express the incidence matrix M as the sum of Boolean matrices MV + ME , such that each row of MV (resp. column of ME ) has at most κ blocks of consecutive ones. Thus, the matrix M can be compressed, since we only need to store the starting and ending indices of each block. Hence, the input hypergraph can be stored in O((m + n)κ) space, which can be much smaller than ∥H∥. This is a significant departure from all existing notions of (hyper)graph degeneracy. All previous degeneracy notions do not give an asymptotic reduction in the input storage. For example, hyperedge degeneracy can be used to bound the total number of (hyper)edges, so the raw storage of the input is (up to constant factors) the same as storing the degeneracy orientations. Queries via computational geometry. The compression provided by interval representations opens up a new dimension for data structures for hypergraph processing. Fundamentally, all primitives boil down to understanding whether certain collections of entries M [v, e] have value 1 (where v and e vary over choices depending on the primitive). That question can be answered by looking at a row of MV or a column of ME , each of which has a block structure. Building on that intuition, we can represent the relevant incidence information of vertices (and hyperedges) by a collection of O(κ) integers that indicate the starting and ending index of the various blocks. So this is an O(κ)-dimensional representation of the relevant information. By a careful formalization, we can convert all primitives to geometric questions in this O(κ)-dimensional space and solve them by using geometric range searching techniques. Assuming bidegeneracy is bounded, consider the EdgeSat query. We first discuss the approach for the general bound of Theorem 1.3 that works for queries of any size. The properties of the interval representations allow for a reduction of satisfying vertex formulas to problems on intersection patterns of specific intervals. Specifically, we determine if a hyperedge e satisfies formula ϕ by inspecting the intervals J (e) and I(v) (for v in the formula ϕ). Essentially, the question is about intersection patterns of constant size. We can represent each hyperedge e as a point in Rd (for constant d) based on the intervals of J (e). Any vertex formula ϕ can be converted into a collection of disjoint boxes in Rd (again based on the interval representation) such that e satisfies ϕ iff the corresponding point lies in one of these boxes. We can now set up classic orthogonal range searching data structures to solve the (weighted) counting, sampling, and listing versions of EdgeSat. The dual invariance of the bidegeneracy definition directly gives algorithms for VertexSat as well. In this construction, the dimension d of the points is linear in κ, leading to an exponential dependence in κ for the query time. This setup is needed for arbitrary queries (indeed, our lower bounds show that exponential dependencies in κ are unavoidable). When the query size t is bounded (for primitives like Adj), we can optimize our technique to reduce the dependence on κ to just polynomial (Theorem 1.2). Since the query only involves t vertices, a careful inspection shows that 7

we only need to discover t intervals (in V and E ) to certify that an edge e satisfies a formula. It turns out to be convenient to dualize our geometric viewpoint and convert to a problem of box stabbing. We represent hyperedges as a collection of boxes in Rd (for constant d), where d is independent of κ and only depends on t. The numbers of boxes in the collection depends only polynomially in κ. Formulas are now represented as vectors (thus the geometric picture is the dual of the previous approach). We now set up box stabbing data structures to solve the various versions of EdgeSat. The exponential dependence is only on t (which needs to be known in advance), since the dimension is independent of κ. The complications of VertexNeigh. For VertexNeigh we follow the above approach, but with significant complications because of the “second-order” nature of the query. For EdgeSat, whether an edge e satisfies a query φ involving vertices v1 , . . . , vt depends only on the column of e and the rows of v1 , . . . , vt in the incidence matrix MH . For VertexNeigh, instead, whether u is a neighbor of v is a function of all the columns of MH . Thus, for VertexNeigh, it is not obvious how to set up the geometric problem between the query vertex and other vertices. We bypass the obstacle by breaking down the neighborhood N (v) of the query vertex v into an “easy” subset N0 (v) and a “hard” subset N1 (v). Recall that, in the interval representation of H, every vertex holds a collection I(v) of at most κ intervals of hyperedges in the ordering E . Then, N0 (v) consists of those neighbors of v whose incidence with v is certified by an edge being in both I(v) and I(u). Therefore N0 (v) is easy in the sense above—for any vertex u ∈ N0 (v) the adjacency with v is certified by the rows of u and v alone. Exploiting this fact, we show that N0 (v) can be counted using an approach analogous to VertexSat queries, with the difference that now both vectors and boxes represent vertices. To deal with N1 (v), we apply a different approach. We show that the set of pairs of vertices {(u, v) | u ∈ N1 (v)} can be expressed as a collection of axis-parallel rectangles in R2 . The sides of these rectangles are constructed from the intervals in the interval representation of H. The construction also crucially uses an additional property of interval representations, niceness, that is given for free by our peeling algorithm.2 The problem of computing now |N1 (v)| becomes a 2-d stabbing problem, where the query is the vertical line (v, ·), and the answer is the size of the union of the y-sides of boxes that cross that line. Existing results for this kind of problem are too abstract and yield only vacuous bounds, thus we adapt them into an efficient algorithm. We then enrich the data structures in order to support listing and sampling.

1.4

Manuscript organization

Section 2 introduces hypergraph bidegeneracy, the interval representation of H, and an algorithm for computing it. Section 3 describes the algorithm that uses the interval representation of H to solve EdgeSat and VertexSat queries via a reduction to Orthogonal Range Searching, proving Theorem 1.3. Section 4 deals with the case of bounded-size queries, proving Theorem 1.2. Section 5 provides the algorithm for VertexNeigh, proving Theorem 1.4. Finally, Section 6 proves the lower bounds of Theorem 1.5. All omitted material can be found in the appendix.

2

Hypergraph bidegeneracy and interval representations

We set up some notation and give a detailed exposition of hypergraph bidegeneracy. We also explain the notion of subhypergraphs, which gives more context for bidegeneracy and the relation to other hypergraph degeneracies. 2

Not to be confused with the one of [17].

8

We will need to distinguish between the identifier of a hyperedge and the actual vertices it contains. We use e ∈ E to denote the identifier and use V (e) to denote the set of vertices that e represents. Similarly, we use E(v) to denote the set of (identifiers of) hyperedges containing v. This setup allows us to deal with multi-hypergraphs, which is critical for defining induced hypergraphs. When we say that two hyperedges are distinct, we mean that the identifiers are different. They could represent the same set. There are numerous subtleties in defining subhypergraphs. There is an entire hierarchy of definitions of induced subhypergraphs [50, 51]. Observe that different hyperedges may induce the same hyperedge on S, and definitions vary on whether these duplicates are kept. This leads to the definition of sub-hypergraph used in this work, which is as follows. Definition 2.1. Consider a hypergraph H = (V, E) with incidence matrix MH and consider V ′ ⊆ V and E ′ ⊆ E. Let M ′ be the submatrix of MH induced by V ′ and E ′ . The subhypergraph H ′ = (V ′ , E ′ ) of H is the hypergraph with incidence matrix M ′ . We come to a crucial point. One may think of the deduplication step (removing “copies” of a hyperedge) as a natural operation. However, the dual operation is to remove vertices that participate in the same hyperedges, which is not a standard operation. Any dual invariant definition needs to remove both “duplicated” vertices and hyperedges. Definition 2.2. Two distinct vertices u, v ∈ V are twins if E(u) = E(v), and two distinct hyperedges e, f are twins if V (e) = V (f ). A hypergraph is twin-free if it contains no twins. Now for the central definition of our paper. This definition is equivalent to Definition 1.1, but expressed in terms in subhypergraphs. Definition 2.3. A hypergraph H is (κv , κe )-bidegenerate if every twin-free subhypergraph of H has a vertex of degree at most κv or an edge of size at most κe . Equivalently, H is (κv , κe )-bidegenerate if every submatrix of MH with unique rows and columns contains a row (column) of Hamming weight at most κv (κe ). A hypergraph is κ-bidegenerate if it is (κ, κ)-bidegenerate. We note that having bounded bidegeneracy is a weaker property than most existing definitions, see Fig. 1. In Appendix A.1, we show that these existing notions are subsumed by bounded bidegeneracy.

2.1

Interval representations

We come to a key tool behind our algorithms: the interval representation of a hypergraph. This is a data structure that specifies orderings of V and E, analogous to the degeneracy ordering for graphs [41, 57], and uses them to encode the hypergraph’s incidence relation in a compact form. This compact form consists in a short sequence of intervals along those orderings, something that is absent from (and significantly more complex than) the standard degeneracy ordering over graphs. We now give the formal definition of interval representation, and then provide some intuition for it. A set X is a k-interval subset of {1, . . . , N } if X can be written as the disjoint union of k intervals X1 , . . . , Xk over [N ]. Clearly, every k-interval subset can be stored implicitly by using k pairs of integers. When there is no risk of ambiguity, we use X to denote both the sequence of intervals X1 , . . . , Xk and their union X1 ⊎ . . . ⊎ Xk . Definition 2.4 (Interval representation of a hypergraph). Let H = (V, E) be a hypergraph. A V , E , I, J ) with the following properties. First, (κv , κe )-interval representation of H is a tuple (V V = (v1 , . . . , vn ) is an ordering of V , and E = (e1 , . . . , em ) is an ordering of E. Second, I maps 9

every v ∈ V to a kv -interval subset I(v) = I1 (v) ⊎ . . . ⊎ Ikv (v) of E , with kv ≤ κv ; and J maps every e ∈ E to a ke -interval subset J (e) = J1 (e) ⊎ . . . ⊎ Jke (e) of V , with ke ≤ κe . Finally, I and J satisfy: 1. Soundness: letting J −1 (v) = {e ∈ E : v ∈ J (e)} and I −1 (e) = {v ∈ V : e ∈ I(v)}, E(v) = I(v) ⊎ J −1 (v), V (e) = J (e) ⊎ I

−1

(e),

∀v ∈ V ,

(1)

∀e ∈ E .

(2)

2. Niceness: ∀v ∈ V, ∀i ∈ [kv ],

e, f ∈ Ii (v) ⇒ J (e) = J (f ) ,

(3)

∀e ∈ E, ∀j ∈ [ke ],

u, v ∈ Jj (e) ⇒ I(u) = I(v) .

(4)

Let us give some intuition about Definition 2.4. Ignore for the moment the niceness property (it is a technical condition given for free by our preprocessing, and exploited by the algorithms). Soundness says that, if v is incident with e, then exactly one of two cases holds: either e ∈ I(v), or v ∈ J (e). Vice versa, if v is not incident with e, then neither e ∈ I(v) nor v ∈ J (e). Thus, under suitable permutations of V and E, every incidence between a vertex v and an edge e can be verified by looking at two short lists. For example, if H has rank at most k, which includes the case of graphs, then we can trivially set I(v) = ∅ for all v, and set J (e) to be the union of at most |V (e)| ≤ k intervals, one per vertex, regardless of V and E . Thus, hypergraphs of rank at most k admit a (0, k)-representation, and in particular graphs admit a (0, 2)-representation. Symmetrically, hypergraphs of degree at most k admit a (k, 0)-representation. In matrix language, Definition 2.4 says that the rows and columns of the incidence matrix M of H can be permuted so that M = MV + ME , where MV (ME ) is a Boolean matrix where every row (column) consists of at most κv (κe ) blocks of consecutive ones. However, clearly, storing the matrix would be too expensive. An interval representation, instead, takes space only O(|V | · κv + |E| · κe ), since each interval can be represented by its endpoints, which take one word of space each. See Fig. 2 for an example.

2.2

From bidegeneracy to interval representations

It is easy to see that a hypergraph is (κv , κe )-bidegenerate if and only if its incidence matrix can be reduced to the empty matrix by a sequence of deletions of rows of (Hamming) weight at most κv , and columns of (Hamming) weight at most κe (provided that identical rows and columns are merged whenever they appear). However, this characterization is not very useful. Here, we show that such a deletion process can be carried out efficiently while storing information about merges, so as to obtain a (κv , κe )-interval representation. Theorem 2.5. Every (κv , κe )-bidegenerate hypergraph H has a (κv , κe )-interval representation that, given H and one of κv and κe , can be computed deterministically in time O(∥H∥ ln1.5 ∥H∥). Finding an interval representation with optimal parameters is hard in general. Even deciding whether a hypergraph admits a (0, k)-interval representation is equivalent to testing whether its incidence matrix satisfies the k-consecutive-ones property, which is NP-complete for every k ≥ 2 [29]. The algorithm of Theorem 2.5 certifies the bidegeneracy of H: given κv , it finds the smallest κe such that H is (κv , κe )-bidegenerate. In this sense the bidegeneracy of H is efficiently computable. The rest of this section proves Theorem 2.5 by giving an algorithm that computes the interval representation. In particular, Section 2.2.1 gives a high-level description of the algorithm, Section 2.2.2 10

V = (v1 , v2 , . . . , v9 ) e1

v2 v1

e2

v3 e4

e5

v7 v8

v9 e6 v5 v6 e3

v4

E = (e1 , e2 , . . . , e6 )   v : [e4 , e4 ]   1     v : [e4 , e4 ]   e1 : [v1 , v2 ]  2     v3 : [e5 , e5 ]       e2 : [v3 , v4 ]      v : [e , e ]  4 5 5  e : [v , v ]  3 5 6 J I v5 : [e6 , e6 ]   e : ∅ 4     v6 : [e6 , e6 ]       e5 : ∅     v7 : [e4 , e6 ]   e :∅   6   v8 : [e4 , e6 ]     v9 : [e4 , e6 ]

e1 e2 e3 e4 e5 e6 v1 v2 v3 v4

1 1 0 0

0 0 1 1

0 0 0 0

1 1 0 0

0 0 1 1

0 0 0 0

v5 v6 v7 v8

0 0 0 0

0 0 0 0

1 1 0 0

0 0 1 1

0 0 1 1

1 1 1 1

v9 0

0

0

1

1

1

Figure 2: An example of a (1, 1)-bidegenerate hypergraph and a valid (1, 1)-interval representation V , E , I, J ). This representation is sound, as every vertex and hyperedge gets defined from the (V intervals I and J , for example E(v1 ) = I(v1 ) ⊎ J −1 (v1 ) = {e1 , e4 }, as e4 ∈ I(v1 ) and v1 ∈ J (e1 ) (hence e1 ∈ J −1 (v1 )). The representation is also nice, as the edges e4 , e5 , e6 have the same intervals in J and each of (v1 , v2 ), (v3 , v4 ) and (v5 , v6 ) have the same intervals in I. On the right the incidence matrix of the hypergraph, in red the entries corresponding to MV and in blue the entries corresponding to ME , matching the assignments of I and J . The red entries in every row and the blue entries in each column form a single block of 1’s. proves its correctness, and Section 2.2.3 describes a careful implementation that brings the algorithm in the time prescribed by Theorem 2.5. The main idea is akin to the algorithm for obtaining the degeneracy ordering in a graph, where we peel the lowest degree vertex at each time. In our case, we peel either a vertex of small degree or a hyperedge of small size. This is complicated by the fact that we need to efficiently detect twins on the fly and remove them. The interval representation arises from constructing two auxiliary forests that track the peeling process, and then computing certain intervals over the leaves of those forests. 2.2.1

The algorithm

We start by describing the algorithm in terms of a peeling process. Let H = (V, E), and recall that deleting v ∈ V yields the hypergraph whose incidence matrix is obtained from the one of H by removing the row of v (similarly, deleting e ∈ E amounts to removing from the matrix the column of e). Until H has no vertices and no edges, we repeat the following step. • If H contains twin vertices u, v, then delete u and v and add a new vertex xuv of type E(u) = E(v). If H contains twin edges e, f , then delete e and f and add a new edge xef of the type V (e) = V (f ). We refer to this operation as a merge. • If H is twin-free, then delete a vertex of degree at most κv if one exists, otherwise delete an edge of size at most κe . We refer to this operation as a deletion. Throughout the process we construct two data structures, the vertex forest TV and the edge forest TE . At the beginning, TV contains one isolated node Xv per vertex v ∈ V ; similarly, TE contains one isolated node Xe per edge of E. We then update the forests as follows, maintaining the invariant that every vertex (edge) of H created along the process, or originally in V (E), is associated to a unique node in TV (TE ). 11

• When we delete a vertex v, we store in Xv the pointers to all nodes Xe of TE such that e contains v. Denote this set of pointers by PTR(Xv ). Note that, by construction, |PTR(Xv )| ≤ κv . Similarly, when we delete an edge e, we store in Xe the set PTR(Xe ) of pointers to all nodes Xv of TV such that v is in e, and |PTR(Xe )| ≤ κe . • When we merge two vertices u, v, we create in TV a new node Xuv associated to the new vertex xuv , and set Xu and Xv as its children, thus merging their subtrees into a new tree rooted at Xuv . Similarly, when we merge edges e, f , we create in TE a new node Xef with Xe and Xf as children. At the end of the process we perform a postorder traversal of TV , and record: • The order in which the leaf nodes {Xv : v ∈ V } are visited. This gives the total order V = (v1 , . . . , vn ) over V . • For every node X in the forest, the interval J(X) formed in V by the leaves of the subtree rooted at X, encoded as the pair of indices j, j ′ such that J(X) = {vj , . . . , vj ′ }. Do the same for TE to obtain the total order E and the intervals I(·). For every node X in a forest, let r(X) be the root of the subtree it lies in. Finally, define: I(v) = {I(X) : X ∈ PTR(r(Xv ))} : ∀v ∈ V

(5)

J (e) = {J(X) : X ∈ PTR(r(Xe ))} : ∀e ∈ E

(6)

The pseudocode is given in Algorithm 1. Fig. 3 gives an example of the execution of the peeling process. Algorithm 1: IntervalRepresentation Input: A (κv , κe )-bidegenerate hypergraph H = (V, E) and κv or κe V , E , I, J ) of H Output: A (κv , κe )-interval representation (V 1 save V0 = V and E0 = E; 2 initialize edgeless forest TV with isolated nodes {Xv : v ∈ V }; 3 initialize edgeless forest TE with isolated nodes {Xe : e ∈ E}; 4 while H ̸= (∅, ∅) do 5 if H contains twin vertices u, v (or twin edges e, f ) then 6 update H by merging u, v into a new vertex uv (or e, f into a new edge ef ); 7 update TV (or TE ) by creating a node Xuv with Xu , Xv as children (or Xef with Xe , Xf as children); 8 else if H contains v of degree at most κv (or e of size at most κe ) then 9 store {Xf : f ∈ E(v)} as PTR(Xv ) (or {Xu : u ∈ V (e)} as PTR(Xe )); 10 update H by deleting v (or deleting e); 11 run a postorder traversal on TV (and TE ) to compute: 12 the total order V (and E ) given by the visit to the leaves of TV (and of TE ); 13 for each node X, its root r(X) in the forest; 14 for each node X, the interval J(X) ⊆ V (and I(X) ⊆ E ) given by its leaves; 15 let I(v) ← {I(X) : X ∈ PTR(r(Xv ))} for each v ∈ V0 ; 16 let J (e) ← {J(X) : X ∈ PTR(r(Xe ))} for each e ∈ E0 ; V , E , I, J ); 17 return (V

12

Step 1

Initial Hypergraph e1 v2 v1 e4

v3 e2 e5 v4

v7 v8

e1 v12 e4 v1 v2 v3 v4 v5 v6 v7 v8 v9

v9

v789

v34 e2 v 12

v789

v34

e5

v56

v1 v2 v3 v4 v5 v6 v7 v8 v9

TV

e6 v5 v6 e3

TV

e6 v56 e3 e1

e2

e3

e4

e5

e6

e1

e2

e3

TE

e4

v789

e5

v12

v34

v789

v56

v78

e4

v1 v2 v3 v4 v5 v6 v7 v8 v9 TV

e6 v56 e1

e2

e3

v789

v12

e5

v34

e4

e5

e6

e1

e2

e3

e4

e6

Step 5 v34

v56

v789

v78

v12

v34

v56

v78

v1 v2 v3 v4 v5 v6 v7 v8 v9

v1 v2 v3 v4 v5 v6 v7 v8 v9

TV

TV

e456

e456

e456

e45 e2

e5

TE

v789

e1

v78

TV

e6

Step 4 v12

v56

v1 v2 v3 v4 v5 v6 v7 v8 v9

TE

v789

e6

Step 3 v789

v34

e5

TE

Step 2 v12 e4

v78

e3

e4

e45 e5

e6

TE

e1

e2

e3

e4

e5

e6

TE

Figure 3: An example of the peeling procedure. Step 1: Twin vertices are combined. v1 and v2 get combined into v12 , v3 and v4 into v34 , v5 and v6 into v56 and v7 and v8 into v78 , which is combined with v9 to form v789 . The new nodes are added to the forest. Step 2: We peel the hyperedges e1 , e2 , e3 (the dashed arrows in the forest represent the sets PTR). Step 3: We peel the vertices v12 , v34 , v56 . Step 4: We combine the duplicated hyperedges e4 , e5 into e4 5, which combines with e6 into e456 , both are added to TE . Step 5: We peel the last vertex, v789 .

13

2.2.2

Correctness

Lemma 2.6. Algorithm 1 returns a valid (κv , κe )-interval representation of H. Proof. We check the output of Algorithm 1 against Definition 2.4. First, observe that the algorithm always terminates, since each iteration of the loop of line 4 decreases the total number of vertices and edges by exactly one, either by deleting an element or by merging two twins into one. Indeed, at every iteration we are left with a subhypergraph of H, and either that subhypergraph contains twins, or it contains a vertex of degree at most κv or an edge of size at most κe . Thus, the construction of both TV and TE takes place as described above. Clearly, V and E are total orderings over respectively V0 and E0 . Now, observe that |PTR(X)| ≤ κv for every node X in TV and |PTR(X)| ≤ κe for every node X in TE . This holds since PTR(X) is created inside the block of line 8, which implies |E(v)| ≤ κv (or |V (e)| ≤ κe ). Moreover, by construction I(X) and J(X) are indeed intervals. We conclude that I(v) is a kv -interval subset for all v ∈ V0 , and J (e) is a ke -interval subset for all e ∈ E0 , where kv ≤ κv and ke ≤ κe . Soundness. For every v ∈ V0 denote by v ∗ the vertex such that r(Xv ) = Xv∗ . Note that v ∗ can be v itself, or a new vertex created by the algorithm via a merge operation. Moreover, let t(v ∗ ) be the time (in the algorithm’s execution) at which v ∗ is deleted; this is well defined, since Xv∗ is a root if and only if v ∗ is deleted without being further merged. For every e ∈ E0 define e∗ and t(e∗ ) in the same way. Now, for every incident v ∈ V0 and e ∈ E0 , either t(v ∗ ) < t(e∗ ) or t(v ∗ ) > t(e∗ ). Suppose t(v ∗ ) < t(e∗ ) and let ℓ(X) be the subtree of TE rooted at X. The crucial observation is: ] {e ∈ E0 (v) : t(e∗ ) > t(v ∗ )} = {e : Xe ∈ ℓ(Xf )} . (7) f ∈E(v ∗ )

To see why, first note that {e : Xe ∈ ℓ(Xf )} is precisely the set of all edges that led to f through some sequence of merge operations; this also implies that the right-hand set is a disjoint union. Thus, if e is in the left-hand set, then take Xf to be the highest ancestor of Xe that is created before t(v ∗ ); this implies v ∗ is incident with f at time t(v ∗ ), that is, f ∈ E(v ∗ ), and therefore e is in the right-hand set. If instead e is in the right-hand set, then observe that if e ∈ / E0 (v) then either Xe ∈ / ℓ(Xf ) or f ∈ / E(v ∗ ), and the same is implied by t(e∗ ) < t(v ∗ ). Finally, observe that the intervals {e : Xe ∈ ℓ(Xf )} for f ∈ E(v ∗ ) are precisely the intervals I(X) computed by the algorithm at line 15 for Xv∗ = r(Xv ). Thus, for every v ∈ V0 , if I(v) = I1 (v), . . . , Ikv (v), then kv [

Ii (v) = {e ∈ E0 (v) : t(e∗ ) > t(v ∗ )} .

(8)

i=1

The case t(v ∗ ) > t(e∗ ) is symmetric, and it yields for every e ∈ E0 : ke [

Jj (e) = {v ∈ V0 (e) : t(v ∗ ) > t(e∗ )} .

(9)

j=1

This proves soundness. Niceness. Suppose e, f ∈ Ii (v) for some v ∈ V and some i ∈ [kv ]. By the construction of the algorithm, this implies Xe , Xf are in the same tree in the forest TE . This implies r(Xe ) = r(Xf ), and therefore the algorithm sets J (e) = J (f ), proving niceness. The case of vertices is symmetric.

14

2.2.3

Running time

Lemma 2.7. Algorithm 1 can be run in time O(∥H∥ ln1.5 ∥H∥). Proof. First, we describe the data structures employed. Let H0 = (V0 , E0 ) be the input hypergraph. We will make sure that, along the algorithm, all vertices are elements of {1, . . . , 2|V0 |} and all edges are elements of {1, . . . , 2|E0 |}. For our algorithm to work, we need to efficiently detect when two distinct vertices u, v have identical type, E(u) = E(v), and the same for edges. This boils down to maintaining a distinguished id η(X) for every set X in a set family under a sequence of updates of the kind “insert element x in set i”. As shown in [59], this can be done in update time O(log1.5 s), where s is the sum of the sets’ sizes. In our case, s = ∥H∥; thus, upon (say) deleting a vertex from a hyperedge V (e), we can update η(V (e)) in time O(log1.5 ∥H∥). We now describe the data structures for vertices; the same holds for edges. As there is no risk of ambiguity, the data structures have the same name for both. Every set, such as E(v), is assumed to be stored in a structure (e.g., a balanced search tree) that supports insertion, deletion, and update in logarithmic time, and querying for the size in constant time. We maintain: • An array TYPE, indexed by {1, . . . , 2|V0 |}, such that TYPE[v] holds E(v) = {e ∈ E : v ∈ V (e)}. If v is not currently a vertex of H, then TYPE[v] = nil. • The forest TV using pointers: each node X = Xv stores v as well as the pointers to its children, if any. The same for the forest TE . • An array NODE, indexed by {1, . . . , 2|V0 |}, such that NODE[v] points to Xv if Xv exists in TV and is nil otherwise. • An array, HASH, such that HASH[v] = η(E(v)). • A dictionary, HASH−1 , such that HASH−1 (h) holds V −1 (h) := {v : η(E(v)) = h}. • A set structure, TWINS, that holds the set {h : |V −1 (h)| ≥ 2}. Finally, we maintain two min-heaps, DegHeap and SizeHeap, that track respectively the smallest degree and the smallest edge size in the current hypergraph. Setting up the data structures (lines 1 to 3). Constructing the array TYPE and the dictionaries TYPE[v] for all v ∈ V0 takes total time O(∥H0 ∥ ln∥H0 ∥). Constructing TV and TE takes time O(|V0 | + |E0 |) = O(∥H0 ∥), and the same for NODE. To construct the array HASH we compute η(E(v)) for every v ∈ V0 , which by our assumptions takes total time O(∥H0 ∥ ln1.5 (∥H0 ∥)). To construct HASH−1 we sort and aggregate HASH by value, which takes total time O(|V0 | ln |V0 |). Note that this also yields TWINS for free. Constructing DegHeap takes again total time O(∥H0 ∥ ln∥H0 ∥). The same applies to the data structures for edges. The total time of the setup is therefore O(∥H0 ∥ ln1.5 ∥H0 ∥). Performing a merge (block of line 5). With the data structures set up, we proceed as follows. First, observe that by checking whether TWINS is empty, and by querying DegHeap and SizeHeap, we can perform in time O(1) the tests of lines 5 and 8. Suppose then we enter the block of line 5 as TWINS contains a hash value h; we look h up in HASH−1 . Suppose we get a set of vertices V −1 (h); the case E −1 (h) is symmetric. Pick any two vertices u, v ∈ V −1 (h). Let z be the smallest integer not yet assigned to any vertex along the process. (Note that this is just |V0 | plus the number of vertex merges so far, including the current one, so z can be kept as a global counter). This ensures z ∈ {1, . . . , 2|V0 |}, since the algorithm performs at most |V0 | merges. We update all our data structures by replacing u, v with z, as follows. First, for every e ∈ E(v) = E(u): 15

• We update TYPE[e] by deleting u and v and inserting z. • We save h = HASH[e], and we update HASH[e] to its new value h′ = η(TYPE[e]). • Using h and h′ we update HASH−1 , by removing e from the dictionary HASH−1 (h) and adding it to HASH−1 (h′ ). This entails deleting HASH−1 (h) if empty and/or creating HASH−1 (h′ ) if not already existing. • We update TWINS by inserting h′ if |HASH−1 (h′ )| ≥ 2, and removing h if |HASH−1 (h)| ≤ 1. • We update SizeHeap by decrementing the size of e. We also update DegHeap by replacing u, v with z. Note that each one of these updates takes time at most O(ln1.5 ∥H0 ∥). Thus, the total time spent so far for a merge is O(deg(z) ln1.5 ∥H0 ∥), where deg(z) = |E(z)| is the current degree of z. Finally, from V we retrieve the pointers to Xu and Xv , and we create a new node Xz in TV that stores z and the pointers to Xu and Xv . We set NODE[z] = Xz and TYPE[z] = TYPE[u], and then set TYPE[u] = TYPE[v] = nil. This takes just time O(1). We also set HASH[z] = HASH[u], replace u and v with z in HASH−1 (HASH[z]) and update TWINS accordingly. This can be done in O(ln∥H0 ∥) time. We now show that the total time spent over merging vertices is in O(∥H0 ∥ ln1.5 ∥H0 ∥); the same holds for edges. To this end, recall that by construction each merge corresponds to an internal node Xz of TV ; as shown above, the time spent for that merge is O(deg(z) ln1.5 ∥H0 ∥), where deg(z) is the degree of z in H at merge time. Now, for each such Xz choose a distinct leaf node Xv in TV that is a descendant of Xz ; this is possible as TV is by construction a binary tree. Note that deg(z) ≤ deg0 (v), where deg0 (v) is the degree of v in H0 . The total cost of vertex merges is thus bounded by: X X
O deg(z) ln1.5 ∥H∥ ≤ O(deg0 (v) ln1.5 ∥H0 ∥) = O(∥H0 ∥ ln1.5 ∥H0 ∥) . (10) Xz ∈TV \L(TV )

Xv ∈L(TV )

Performing a deletion (block of line 8). Suppose now we enter the block of line 8 having chosen v with deg(v) ≤ κv (the case of e is symmetric). We read E(v) from TYPE[v], and for every f ∈ E(v) we add NODE[f ] to a list. Finally, we write the pointer to this list in the entry PTR[v] of an array PTR indexed again by {1, . . . , 2|V0 |}. We then update H using the same operations that delete v during a merge. First, we read E(v) from TYPE[v], and for every e ∈ E(v): • We update TYPE[e] by deleting v. • We update SizeHeap by decreasing the size of e by one. • We save h = HASH[e], and we then update HASH[e] to its new value h′ = η(TYPE[e]). • We remove e from HASH−1 (h) and insert it into HASH−1 (h′ ). As above, we might need to delete or create the corresponding entries. • We insert h′ in TWINS if |HASH−1 (h′ )| ≥ 2. (Note that certainly h ∈ / TWINS, since H is twin-free if we are doing a deletion, hence no further checks on TWINS are needed). Every one of these updates takes time at most O(ln1.5 ∥H∥), for a total of O(deg(v) ln1.5 ∥H∥). Finally, we remove v from HASH−1 (HASH[v]). We then set TYPE[v] = nil, and remove v from DegHeap, which cost O(ln∥H∥). To bound the total time spent on vertex deletions, we proceed like for merges. If a vertex z is deleted, then Xz is the root of a tree in TV , and therefore it can be mapped to a distinguished leaf 16

Xv with v ∈ V0 . Moreover, deg(z) ≤ deg0 (v). Adapting Equation (10) yields a total time bound of O(∥H∥ ln1.5 ∥H∥). Wrapping up (lines 11 to 17). Performing the postorder traversal of TV and TE and writing V and E takes time O(∥H0 ∥), as this is the total size of the forests. Note that r(X) and J(X), with J(X) represented by its endpoints, can be computed for free during the traversal. Line 15 requires, for each v ∈ V0 , to read Xz = r(v), read the nodes in PTR[z], and for each such node X add I(X) to the list I(v). This takes time O(|PTR[r(v)]|) for each v. By the same charging argument used above, we conclude that line 15 takes time O(∥H∥). The same holds for line 16. Summarizing, Algorithm 1 can be run in time O(∥H∥ ln1.5 (∥H∥)), as claimed.

3

Answering EdgeSat queries

In this section, we prove the more general Theorem 1.3, showing that we can efficiently preprocess and answer EdgeSat queries on hypergraphs of small bidegeneracy. With the techniques and setup in place, it is easier to explain how to solve EdgeSat, for fixed length queries (Theorem 1.2). This is done in Section 4. The results on VertexSat follow by taking the dual of H. We actually solve the simpler EdgePartialMatch primitive; it is rather straightforward to transform every EdgeSat query into a collection of disjoint EdgePartialMatch queries. Recall that an EdgePartialMatch query takes in a “positive” vertex set P ⊆ V and a “negative” vertex set N ⊆ V . A hyperedge e satisfies this query if P ⊆ V (e) and N ∩ V (e) = ∅. We will actually solve a stronger weighted version of this query. Let us assume that there is a weight function w : E → N. In the counting version of this query, we need to output the total weight of satisfying hyperedges. In the sampling version, we need to sample a satisfying hyperedge with probability proportional to its weight. And, in the listing version, we need to enumerate all satisfying hyperedges with small delay. The main result we prove is: Theorem 3.1. There exists an algorithm for EdgePartialMatch with the following guarantees. Given in input a (κv , κe )-bidegenerate hypergraph H = (V, E) and an edge weighting w : E → N,
• First, the algorithm constructs a data structure in time O 2O(κe ) ∥H∥ log2κe +1 ∥H∥ . O(t)

• Afterwards, the algorithm can answer every query in time O(κv 2O(κe ) κe log2κe +1 ∥H∥), where t = |P | + |N | is the query size. This holds for counting, sampling, and O(1)-delay listing. Section 3.1 shows how EdgePartialMatch queries can be expressed as a set of constraints that involve the interval representation of H. Section 3.2 exploits this connection to describe an algorithm that performs a reduction to orthogonal range searching. Section 3.3 wraps up the proof of Theorem 3.1. Finally, Section 3.4 shows how this yields the results on Sat of Theorem 1.3.

3.1

Converting to a question on intervals

V , E , I, J ) of H in near-linear Theorem 2.5 tells us that we can compute a (κv , κe )-representation (V time. Our first step is to convert the question of which edges satisfy an EdgePartialMatch query to a question on the interval representation. To lighten the notation, we assume that the vertices and the edges of H are relabeled so as to match their rank in V and E . Thus, V = (v1 , . . . , vn ) = (1, . . . , n) and E = (e1 , . . . , em ) = (1, . . . , m). Such a relabeling can be obviously computed in linear time. We introduce some notation about the intervals I and J . Recall from Definition 2.4 that every J (e) is a set of at most κe intervals J1 (e), . . . , Jke (e) in V . For convenience, we add dummy 17

intervals J0 (e) = (−∞, 0] and Jke +1 (e) = [n + 1, ∞) that contain no vertices in V . For every subinterval J ⊆ V , denote its endpoints by start(J) and end(J), so that J = [start(J), . . . , end(J)]. Without loss of generality, we assume the intervals of J (e) to be indexed in increasing order, so that end(Ji (e)) < start(Ji+1 (e)) for each i ∈ [ke − 1]. For each v ∈ V , I(v) is a collection of kv ≤ κv intervals in E . Let I ∪ (v) be the union of these intervals. For any two subsets X, Y ⊆ V , define the union of intervals I ∪ (X, Y ) as follows. ! ! [ \ ∪ ∪ ∪ I (X, Y ) := I (v) \ I (u) (11) v∈X

u∈Y

The central claim for the reduction is the following: Claim 3.2. A hyperedge e ∈ E is a match for EdgePartialMatch(P, N ) if and only if there exists a subset S ⊆ P (possibly empty) such that the following claims hold: • e ∈ I ∪ (P \ S, N ). • There is a mapping σ : S → [ke ] such that, for every s ∈ S, s ∈ [start(Jσ(s) (e)), end(Jσ(s) (e))] • There is a mapping τ : N → {0}∪[ke ] such that, for every t ∈ N , t ∈ (end(Jτ (t) (e)), start(Jτ (t)+1 (e))) Moreover, if e is a match, then the choice of S, σ, τ is unique. S e Proof. By Definition 2.4, V (e) = kj=1 Jj (e) ⊎ I −1 (e). Take S to be: S=P∩

ke [

(12)

Jj (e) .

j=1 ∪ Now, suppose e is a match. Then P \ S ⊆ I −1 (e)and N ∩ I −1 (e)  =S∅. Hence, e
∈ I (v) for all T ∪ ∪ ∪ v ∈ P \ S, and v ∈ / I −1 (e) for all v ∈ N . Hence, e ∈ v∈P \S I (v) \ u∈N I (u) = I (P \ S, N ). Each s ∈ S lies in some Jj (e). By Definition 2.4, the intervals Jj (e) are pairwise disjoint, thus j is unique; let then σ(s) = j. Each t ∈ N , instead, does not lie in any Jj (e). This means that t lies in the “spaces” between these intervals. Formally, there exists a unique j such that t lies strictly between end(Jj (e)) and start(Jj+1 (e)); let then τ (t) = j. That completes the proof that, if e is a match, then the claims of the statement hold. Conversely, suppose the three conditions hold. By the first condition, we have P \ S ⊆ I −1 (e) and N ∩ I −1 (e) = ∅. By the second, every s ∈ S belongs to some Jj (e), while the third ensures that no t ∈ N belongs to any Jj (e). The soundness property of the interval representation lets us conclude that P ⊆ V (e) and N ∩ V (e) = ∅, so e is a match. Finally, the uniqueness of S follows from soundness, while the uniqueness of σ and τ follows from the disjointness and ordering of the intervals.

Thus, the problem of determining whether e is a match for EdgePartialMatch(P, N ) is equivalent to determining the conditions of Clm. 3.2.

3.2

The algorithm

We now prove that the interval problem defined by Clm. 3.2 can be solved by a reduction to V , E , I, J ) of H and the edge Orthogonal Range Searching. Given the (κv , κe )-representation (V weighting w, the algorithm embeds the edges e1 , . . . , em into a (2κe + 2)-dimensional space based on 18

the interval representation. The preprocessing step constructs a data structure to answer weighted orthogonal range queries on those points. To answer a given query (P, N ), the algorithm computes a certain set of boxes in the same (2κe + 2)-dimensional space and performs an orthogonal range search query for each one of them. It aggregates all answers, either by summing them (in the counting version) or concatenating them (in the reporting version) or by sampling from them (in the sampling version). 3.2.1

Preprocessing

In §B, we recall standard results on Orthogonal Range Searching. While there are many such results, we could not find a single one that supports counting, sampling, and listing under weightings; so we provide our own version, Theorem B.1, together with a complete proof. Basically, it says one can preprocess a weighted set of n points in Rd in 2O(d) n logd−1 n time so that, given an axis-aligned box as query, counting/sampling/listing can be done in 2O(d) logd−1 n time (for listing, this time is paid only once, and afterwards one can have delay O(1)). We first describe how to convert each hyperedge e into a vector in R2κe +2 . Consider the at most κe intervals J1 (e), J2 (e), . . . , Jke (e). The vector associated to e is:
(13) ⃗e e := e, start(J1 (e)), end(J1 (e)), . . . , start(Jke (e)), end(Jke (e)), n + 1, 0, . . . , 0 . | {z } 2(κe −ke )

The extra n + 1 is just a dummy padding to make the procedure simpler. Technically, we could remove it (and reduce the dimension), at the cost of extra handling of a corner case. Using as input the set of vectors {⃗⃗e e : e ∈ E }, we construct an orthogonal range query data structure. The pseudocode is given in Algorithm 2. V , E , I, J , w) Algorithm 2: EdgePartialMatch-Preprocess(V 1 compute the vector ⃗ e e for every e ∈ E ;

⃗e e : e ∈ E } with weighting w; 2 run ORQ-Preprocess on the set {⃗

3.2.2

Converting queries to boxes

Each query (P, N ) is converted to a collection of axis-parallel boxes, based on the conditions in Clm. 3.2. We use t = |P | + |N |. Fix a subset S ⊆ P . In what follows, we will describe constructions of various intervals for each coordinate that will be used to construct these axis-parallel boxes. The overall collection of boxes is obtained by varying S and these intervals of all the coordinates. The first coordinate. Recall the definition of I ∪ (P \ S, N ) in Equation (11). We state an easy claim. Claim 3.3. I ∪ (P \ S, N ) is a disjoint union I1 (S) ⊎ . . . ⊎ Iz (S) of z ≤ κv t + 1 intervals of E . T Proof. Note that, as |I(v)| ≤ κv for all v ∈ V , then v∈P \S I ∪ (v) is a disjoint union of at most |P \ S|κv ≤ |P |κv intervals. Hence, I ∪ (P \ S, N ) is the disjoint union of at most 1 + |P |κv + |N |κv = 1 + κv t intervals. Let I(P \ S, N ) = I1 (S), . . . , Iz (S). Each box constructed from the query (P, N ) will have, on its first coordinate, one of the intervals in I(P \ S, N ). 19

The remaining coordinates. Recalling Clm. 3.2, consider functions σ : S → [κe ] and τ : N → {0} ∪ [κe ]. We use a procedure, Endpoints, to compute a sequence of values αj , βj , for 2 ≤ j ≤ 2κe + 2. In the procedure, if a set is undefined, the operation involving the max or min is a no op. Algorithm 3: Endpoints(σ, τ ) 1 foreach 2 ≤ j ≤ 2κe + 2 do 2 initialize αj = −∞ and βj = ∞ 3 set α2 = max{τ −1 (0)} + 1/2; 4 foreach 1 ≤ i ≤ κe do 5 set α2i+1 = max{σ −1 (i)} and β2i = min{σ −1 (i)}; 6 set α2i+2 = max{τ −1 (i)} + 1/2 and β2i+1 = min{τ −1 (i)} − 1/2

We now state the claim that explicitly converts the matching condition into a geometric condition on boxes. Claim 3.4. The hyperedge e is a match for EdgePartialMatch(P, N ) if and only if the following hold. There exist a set S ⊆ P , an interval I ∈ I(P \S, N ), and functions σ :QS → [κe ] and τ : N → {0}∪[κe ] e +2 such that, with αj , βj returned by Endpoints(σ, τ ), we have ⃗e e ∈ I × 2κ j=2 [αj , βj ]. Moreover, if e is a match, then the choice of S, I, σ, τ is unique. Proof. Suppose e is a match. By Clm. 3.2, there exists S, σ, τ such that e ∈ I ∪ (P \ S, N ). (The range of σ, τ are technically [ke ], a subset of [κe ].) Also, for every s ∈ S, s ∈ [start(Jσ(s) (e)), end(Jσ(s) (e))], and for every t ∈ N , t ∈ (end(Jτ (t) (e)), start(Jτ (t)+1 (e))). Let us argue that ⃗e e is in the desired box, coordinate by coordinate. First coordinate: Note that e ∈ I ∈ I ∪ (P \ S, N ). The first coordinate of ⃗e e is just e, so that satisfies the claim. Coordinate j = 2i, 1 ≤ i ≤ ke . The coordinate of ⃗e e is start(Ji (e)). For each s ∈ S such that σ(s) = i, s ≥ start(Ji (e)). Hence, β2i = min{σ −1 (i)} ≥ start(Ji (e)). For each t ∈ N such that τ (t) = i − 1, t < start(Ji (e)) (this also holds for i = 1, in which case τ (t) = 0). Hence, max{τ −1 (i − 1)} < start(Ji (e)). Since, these are all integers, we can add 1/2 to left to get α2i < start(Ji (e)). In summary, the jth coordinate of ⃗e e lies in [αj , βj ]. Coordinate j = 2i + 1, 1 ≤ i ≤ ke . The coordinate of ⃗e e is end(Ji (e)). For each s ∈ S such that σ(s) = i, s ≤ end(Ji (e)). Hence, α2i+1 = max{σ −1 (i)} ≤ end(Ji (e)). For each t ∈ N such that τ (t) = i, t > end(Ji (e)). Hence, β2i+1 = min{τ −1 (i)} − 1/2 > end(Ji (e)) (using the integrality of the quantities). So, like the previous case, the jth coordinate of ⃗e e lies in [αj , βj ]. Coordinate j ≥ 2i + 1, i > ke . Since the values of σ, τ are at most ke , the values of αj , βj maintain their default values of −∞, ∞ in Endpoints(σ, τ ). Coordinate j = 2ke + 2. The coordinate of ⃗e e is n + 1. Since σ ∈ [ke ], we have βj = ∞. Moreover, αj ≤ n + 1/2, since N ⊆ [n]. So, the jth coordinate of ⃗e e lies in [αj , βj ]. Overall, we conclude that ⃗e e is in the desired box. Conversely, suppose ⃗e e is in the desired box. The first coordinate implies that we have e ∈ I ∪ (P \ S, N ). For every s ∈ S, the constraints on the corresponding coordinates imply that s ∈ Jσ(s) (e). The case for t ∈ N is analogous. Thus, all the conditions of Clm. 3.2 hold, and e is a match. If e is a match, the uniqueness holds by the fact that the intervals I ∈ I(P \ S, N ) are disjoint, and the uniqueness of S, σ, τ from Clm. 3.2. In Algorithm 4, we give the pseudocode for converting a query into boxes and getting the answer, and in Fig. 4 we show an example of the construction. 20

Algorithm 4: EdgePartialMatch(P, N ) 1 initialize B ∗ = ∅; 2 foreach subset S ⊆ P do

construct the family of intervals I(P \ S, N ); foreach function σ : S → [κe ] do 5 foreach function τ : N → {0} ∪ [κe ] do 6 run Endpoints(σ, τ ) to get αj , βj values; 7 foreach interval I ∈ I(P \ S, N ) do Q e +2 ∗ 8 add the box I × 2κ j=2 [αj , βj ] to B 9 for counting, P 10 return B ∗ ∈B⋆ ORQ-Count(B ∗ ); 11 for sampling, 12 pick B ∗ ∈ B ⋆ with probability proportional to ORQ-Count(B ∗ ); 13 return ORQ-Sample(B ∗ ); 14 for reporting, 15 warm up ORQ-Report(B ∗ ) on every B ∗ ∈ B ⋆ ; 16 run the rest of ORQ-Report(B ∗ ) on every B ∗ ∈ B ⋆ ; 3 4

3.3

Proof of Theorem 3.1

We wrap up the proof. Given the input hypergraph H, we first compute the interval representation using Theorem 2.5. We then apply the preprocessing step of Algorithm 2. Each query is processed by Algorithm 4. The correctness of the output holds by Clm. 3.4 that correctly maps the query to a collection of boxes, and by Theorem B.1 on the correctness of the range searching procedures. We now give the running time bounds. To construct the set {⃗⃗e : e ∈ E}, we retrieve the family of intervals J (e) = (J1 (e), . . . , Jke (e)) from J , and we write out ⃗e e . Recalling that each interval J is stored precisely as the pair start(J), end(J), the procedure takes time O(|E| · κe ). Finally, by Theorem B.1, constructing the data structure for weighted Orthogonal Range Search takes time O(2O(κe ) ∥H∥ · log2κe +1 ∥H∥), which dominates O(|E| · κe ) and gives the bound. We now analyze the query time. Each query to the range searching data structure takes O(2O(κe ) log2κe +1 ∥H∥) time. There are 2|P | possible subsets S. The family of intervals I(P \ S, N ) O(t) can be computed in O(κv t log |E|) time. There are κe possible functions σ and τ . Each call to Endpoints takes O(κe + t) time (by computing the preimages of σ and τ in a single pass). For fixed S, σ and τ , there are at most O(κv t) intervals. Building a single box takes O(κe ) time. The total O(t) O(t) query time is therefore O(2|P | κv κe 2O(κe ) t log2κe +1 ∥H∥) = O(2O(κe ) κe κv log2κe +1 ∥H∥).

3.4

Sat queries

We can answer Sat queries by converting them into a collection of PartialMatch queries. The following theorem gives time bounds for EdgeSat; as usual, the VertexSat version has κe and κv switched. Theorem 3.5. There is an algorithm for EdgeSat with the following guarantees. Given κv , κe and an edge-weighted (κv , κe )-bidegenerate hypergraph H, • First, the algorithm constructs a data structure in time O(2O(κe ) ∥H∥ log2κe +1 ∥H∥). • Subsequently, any counting, sampling, or listing EdgeSat query can be answered in time O(t) κv 2O(κe ) κe log2κe +1 ∥H∥, where t is the query size. 21

e1

v2 v1

e2

v3 e4

e5

v7 v8

v9 e6 v5 v6 e3

Query: P = {v3 }, N = {v8 } Output: {e2 }

v4

  v : [e4 , e4 ]   1    v 2 : [e4 , e4 ]     v3 : [e5 , e5 ]       v4 : [e5 , e5 ]  I v5 : [e6 , e6 ]    v6 : [e6 , e6 ]      v7 : [e4 , e6 ]      v8 : [e4 , e6 ]     v9 : [e4 , e6 ]   e1 : [v1 , v2 ]       e2 : [v3 , v4 ]    e : [v , v ] 3 5 6 J  e4 : ∅      e5 : ∅    e :∅

10 [e1 , e3 ] × (−∞, 3] × [3, 7.5] × [8.5, ∞)

8

(e3 , 5, 6, 10)

6

(e2 , 3, 4, 10) 4 (e1 , 1, 2, 10)

2

0

2

4

(e4 , 10, 0, 0) (e5 , 10, 0, 0) (e6 , 10, 0, 0) 6

8

10

6

Figure 4: An example of the construction from §3. Given the same hypergraph as in Fig. 2, we preprocess their corresponding four-dimensional points, for which we show their second and third dimension in the plot on the right. We then compute the query P = {v3 } and N = {v8 } by reducing it to an instance of Orthogonal Range Searching. For S = {v3 } we get I ∪ = [e1 , e3 ] (S = ∅ leads to an empty interval). For σ : v3 → 1 and τ : v8 → 1 (τ : v8 → 0 leads to a non-valid box) we get the endpoints representing the box in purple. We can check that only e2 is contained in that box and it is the correct output. Proof. First, we run the preprocessing phase of EdgePartialMatch. By Theorem 3.1, this takes time O(2O(κe ) ∥H∥ log2κe +1 ∥H∥). Consider now a query φ. We begin φ in orthogonal DNF form, φ = φ1 ⊕ . . . ⊕ φN . Vby rewriting  V  Every subformula φh is in the form ̸ j. v∈Ph xv ∧ v∈Nh ¬xv , and φi (H) ∩ φj (H) = ∅ for i = This construction can be done in 2O(t) time where t is the size of φ. The set φi (H) is exactly EdgePartialMatch(Pi , Ni ). We can thus answer the different flavors (counting, sampling, listing) of EdgeSat for each φi . Since the matches for all φi are disjoint, we can combine the answers to get counting/sampling/listing for the original query φ. Answering each query EdgePartialMatch(Pi , Ni ) O(t) takes time κv 2O(κe ) κe log2κe +1 ∥H∥, by Theorem 3.1. As there are at most 2O(t) such queries, that is also a bound on the overall running time for an EdgeSat query.

4

EdgePartialMatch and EdgeSat with fixed query size

When the query length is known in advance, we can give a faster algorithm for EdgePartialMatch. For every t ≥ 2, the algorithm answers queries (P, N ) with |P | + |N | = t (note t = 1 is trivial). Theorem 4.1. For every t ≥ 2 there is an algorithm with the following guarantees. Given a (κv , κe )-interval representation of a hypergraph H = (V, E) and an edge weighting of H, • First, the algorithm constructs a data structure in time O(∥H∥ κt−1 logt+2 ∥H∥). e • Afterwards, any counting/listing/sampling EdgePartialMatch query (P, N ) with |P | + |N | = t can be answered in time O(κv logt+2 ∥H∥).

22

For positive queries (N = ∅), both exponents are t instead of t + 2. Moreover, for the counting version, both exponents can be (further) decreased by 1. The algorithm is different than the one behind Theorem 1.3 and Theorem 3.1, and relies on box stabbing rather than orthogonal range search. As a first consequence of Theorem 4.1, we obtain a faster algorithm for EdgeSat. The proof follows immediately from the preprocessing guarantees of Theorem 2.5 and the reduction of EdgeSat to EdgePartialMatch of Section 3.4. Corollary 4.2. For every t ≥ 2 there is an algorithm with the following guarantees. Given κv ≥ 1 and an edge-weighted (κv , κe )-bidegenerate hypergraph H,
• First, the algorithm constructs a data structure in time O ∥H∥κt−1 logt+2 ∥H∥ . e • Afterwards, any counting/listing/sampling EdgeSat query on t variables can be answered in
time O κv logt+2 ∥H∥ . A second consequence of Theorem 4.1 is faster algorithms for the counting version of some primitives of interest, see Table 1. Note that Superset(S) is EdgePartialMatch(S, ∅), hence the faster bounds apply. Moreover, for SubH(S) we get the same bounds of Superset(S), and for Venn(e, f, g) the same bounds of Superset(S) for |S| = 3; this is because we can solve the counting version of EdgePartialMatch(P, N ) by inclusion-exclusion after solving queries EdgePartialMatch(S, ∅), which is Superset(S), for each S ⊆ P ∪ N . Primitive

Preprocessing time

Adj(u, v)

∥H∥ · log1.5 ∥H∥ + κe log∥H∥

Int(e, f ), Union(e, f ), Diff(e, f )

∥H∥ · log1.5 ∥H∥ + κv log∥H∥

Superset(S), SubH(S) for |S| = t ≥ 2

∥H∥ · log

Venn(e, f, g)

∥H∥ · κv log∥H∥

1.5

Query time

κv log∥H∥

∥H∥ + κt−1 logt−1 ∥H∥ e
2

κe log∥H∥

κv logt−1 ∥H∥ κe log2 ∥H∥

Table 1: Guarantees for the counting (and thus decision) version of some primitives of interest. For Superset and SubH, the size of the query |S| must be known before preprocessing.

4.1

The algorithm

The basic idea is as follows. Let (P, N ) be the query, and for every e ∈ E define Se = P ∩ J ∪ (e). Note that, if e matches the query, then: Se = {v ∈ P : v ∈ J ∪ (e)}

(14)

∪

(15)

P \ Se = {v ∈ P : e ∈ I (v)}

In words, Se contains the vertices of P whose incidence with e is certified by the intervals of e, while P \ Se contains the vertices of P whose incidence with e is certified by their own intervals. As a first step, we distinguish edges into “easy” and “hard”, according to Se . The easy edges: Se ⊊ P . Suppose e is such that Se ⊊ P . Then, e ∈ I for some I ∈ I(v) for some vertex v ∈ P \ Se . Intuitively, then, one can find all such edges by looking at each I, and for every e ∈ I checking if e is indeed a match. Checking all such edges explicitly is clearly infeasible, as they 23

are too many. However, by the niceness property of Definition 2.4, we need only to check one edge ê per each interval I: indeed, ê is a match if and only if all e ∈ I are. By guessing every S ⊊ P , we can in this way find all easy edges. The hard edges: Se = P . Suppose now Se = P . In this case we cannot search e in the intervals of some v ∈ P , because the incidence between e and v is encoded in J (e) instead of I(v). To find these edges we thus perform a reduction to box stabbing. The basic idea is simple: for every v ∈ P we know v ∈ Ji for some Ji = J (e), and for every v ∈ N , we know v ∈ / Ji for all Ji ∈ J (e). Thus, the vector (v1 , . . . , vt ) formed by the query vertices lies in a t-dimensional box Ji1 , . . . , J¯it , with the “positive” sides Ji chosen from J (e) and the “negative” sides J¯i chosen from their complements. Let us pin this down more precisely. Let e ∈ E, and recall J (e) = J1 (e), . . . , Jke (e). Denote by J¯(e) = J¯0 (e), . . . , J¯ke (e) the family of intervals that complements J , so that J¯0 (e) ⊎ . . . ⊎ J¯ke (e) = V \ J ∪ (e). Formally, J¯j (e) = [1, start(Jj+1 (e)) − 1] J¯j (e) = [end(Jj (e)) + 1, start(Jj+1 (e)) − 1]

j=0

(16)

j = 1, . . . , ke − 1

(17)

J¯j (e) = [end(Jj (e)) + 1, n]

j = ke

(18)

Note that J¯0 (e) and J¯ke may be empty. We use the intervals Jj and J¯j to transform every edge e into a set of boxes; at query time we then convert the vertices into a vector to stab the boxes. This is where the preprocessing comes into play, to preprocess the boxes so as to support box stabbing efficiently. Algorithm 5 and Algorithm 6 give respectively the pseudocode of preprocessing and query. The rest of the section proves the correctness and running time of the algorithms, and wrap up the proof of Theorem 4.1. V , E , I, J , w, τ ) Algorithm 5: EPartialMatcht -Preprocess(V 1 initialize Be = ∅; 2 foreach e ∈ E do

let J (e) = J1 , . . . , Jke and J¯(e) = J¯0 , . . . , J¯ke ; 4 foreach (i1 , . . . , it−τ ) ∈ [ke ]t−τ and (j1 , . . . , jτ ) ∈ {0} ∪ [ke ]τ do 5 add to Be the box [−∞, e] × [e, ∞] × Ji1 × . . . × Jit−τ × J¯j1 × . . . × J¯jτ ∈ Rt+2 ; S 6 preprocess e∈E Be for box stabbing; 3

Algorithm 6: EPartialMatcht (P, N ) 1 let P = {u1 , . . . , ut−τ } and N = {v1 , . . . , vτ }; 2 foreach subset S ⊊ P do

foreach interval I ∈ I(P \ S, N ) do pick any ê ∈ I; 5 if (S ∪ N ) ∩ J ∪ (ê) = S then 6 add I to the output set; 7 foreach interval I ∈ I(∅, N ) do 8 perform a box stabbing query on the vector q I = (start(I), end(I), u1 , . . . , ut−τ , v1 , . . . , vτ ); 3

4

24

4.2

Correctness

The next two claims prove the correctness of our algorithm. Claim 4.3. The loop of line 2 finds the set of matching edges with Se ⊊ P . Proof. Suppose e matches the query and Se ⊊ P . Since e ∈ / I ∪ (v) for all v ∈ N , it follows that ∪ e ∈ I for some I ∈ I (P \ Se , N ). The algorithm at some point reaches line 3 with S = Se and the above choice of I. It then picks some ê ∈ I, possibly different from e. However, since P \S = ̸ ∅, then e, ê ∈ I implies e, ê ∈ Ii (u) for some u ∈ P and some i ∈ [ku ]; by the niceness property of the interval representation, this implies J (e) = J (ê). On the one hand this implies S = P ∩ J (e) = P ∩ J (ê) ⊆ J (ê); on the other hand, N ∩ J (ê) = N ∩ J (e) = ∅. Therefore (S ∪ N ) ∩ J ∪ (e) = S, and the algorithm adds I, which contains e, to the output set. Now suppose the algorithm adds e to the output set. Thus, for some S ⊊ P , for some I ∈ I(P \ S, N ), the algorithm added I to the output set, and e ∈ I. On the one hand, this implies e ∈ I ∪ (P \ S, N ), which means e ∈ I(v) for every v ∈ P \ S and e ∈ / I(v) for every v ∈ N On ∪ the other hand, the algorithm found that S ⊆ J (ê) for some ê ∈ I. As noted above, however, J ∪ (e) = J ∪ (ê); therefore (S ∪ N ) ∩ J ∪ (e) = S, which means v ∈ J ∪ (e) for every v ∈ S and v∈ / J ∪ (e) for every v ∈ N . We conclude that V (e) ∩ (P ∪ N ) = P , as claimed. Claim 4.4. The loop of line 7 finds the set of matching edges with Se = P . Proof. Suppose B ∈ Be is stabbed by some q I . The first two coordinates imply e ∈ I and thus e∈ / I ∪ (v) for every v ∈ N ; while the last τ coordinates imply v ̸∈ Ji (e) for all i ∈ [ke ] for every v ∈ N . Thus, e ∈ / E(v) for every v ∈ N . Finally, the remaining t − τ coordinates imply, for every v ∈ P , that v ∈ Ji (e) for some i ∈ [ke ]. Thus Se = P , and moreover e ∈ E(v) for every v ∈ P . Now suppose e ∈ E matches the query and Se = P . We show that, among the boxes stabbed by the vectors {qq I : I ∈ I(∅, N )}, exactly one box is in Be . First, e ∈ I for some unique I ∈ I(∅, N ). Thus, for all I ′ ∈ I(∅, N ) with I ′ ̸= I, the vector q I ′ cannot stab any B ∈ Be . The vector q I instead stabs every B ∈ Be in the first two dimensions. Moreover, since J (e) ∪ J¯(e) partitions V , then every v ∈ P ∪ N falls precisely in one of those intervals, which implies that there exists precisely one B ∈ Be that is stabbed by q I along the last t dimensions, too. This concludes the proof.

4.3

Running time

Claim 4.5. Algorithm 5 can be run in time O ∥H∥ κt−1 logt+2 ∥H∥ . The exponent can be decreased e from t + 2 to t + 1 for the counting version of queries. Proof. For each e ∈ E the algorithm spends time O(κe ) to fetch J (e) and construct J¯(e), and creates at most ket−τ · (ke +P1)τ ≤ (ke + 1)t = O(ke · κt−1 e ) boxes, spending time O(t) = O(1) for each of them. Noting that k ≤ ∥H∥, the number of boxes and the running time are both in e∈E
e
P t−1 t−1 O κe e∈E ke = O κe ∥H∥ . By Theorem C.2 we can thus preprocess the boxes in time


t+2
t−1 O κt−1 = O ∥H∥ κt−1 · logt+2 ∥H∥ , e ∥H∥ · O log κe ∥H∥ e

(19)

which dominates the algorithm. The decrease in the exponent follows again Theorem C.2. V , E , I, J , w, τ ), Algorithm 6 can be run in time Claim 4.6. After EPartialMatcht -Preprocess(V t+2 t+1 O(κv log ∥H∥), and in time O(κv log ∥H∥) in the counting version.

25

Proof. The second bound follows again from Theorem C.2. Let us prove the first one. First part. The algorithm loops over 2t−τ − 1 ≤ 2t subsets S ⊊ P . For each S, computing I(P \ S, N ) takes time O(κv t log |E|), see the proof of Theorem 3.1 in Section 3.3. Checking (S ∪ N ) ∩ J ∪ (ê) = S requires, for every v ∈ S ∪ N , a binary search over the endpoints of J , which takes time O(ln κe ); this is repeated |I(P \ S, N )| ≤ κv t + 1 times, see Clm. 3.3. We maintain the output set as, once again, a disjoint union of intervals. To add I we perform a binary search, and we update the intervals intersected by I. Every endpoint ever appearing in our list is deleted at most once, and this easily implies a total work of O(k ∗ ln |E|) where k ∗ ≤ 2t (κv t + 1) is the total number of intervals possibly added, and |E| is the maximum size of the list at any time (since the intervals are disjoint and are subsets of E ). Thus the total cost of updating the output list is O(2t κv t2 ln |E|). The total time of the first part, as t = O(1) and |E| + κe = O(∥H∥), is:

O 2t · κv t (ln |E| + ln κe ) + O 2t κv t2 ln |E| = O (κv log∥H∥) . (20) Second part. Computing I(∅, N ) can be charged to the first part. For |I(∅, N )| ≤ κv t + 1 times,

t+2 the algorithm
invokes box stabbing, paying each time O log κt−1 , which for t = O(1) is e ∥H∥
t+2 t+2 O log ∥H∥ . Thus the second part takes in total O κv log ∥H∥ , which dominates the first part.

4.4

The special case N = ∅

For the special case N = ∅ of Theorem 4.1, we edit the pseudocode as follows. In Algorithm 5, the box constructed by line 5 becomes Ji1 × . . . × Jit−τ × J¯j1 × . . . × J¯jτ ∈ Rt . In Algorithm 6, the loop of line 7 is replaced by just one stabbing query on the vector (u1 , . . . , ut−τ , v1 , . . . , vτ ). It is immediate to check that the proofs of correctness carry over with minimal modifications. The running time analysis changes slightly, as follows. Algorithm 5 now uses t-dimensional rather than (t + 2)-dimensional boxes; therefore it takes time O(|E| κte ) · O (t log∥H∥)t . The second part of Algorithm 6 now costs only O (t log∥H∥)t , hence the total running time is in O(κv ) · O (t log∥H∥)t . For fixed t, both expressions yield the claimed bounds. Moreover, once again, for the counting version we can decrease the exponents from t to t − 1.

5

Answering VertexNeigh queries

This section presents our algorithms for VertexNeigh and EdgeNeigh. We focus on VertexNeigh, as the results for EdgeNeigh follow by taking the dual of H and exchanging κv and κe . Akin to PartialMatch, our algorithm relies on an interval representation of H. We solve the weighted version, where the input also includes a vertex weight function w : V → N. Our main result is: Theorem 5.1. There exists an algorithm for VertexNeigh with the following guarantees. Given a (κv , κe )-interval representation of a weighted hypergraph H = (V, E), • First, the algorithm constructs a data structure in time κe 2O(κv ) ∥H∥ log2κv −1 ∥H∥. • Then, (weighted) counting, sampling, and O(log∥H∥)-delay listing of any VertexNeigh query can be done in time 2O(κv log κv ) log2κv −1 ∥H∥. Note that the algorithm is exponential in κv , but only polynomial in κe . Previous work shows that, in many hypergraph datasets, κv is below 20 when κe is in the hundreds or thousands. In fact, this 26

holds for the stronger parameters β and α of [17]. There are good reasons to think that κv and κe are significantly smaller. Thus, Theorem 5.1 may actually perform well in practice. V , E , I, J ) be the (κv , κe )-interval representation of H = (V, E) given as input. As in Let (V Section 3, we assume V and E are relabeled so that V = (1, . . . , n) and E = (1, . . . , m). Our algorithm constructs two data structures that, for every vertex v ∈ V , allow us to efficiently access two disjoint sets N0 (v) and N1 (v) whose union is N (v). We define these sets as follows:  N0 (v) := u ∈ V : I ∪ (v) ∩ I ∪ (u) ̸= ∅ , (21) (22)

N1 (v) := N (v) \ N0 (v). We outline the idea behind the two data structures.

1. For N0 (v), we preprocess each vertex u by mapping it to a 2κv -dimensional vector whose coordinates encode the endpoints of the intervals in I(u). At query time, the intervals of I(v) and their complements induce a family of disjoint axis-aligned boxes. We select precisely those boxes whose endpoint constraints guarantee that at least one interval of the represented vertices intersects I ∪ (v). The selected boxes contain exactly the points corresponding to N0 (v), which can be found using orthogonal range queries. 2. For N1 (v), we take a complementary approach. Unlike N0 (v), this set cannot be characterized by the intersection of the intervals in I(v) and I(u), so the previous reduction to orthogonal range queries does not apply. We bypass this problem by reducing to a variant of box stabbing, which we call union stabbing, for which we show an efficient algorithm. We construct a family of two-dimensional boxes over V × V that captures all remaining adjacencies, possibly including some already covered by N0 . These boxes are obtained by combining intervals from the J side, either with individual vertices or with other intervals. Crucially, the niceness property of Definition 2.4 guarantees that a single representative edge suffices to capture the relevant adjacencies for each interval in I(v), and that each box either consists entirely of pairs already captured by N0 or contains none of them. We can therefore discard redundant boxes by testing a single pair per box, and reduce queries for N1 (v) to weighted union stabbing on the remaining family. Figure 5 gives a visual representation of both procedures. The next two subsections formalize this intuition, describing the algorithms for N0 (v) and N1 (v). Since N0 (v) and N1 (v) are disjoint, it is straightforward to combine the two algorithms into a single one.

5.1

Computing N0 (v)

This section proves the following result: Theorem 5.2. There exists an algorithm that, given a (κv , κe )-interval representation of a weighted hypergraph H = (V, E), in time 2O(κv ) |V | log2κv −1 |V | builds a data structure that can answer any counting/listing/sampling query on N0 (v) in time 2O(κv ln κv ) log2κv −1 |V |. The proof performs a reduction to the weighted version of Orthogonal Range Search, similarly to what we did for PartialMatch. The idea is to represent every vertex u ∈ V as a vector ⃗u, and construct on all those vectors a data structure for orthogonal range searching. Given a query vertex v, we will then construct a family of disjoint axis-aligned boxes that contains precisely the vectors of N0 (v). Throughout this section, we use ORQ-Preprocess, ORQ-Count, ORQ-Report and ORQ-Sample to denote the respective procedures for weighted Orthogonal Range Searching, whose existence is guaranteed by Theorem B.1. 27

e4 e2

v1

v5 v3 v4

v2

e1

e3 [e1 , e2 ] × [e3 , e4 ]

[e3 , e4 ] × [e3 , e4 ]

v5

e4

v5

v4

v1

[v3 , v3 ] × [v4 , v4 ]

v4

v2

e3

v3

e2

[v4 , v4 ] × [v3 , v3 ]

v3

v2

e1

v1 [e1 , e2 ] × [e1 , e2 ]

e1

e2

[e3 , e4 ] × [e1 , e2 ]

e3

e4

v1

(a) Retrieving N0 (v4 ).

v2

v3

v4

v5

(b) Retrieving N1 (v4 ).

Figure 5: Above: a hypergraph H with peeling sequence v1 , v2 , e1 , v3 , v4 , v5 , shown immediately before peeling the highlighted vertex v4 . Dashed outlines indicate previously peeled elements. Below: Retrieving the neighborhood of v4 . (a) The vertex-side intervals are I(v1 ) = {[e4 , e4 ]}, I(v2 ) = {[e3 , e3 ]}, I(v3 ) = {[e2 , e2 ]}, I(v4 ) = {[e3 , e4 ]}, and I(v5 ) = {[e2 , e4 ]}. The query interval I(v4 ) = {[e3 , e4 ]} induces the partition C1 = [e1 , e2 ] and C2 = [e3 , e4 ]. The shaded boxes represent intervals intersecting I(v4 ). Orthogonal range queries over these boxes yield {v1 , v2 , v4 , v5 }. (b) The only nonempty edge-side interval family is J (e1 ) = {[v3 , v3 ], [v4 , v4 ]}. Let J = [v3 , v3 ] and J ′ = [v4 , v4 ]. Combining these intervals produces four rectangles: J × J, J × J ′ , J ′ × J, and J ′ × J ′ . The shaded rectangles J × J ′ and J ′ × J are the only ones retained after filtering. Stabbing them at v4 yields N1 (v4 ) = {v3 }.

28

5.1.1

Preprocessing

For every u ∈ V with ku ≥ 1, let Ii (u) = [li , ri ] for i ∈ [ku ], where without loss of generality we assume ri < li+1 . The vector associated to u is then simply: (23)

⃗u := (l1 , r1 , . . . , lku , rku , 0, . . . , 0 ) ∈ {0, . . . , m}2κv . | {z } 2(κv −ku )

⃗ : u ∈ V }. Then, construct an orthogonal range counting structure on the indexed family of vectors {⃗u The pseudocode is given by Algorithm 7. V , E , I, J , w) Algorithm 7: VertexNeigh-Preprocess(V u for every u ∈ V ; 1 compute the vector ⃗

⃗ : u ∈ V } with weighting w; 2 run ORQ-Preprocess on the indexed family {⃗ u

5.1.2

Query

We describe the query phase of VertexNeigh. The pseudocode is given by Algorithm 8. Algorithm 8: VertexNeigh(v) 1 compute the partition C1 , . . . , C2kv +1 of E induced by the intervals I1 (v), . . . , Ikv (v) of I(v); 2 initialize B ∗ = ∅;

κv 3 foreach B ∈ ∪k=1 Bk (v) do

if B is a v-box then add the extended box B ∗ = B × {0} × . . . × {0} to B ∗ 6 for counting, P 7 return B ∗ ∈B⋆ ORQ-Count(B ∗ ); 8 for sampling, 9 pick B ∗ ∈ B ⋆ with probability proportional to ORQ-Count(B ∗ ); 10 return ORQ-Sample(B ∗ ); 11 for reporting, 12 warm up ORQ-Report(B ∗ ) on every B ∗ ∈ B ⋆ ; 13 run the rest of ORQ-Report(B ∗ ) on every B ∗ ∈ B ⋆ ; 4

5

Let v ∈ V be the query vertex, and let I(v) = I1 (v), . . . , Ikv (v), where for every i = 1, . . . , kv we have Ii (v) = [xi , yi ] ⊆ [m]. Again, we assume the intervals are sorted increasingly, so that yi < xi+1 . Define y0 := 0 and xkv +1 := m + 1. Boxes. Consider then the following set of c := 2kv + 1 cells C1 , . . . , C2kv +1 : C2j := Ij (v) C2j+1 := [yj + 1, xj+1 − 1]

j = 1, . . . , kv ,

(24)

j = 0, . . . , kv .

(25)

In words, the even cells C2 , . . . , C2kv are the intervals of I(v), and the odd cells C1 , . . . , C2kv +1 are the gaps between them. Note that C1 and C2kv +1 may be empty.

29

Next, for every k = 1, . . . , κv , consider the following grid partition of [m]2k induced by C1 , . . . , C2kv +1 : Bk (v) := {C1 , . . . , C2kv +1 }2k . Thus, Bk (v) is a collection of axis-aligned boxes. For every B ∈ Bk (v), the extension of B to 2κv dimensions is the box: B ∗ = B × {0} × · · · × {0} . | {z }

(26)

2(κv −k)

For every such B ∗ let V (B ∗ ) = {v ∈ V : ⃗v ∈ B ∗ }. We now identify the subset of boxes that have the property of containing the vectors of vertices in N0 (v), that is, such that V (B ∗ ) ⊆ N0 (v). Definition 5.3. Let k ∈ {1, . . . , κv }. A box B = Ca1 × Cb1 × · · · × Cak × Cbk ∈ Bk (v) is a v-box if ai ≤ 2j ≤ bi for some i ∈ [k] and j ∈ [kv ]. An extended box B ∗ is a v-box whenever B is. We let B(v) = B1 (v) ∪ . . . ∪ Bκv (v), and we let B ∗ (v) be the set of all extensions of v-boxes of B(v). At query time, the algorithm runs an orthogonal range query on every v-box B ∗ ∈ B ∗ (v), and returns the aggregate size of the output sets. 5.1.3

Correctness

The following lemma gives the correctness of the algorithm. U Lemma 5.4. N0 (v) = B ∗ ∈B∗ (v) V (B ∗ ), and in particular: 1. For every B ∗ ∈ B ∗ (v) we have V (B ∗ ) ⊆ N0 (v). 2. For every u ∈ N0 (v) there exists a unique B ∗ ∈ B ∗ (v) such that u ∈ V (B ∗ ). Proof. Item 1. Let B ∗ = B × {0}, . . . , {0} where B = Ca1 × Cb1 × · · · × Cak × Cbk ∈ Bk (v) is a v-box. Since B is a v-box, there exist i ∈ [k] and j ∈ [kv ] such that ai ≤ 2j ≤ bi , which implies Ij (v) = C2j ∈ {Cai , . . . , Cbi }. Now, suppose ⃗u = (l1 , r1 , . . . , lku , rku , 0, . . . , 0) ∈ B ∗ for some u ∈ V . Since ⃗u ∈ B ∗ , then necessarily ku = k, and moreover li ∈ Cai and ri ∈ Cbi for every i ∈ [k], where [li , ri ] = Ii (u). If 2j = ai , this implies li ∈ Cai = Ij (v), and therefore Ii (u) ∩ Ij (v) ̸= ∅; the same conclusion holds if 2j = bi . If instead ai < 2j < bi , then we have Ij (v) = C2j ⊆ [li , ri ] = Ii (u), hence again Ii (u) ∩ Ij (v) ̸= ∅. We conclude that u ∈ N0 (v). Item 2. Let u ∈ N0 (v). Let ⃗u = (l1 , r1 , . . . , lku , rku , 0, . . . , 0) be the vector associated to u, and for every i = 1, . . . , ku let ai , bi ∈ [2kv + 1] be such that li ∈ Cai and ri ∈ Cbi . Note that such ai , bi exist and are unique, since li , ri ∈ [m] and the intervals C1 , . . . , C2kv +1 form a partition of [m]. Finally, let B = Ca1 × Cb1 × . . . × Cak × Cbk , and let B ∗ be its extension. By construction, B ∗ is unique and ⃗u ∈ B ∗ . It remains to show that B is a v-box. To this end note that, since u ∈ N0 (v), then there exist i ∈ [ku ] and j ∈ [kv ] such that Ii (u) ∩ Ij (v) ̸= ∅. As li ∈ Cai and ri ∈ Cbi this implies Ij (v) ∈ {Cai , . . . , Cbi }, and since Ij (v) = C2j , then ai ≤ 2j ≤ bi too. 5.1.4

Running time

Lemma 5.5. Algorithm 7 can be run in time 2O(κv ) |V | log2κv −1 |V |. Proof. Building the vectors takes time O(κv |V |). Since the vectors lie in R2κv , the bounds follow from Theorem B.1 with d = O(κv ). 30

Lemma 5.6. After executing VertexNeigh-Preprocess, Algorithm 8 can be run: • in the counting and sampling versions, in time 2O(κv ln κv ) log2κv −1 |V |. • in the listing version, with O(1)-delay per element, after an initial warm-up time of 2O(κv ln κv ) log2κv −1 |V |.
Proof. The loop of line 3 performs O (2kv + 1)2κv = 2O(κv ln κv ) iterations, each of which entails work O(κv ) to check if B is a v-box, and again work O(κv ) to add the extended box B ∗ to B ∗ . Then, by Theorem B.1 with d = O(κv ) and P = V all the claimed bounds follow.

5.2

Computing N1 (v)

This section proves the following result: Theorem 5.7. There exists an algorithm that, given a (κv , κe )-interval representation of a weighted hypergraph H = (V, E), in time O(κe κv ∥H∥ log∥H∥) builds a data structure that, on query v ∈ V , can: • count N1 (v) in time O(1), • list N1 (v) with O(log∥H∥) delay per element, • sample from N1 (v) in time O(log∥H∥). The proof performs a reduction to a particular variant of box stabbing, namely union stabbing. In the classical 1-d formulation, given a set of intervals X1 , . . . , XN and a query point x, box stabbing asks to retrieve all intervals Xi containing x. In union stabbing, instead, each Xi is associated with a Ssecond interval Yi , possibly over a different domain. Given x, the problem asks now to retrieve Y :x∈X Y , that is, the union of all Yi whose Xi ’s are stabbed. To reduce the problem of computing N1 (v) to union stabbing, define the set of 2-d vectors N1 := {(v, u) : u ∈ N1 (v)}. We show that this set can be encoded as the union of a family of axis-aligned rectangles Xi × Yi over V × V . At this point, N1 (v) will be precisely the result of a union stabbing query on v. Let us give some intuition about the construction of N1 . Observe that every pair (v, u) ∈ N1 has a witnessing edge in which at least one of the two incidences is represented through J . Thus, to capture these adjacencies, we build rectangles by combining all intervals of J either with individual vertices or with other intervals of J . The key observation is that the niceness property of Definition 2.4 allows us to capture potentially many adjacencies with a single rectangle. Moreover, the same property guarantees that each rectangle either consists entirely of adjacencies already captured by N0 , or contains none of them. Thus, by testing a single pair per rectangle, we can discard the redundant rectangles and obtain a family whose union represents exactly N1 . The rest of the section is dedicated to formalizing this intuition. 5.2.1

Preprocessing

V , E , I, J ) be a (κv , κe )-interval representation of a Preprocessing is composed of two phases. Let (V hypergraph H = (V, E). In the first phase, the procedure builds the family of rectangles representing exactly N1 . To this end, it first generates a family R̂. In general R̂ could contain pairs that have already been witnessed in N0 , thus with an additional scan over R̂ it computes the family R. As we prove in Section 5.2.3, for every v ∈ V , R(v) = N1 (v). Hence, R contains all the information we need. In the latter part, the algorithm builds a data structure that supports efficient queries on R(v) for every v ∈ V . As anticipated in the introduction of this section, we achieve this by reducing the problem to a weighted union stabbing problem, which we formally define as follows. 31

Definition 5.8. Let P = {P1 , . . . , PN } be a family of intervals over [n], let Q = {Q1 , . . . , QN } be a familyP of intervals over [m], and let ω : [m] → S N be a weighting of [m]. For any A ⊆ [m], let ω(A) = u∈A ω(u). For q ∈ [n], define U (q) = i:q∈Pi Qi . A weighted union stabbing query with q ∈ [n] asks to: • return ω(U (q)) (counting), • list the elements of U (q) (reporting),   ω(u) • sample from the distribution ω(U (q))

u∈U (q)

(sampling).

Note that union stabbing is a special case of the stabbing semigroup problem (See for instance S , +), [2]). In this problem, each interval Pi is assigned to an element of a commutative semigroup (S and a query q ∈ [n] returns the sum of the elements associated to the intervals containing q. Observe S , +) = (2[m] , ∪) and assigning Qi to Pi for each i, each stabbing-semigroup query that, by taking (S q ∈ [n] returns exactly U (q). However, standard semigroup bounds assume constant-time operations on constant-size elements, whereas representing arbitrary subsets of [m] and computing their unions may require non-constant time and space. Thus, these bounds do not directly yield our counting, reporting, and sampling guarantees. Nonetheless, we claim that there exists a data structure that supports counting/listing/sampling efficiently on any weighted union stabbing instance. The proof for this can be found in Section C.3. Theorem 5.9. There exists a data structure that, given two families of intervals P = {P1 , . . . , PN }, Q = {Q1 , . . . , QN } over [n] and [m] and ω : [m] → N, can be built in time O(n + m + N log m) and on input q ∈ [n] supports the following operations: • return ω(U (q)) in time O(1). • list U (q) in total time O(|U (q)| log m) and with O(log m) delay.   ω(u) • sample from the distribution ω(U in time O(log m). (q)) u∈U (q)

Now let SR = {Xi × Yi : i ∈ [|R|]} be the family of rectangles built by the algorithm, and let R(v) = i:v∈Xi Yi . Observe that R can be seen as a weighted union stabbing instance, with P = (Xi )i∈[|R|] , Q = (Yi )i∈[|R|] and weight function w. Thus, we apply Theorem 5.9 to preprocess this instance, and obtain a data structure D capable of efficiently answering queries on R(v). The preprocessing procedure just described is summarized by Algorithm 9. Similarly to Section 5.1, we make use of US-Prec, US-Count, US-Report and US-Sample to refer to the respective union stabbing procedures. 5.2.2

Query

Let D be the data structure returned by Algorithm 9. By Theorem 5.9, this structure supports efficient counting, listing and sampling on R(v) for every v ∈ V . Thus, given v ∈ [n], we simply perform the corresponding weighted union stabbing query on D and return the result. This is formalized in Algorithm 10.

32

V , E , I, J , w) Algorithm 9: N1-Preprocess(V 1 R̂ ← ∅; 2 foreach v ∈ V

do foreach I ∈ I(v) do 4 choose any e ∈ I; 5 foreach J ∈ J (e) do 6 R̂ ← R̂ ∪ {{v} × J, J × {v}}; 7 foreach e ∈ E do 8 foreach J, J ′ ∈ J (e) do 9 R̂ ← R̂ ∪ {J × J ′ }; 10 R ← ∅; 11 foreach R ∈ R̂ do 12 Let R = X × Y , choose any x ∈ X, y ∈ Y ; 13 if I ∪ (x) ∩ I ∪ (y) = ∅ then 14 R ← R ∪ {R} 15 denote R = {Xi × Yi : i ∈ [N ]}, then P ← (Xi )i∈[N ] and Q ← (Yi )i∈[N ] ; 16 D ← US-Prec(P, Q, w); 17 return D; 3

5.2.3

Correctness

V , E , I, J , w) and D the returned Let R be the family of rectangles built by Algorithm 9 on input (V data structure. We prove that R(v) = N1 (v) for every v ∈ V . Observe that this is sufficient to prove the correctness of all the procedures. Indeed, Algorithm 9 and Algorithm 10 respectively build and interrogate D, whose correctness is already guaranteed by Theorem 5.9. V , E , I, J ) be the representation of H = (V, E) given in input to Algorithm 9. Lemma 5.10. Let (V Then, for every v ∈ V , R(v) = N1 (v). Proof. Let R̂ be the family built before filtering, let X × Y ∈ R̂, and let (x, y) ∈ X × Y be the pair tested at Line 12. We claim that, for every (x′ , y ′ ) ∈ X × Y , y ′ ∈ N0 (x′ ) ⇐⇒ I ∪ (x) ∩ I ∪ (y) ̸= ∅.

(27)

Note that each of X and Y is either a singleton or an interval of J (e) for some e ∈ E. In both cases, by the niceness property of the representation, we have I(x) = I(x′ ) and I(y) = I(y ′ ). Therefore, I ∪ (x′ ) ∩ I ∪ (y ′ ) = I ∪ (x) ∩ I ∪ (y), and the claim follows from the definition of N0 (x′ ). We now prove that R(v) = N1 (v). (⊆) Let u ∈ R(v). By definition of R, there exists R ∈ R such that (v, u) ∈ R and I ∪ (v ′ )∩I ∪ (u′ ) = ∅ for some (v ′ , u′ ) ∈ R. By construction, we have R ⊆ R̂. Thus, by Equation (27), we conclude that u∈ / N0 (v). Moreover, u ∈ N (v), since every rectangle of R is built from incidences with a common edge. Hence, u ∈ N (v) \ N0 (v) = N1 (v). (⊇) Let u ∈ N1 (v). Then there must exist an edge e ∈ E containing v and u such that v ∈ J ∪ (e) or u ∈ J ∪ (e). We distinguish two cases. If both v ∈ J ∪ (e) and u ∈ J ∪ (e), let J, J ′ ∈ J (e) be two intervals containing v and u, respectively. Observe that the algorithm builds the rectangle R = J × J ′ at Line 9, which contains (v, u). Otherwise, assume that e ∈ I ∪ (v) and u ∈ J ∪ (e), the symmetric case being analogous. Let I ∈ I(v) be the interval containing e and J ∈ J (e) the one containing u. At Line 6, the algorithm selects an edge e′ ∈ I and builds {v} × J ′ for every J ′ ∈ J (e′ ). 33

Since e, e′ ∈ I, the niceness property guarantees that J (e) = J (e′ ), meaning that the rectangle {v} × J containing (v, u) is built. Hence, in both cases, u ∈ R̂(v). Moreover, I ∪ (u) ∩ I ∪ (v) = ∅ since u∈ / N0 (v). Thus, by Equation (27), the corresponding rectangle is not discarded, and consequently u ∈ R(v).

Algorithm 10: N1-Query(D, v) 1 for counting;

return US-Count(D, v); 3 for sampling; 4 return US-Sample(D, v); 5 for listing; 6 return US-Report(D, v); 2

5.2.4

Running time

We first prove that the number of boxes built by Algorithm 9 is bounded by some function on the parameters κv , κe . Then, we analyze the running time of the three algorithms. V , E , I, J , w) be the interval representation of H = (V, E) in input to Algorithm Lemma 5.11. Let (V 9 and let R be the family of filtered boxes, then |R| = O(κe ∥H∥). Proof. Let R̂ be the family of rectangles built at the end of Line 9. Observe that the algorithm builds two different types of rectangles: • for every v ∈ V and every interval I ∈ I(v) the algorithm picks eI ∈ I. Then, for every J ∈ J (eI ) it builds {v} × J and J × {v}. Recall that, by definition, every eI has O(κe ) intervals J ∈ J (eI ). In total, this yields X X X 2 |J (eI )| ≤ 2κe |I(v)| = O(κe ∥H∥) (28) v∈V I∈I(v)

v∈V

rectangles. • for every e ∈ E and every pair of intervals J, J ′ ∈ J (e), the algorithm builds J × J ′ . Since every edge has O(κe ) intervals, a total of X X |J (e)|2 ≤ κe |J (e)| = O(κe ∥H∥) (29) e∈E

e∈E

rectangles are built. Since R ⊆ R̂, we obtain |R| = O(κe ∥H∥), as claimed. V , E , I, J , w) be the interval representation of H = (V, E) given as input. Then Lemma 5.12. Let (V Algorithm 9 can be run in time O(κe κv ∥H∥ log∥H∥). Proof. We first bound the time required to build R. Then, the time to preprocess R follows directly from Theorem 5.9. Putting these two together proves the lemma. By Lemma 5.11, at most O(κe ∥H∥) rectangles are built, each requiring O(1) time. Let R ∈ R̂ and let (x, y) ∈ R be the pair of elements chosen by the procedure. At Line 13, the algorithm 34

tests whether I ∪ (x) ∩ I ∪ (y) = ∅. Since I ∪ (x) and I ∪ (y) are ordered, and each contains O(κv ) intervals, this can be done in time O(κv ) with a linear scan. Putting everything together, building R requires time O(κv κe ∥H∥). Now let R = {Xi × Yi : i ∈ [N ]}, where N = |R|. The algorithm builds the data structure of Theorem 5.9 on the instance P = (Xi )i∈[N ] , Q = (Yi )i∈[N ] , and weighting w. Since both families consist of intervals over V , by Theorem 5.9 the structure can be built in time O(|V | + N log |V |). Moreover, by Lemma 5.11, N ≤ |R̂| = O(κe ∥H∥), yielding O(κe ∥H∥ log∥H∥) time. The claimed bound follows. Lemma 5.13. After executing N1-Preprocess, Algorithm 10 can be run on input v ∈ V 1. in the counting version in time O(1), 2. in the listing version in total time O(|R(v)| log∥H∥), with O(log∥H∥) delay per element, 3. in the sampling version in time O(log∥H∥). Proof. Immediate from Theorem 5.9.

6

Lower Bounds

In this section, we establish conditional lower bounds for many problems arising naturally in our framework, including PartialMatch (in both versions) and Neigh, as well as all the primitives introduced in Section 1, under the Orthogonal Vectors Conjecture (OVC) and the strong SetDisjointness Conjecture (SDC). We also provide a lower bound for the primitive Contain based on Boolean Matrix Multiplication (BMM). We first recall the formulation of the Orthogonal Vectors Conjecture (OVC) used throughout this section. Conjecture 6.1 (Orthogonal Vectors Conjecture, see [1]). There is no ε > 0 such that, for all c ≥ 1, there is an algorithm that, given a set U ⊆ {0, 1}d of n Boolean vectors, where d = c log n, determines whether there exist two distinct a, b ∈ U such that a · b = 0 in time O(n2−ε ). In particular, OVC rules out algorithms with running time 2o(d) n2−ε for any fixed ε > 0. We refer to the corresponding decision problem as Orthogonal Vectors (OV). Hypothesis

Primitive

Preprocessing time/space

Query time

OVC

EdgePartialMatch/ VertexPartialMatch, VertexSat/EdgeSat, Superset, SubH, Neigh, Union

2o(κ) ∥H∥2−δ

2o(κ+t) ∥H∥1−ε

SDC

Adj, Venn, NeighINT

∥H∥1+o(1)

∥H∥1/2−ε

BMM

Contain

∥H∥ω0 /2−δ

∥H∥(ω0 −2)/2−ε

Table 2: Summary of conditional lower bounds. Each row rules out the simultaneous preprocessing (or space) and query bounds shown, for fixed ε, δ > 0. Here κ denotes bidegeneracy and t denotes query size. The SDC lower bound for NeighINT holds even for constant bidegeneracy, whereas those for Adj and Venn hold for general hypergraphs. We next recall the SetDisjointness problem and its associated conjecture: 35

Definition 6.2 (SetDisjointness). Given a collection of sets S = {S1 , . . . , Sm } over a universe U , the SetDisjointness (SD) problem asks to preprocess S so that, for any two indices i, j ∈ [m], one can determine whether Si ∩ Sj = ∅. P The size of a SetDisjointness instance is defined as N = |U | + m i=1 |Si |. Conjecture 6.3 (Strong SetDisjointness Conjecture, see [30]). Any data structure for the SetDis2 jointness problem with query time T requires S = Ω̃( N ) space. T2 Our results are summarized in Table 2.

6.1

Reductions from Orthogonal Vectors

We prove a lower bound for an easier version of EdgePartialMatch, Superset, where the negative set is empty. Observe that the same lower bound immediately applies to SubH, since Superset(S) > 0 for some S ⊆ V if and only if S appears in the output of SubH(S). Theorem 6.4. Suppose there exist ε, δ > 0 such that for all r > 0, there is a data structure solving the decision version of Superset(S) on κ-bidegenerate hypergraphs with preprocessing time O(2κ/r ∥H∥2−δ ) and query time O(2(κ+|S|)/r ∥H∥1−ε ). Then OVC is false. A similar conclusion holds for EdgeNeigh(e) and Union(F ) queries, with query time O(2κ/r ∥H∥1−ε ) and O(2(κ+|F |)/r ∥H∥1−ε ), respectively. Proof. Fix c ≥ 1 and consider an OV instance with vectors x1 , . . . , xn ∈ {0, 1}d , where d = c log n. Let us consider these vectors to be subsets S1 , S2 , . . . , Sn ⊆ [d]. The OV instance is a yes-instance iff ∃i, j such that Si ⊆ Sj . Let us solve the OV instance by our data structure for Superset queries. We first create the hypergraph H corresponding to set system S1 , S2 , . . . , Sn . The hypergraph H has d vertices and n hyperedges, and ∥H∥ = O(nd). It is trivially d-bidegenerate and can be constructed in O(nd) time. We will choose r to be a sufficiently large constant depending on other (constant) parameters. The preprocessing time is O(2d/r (nd)2−δ ). To solve the OV instance, we invoke queries Superset(S1 ), . . . , Superset(Sn ). The OV instance is a yes-instance iff any of these queries returns a non-zero. The total query time is O(22d/r (nd)2−ε ). −1 −1 The overall running time is O(nd + 2r c log n (n log n)2−δ + 22r c log n (n log n)2−ε ). For sufficiently large constant r (depending on c, ε, δ), the running time is O(n2−α ), for some constant α > 0. Hence, OVC is false. For EdgeNeigh(e) queries, we can use a direct reduction. Observe that OV instance is a yesinstance iff there exists i, j such that Si ∩ Sj = ∅. Equivalently, there exists some i such that EdgeNeigh(Si ) < n (so there exists some Sj that it does not intersect). We can make n EdgeNeigh queries to solve the OV instance. The running time math of the previous paragraph can be followed to complete the proof. For Union queries, we use a dual reduction. We start from the same OV instance with vectors x1 , . . . , xn ∈ {0, 1}d , where d = c log n and c ≥ 1. We create the hypergraph H by adding one vertex vi for each xi , and one hyperedge eℓ = {vi : xi [ℓ] = 1} for each ℓ ∈ [d], and identifying twin edges. H is trivially d-bidegenerate S and can be constructed in O(nd) time. Consider the set Fi = {eℓ : xi [ℓ] = 1}. We have vj ∈ e∈Fi e ⇐⇒ ∃ℓ : xi [ℓ] = xj [ℓ] = 1 ⇐⇒ xi · xj > 0, so that Union(Fi ) = |{j ∈ [n] : xi · xj > 0}|. To solve the OV instance, we create n Union(Fi ) queries, where i ∈ [n]. The OV instance is a yes-instance iff Union(Fi ) < n for some i. Again, the same arguments as the previous paragraphs complete the proof.

36

6.2

Reductions from SetDisjointness

We first consider a refined version of Neigh involving the neighborhoods of multiple vertices: given a query set P ⊆ V , we want to compute the cardinality of the intersection of their neighborhoods, T | v∈P N (v)|. We show that, assuming SDC, such queries cannot be supported with polylogarithmic time and near-linear space, even on hypergraphs of constant bidegeneracy. In fact, the lower bound already holds for |P | = 2, even when the task is merely to determine whether their neighborhoods intersect. This shows that the running time bounds we achieve for Neigh cannot be generalized to a “neighbor version” of PartialMatch. Definition 6.5 (NeighINT). Given a hypergraph H = (V, E), a NeighINT (neighborhood intersection) T query takes in input a set of vertices P ⊆ V and asks to compute | v∈P N (v)|. Theorem 6.6. Assuming SDC, for every ε > 0, there is no data structure for NeighINT on 1 e e κ-bidegenerate hypergraphs with space 2O(κ) ∥H∥1+o(1) and query time 2O(κ) ∥H∥ 2 −ε . Proof. Let S = {S1 , . . . , Sm } over a universe U be an instance of SD. We construct a bipartite graph B = (V, E) in the following way: for every v ∈ U , we add a vertex v to V ; for every Si ∈ S, we add a vertex ai to V ; then, we add edges {u, ai } to P E if and only if u ∈ Si . The resulting graph is clearly 2-bidegenerate, has size ∥B∥ = O(|U | + m i=1 |Si |) = O(N ) and we immediately observe that N (ai ) ∩ N (aj ) = Si ∩ Sj . So, one single query of NeighINT with P = {ai , aj } can determine the size of that intersection, and answer the corresponding SD query. A data structure 1 e e with space 2O(κ) ∥H∥1+o(1) = O(∥B∥1+o(1) ) = O(N 1+o(1) ) = S and query time 2O(κ) O(∥H∥ 2 −ε ) = 1 1 O(∥B∥ 2 −ε ) = O(N 2 −ε ) = T would be able to answer SD with ST 2 = O(N 2−2ε+o(1) ), contradicting SDC. Then, we consider Adj and Venn and show that, assuming SDC, such queries cannot be supported with polylogarithmic time and near-linear space on general hypergraphs. Theorem 6.7. Assuming SDC, for every ε > 0, there is no data structure for Adj or Venn on general hypergraphs with space ∥H∥1+o(1) and query time O(∥H∥1/2−ε ). Proof. Let S = {S1 , . . . , Sm } over a universe U be an instance of SD. For Adj, we construct a hypergraph H with one vertex vi for each Si and one hyperedge ex for each x ∈ U , where vi ∈ ex if and only if x ∈ Si . Then Adj(vi , vj ) is a yes-instance iff |Si ∩ Sj | > 0. For Venn, we construct the hypergraph H = (U, {Si }i∈[m] ) and observe that any query Venn(Si , Sj , Sk ) allows us to compute |Si ∩ Sj | by summing |(Si ∩ Sj ) \ Sk | and |Si ∩ Sj ∩ Sk |. Both constructions take O(N ) time and each SD query can be answered with a single query to the corresponding primitive. The claimed bounds follows from SDC.

6.3

Reductions from Boolean Matrix Multiplication

We let ω0 denote the Boolean matrix multiplication exponent. Consider answering Contain queries: given hyperedges e, e′ , determine if e ⊆ e′ . Theorem 6.8. Consider a data structure for general hypergraphs for answering Contain queries with preprocessing time O(∥H∥α ) and worst-case query time O(∥H∥δ ). Then, either α ≥ ω0 /2 or δ ≥ (ω0 − 2)/2. Proof. Consider the problem of multiplying two Boolean n × n matrices A and B. It is convenient to think in terms of AT and B, where the matrix product corresponds to all pairwise dot products of 37

the column vectors. We create a hypergraph H where the vertex set correspond to the coordinates of the vectors. We define two sets of hyperedges EA and EB . We treat each column vector of AT as an incidence vector of a hyperedge of EA . We take the complement of each column vector of B to get the hyperedges of EB . Observe that for e ∈ EA and e′ ∈ EB , the corresponding matrix product entry is 1 iff e ̸⊆ e′ . To compute the matrix product, we construct the hypergraph H and set up the data structure for answering Contain queries. We make query for all pairs of hyperedges e ∈ EA and e′ ∈ EB . The total running time is O(n2 + P + n2 Q), where P is the preprocessing time and Q is the query time. Suppose that P = O(∥H∥α ) and Q = O(∥H∥δ ). Since ∥H∥ = O(n2 ), we get the total running time to be O(n2 + n2α + n2+2δ ). We must have max{2, 2α, 2 + 2δ} ≥ ω0 . Hence, either α ≥ ω0 /2 or δ ≥ ω02−2 .

38

A

Auxiliary Proofs

A.1

Implications in Figure 1

In what follows, MH ∈ {0, 1}n×m denotes the incidence matrix of a hypergraph H with n vertices and m edges. Niceness [17]. H = (V, E) is (α, β)-nice if E = E1 ⊎ E2 such that (V, E1 ) has rank at most α and (V, E2 ) has degree at most β. It is immediate to see that hypergraphs of rank at most α and hypergraphs of degree at most β are proper special cases of (α, β)-nice hypergraphs. Moreover, if H is (α, β)-nice, then every submatrix of MH contains a column of weight at most α or a row of weight at most β; thus H is (β, α)-bidegenerate. To see that the implication is strict, take the “sunflower” hypergraph on V = [2n], where for every i ∈ [n] there is a hyperedge {i} ∪ {n + 1, . . . , 2n}. This hypergraph is not (α, β)-nice for any α, β < n, yet it is 1-bidegenerate: every twin-free submatrix of MH either contains a row in [n], which has weight 1, or it has a single row, and therefore a column of weight at most 1. ∞-degeneracy ([50]). The ∞-degeneracy can be defined as the smallest k such that every twinfree submatrix obtained by deleting rows from MH contains a row of weight at most k. Since deleting columns cannot increase the weight of the rows, this implies (k, 0)-bidegeneracy and thus k-bidegeneracy. To see that the containment is strict, the complete graph Kn has ∞-degeneracy n − 1 but bidegeneracy 2. Hyperedge degeneracy [51]. This is a stronger notion of ∞-degeneracy that keeps duplicates. The hyperedge degeneracy is the smallest k such that every submatrix obtained by deleting rows from MH contains a row of weight at most k. The ∞-degeneracy is therefore at most the hyperedge degeneracy. (k, q)-cores [38]. A (k, q)-core is the (hypergraph of) a maximal submatrix of H where all rows have weight at least k and all columns have weight at least q. Note that this does not require the submatrix to be twin-free. Thus, if H has no (k, q)-core, then H is (k, q)-bidegenerate. To see that the inclusion is strict, just take H for MH = 1 n × 1 ⊤ n ; it has an (n, n)-core but it is 1-bidegenerate. Bidegeneracy of the incidence graph [21]. The bidegeneracy of a bipartite graph is defined as the maximum, over all subgraphs, of the smallest (≤ 2)-hop neighborhood of a vertex. In particular, it bounds the minimum degree of every subgraph. Applied to the incidence graph of H, it bounds the (k, k)-core number of H.

A.2

Implementing primitives

We show that list of primitives in the introduction can be implemented using EdgeSat or VertexNeigh queries. • Adj: given u, v ∈ V , decide whether there exist a hyperedge containing both u and v. This is the EdgeSat query xu ∧ xv . • Contain: given hyperedges e, e′ ∈ E, decide whether e ⊆ e′ . We can compute the size of e \ e′ with the dual of an EdgeSat query, which is ye ∧ ye′ . • EdgeNeigh: given e, return the number of edges intersecting e. This is the dual of a VertexNeigh query. • Superset: Vgiven vertex subset S ⊆ V , count the number of hyperedges f ⊇ S. This is the EdgeSat query s∈S xs .

39

• SubH: return the subhypergraph induced by S. Specifically, list out all distinct, non-empty sets e ∩ S (over hyperedges e). We make a Superset query over all subsets S ′ ⊆ S and recover the intersection counts by inclusion-exclusion. S • Union: givenWa subset F of hyperedges, compute the union size | f ∈F f |. This is the dual of an EdgeSat query f ∈F xf . • Venn: given three hyperedges e, f, g, compute the “Venn diagram” of all intersection patterns between these hyperedges. This can be expressed as 7 different dual EdgeSat queries, one for each combination of including/excluding each hyperedge (minus the all excluding ye ∧ yf ∧ yg ). • EdgePartialMatch: Given a set P of "positive vertices" and a set N of "negative vertices", count the number of hyperedges that contain P and have no vertex of N . This is again an EdgeSat query.

B

Results on Orthogonal Range Searching

Let P = (pp1 , . . . , p n ) ⊆ Rd be an indexed family of points and w : P → N a weight function. With a slight abuse of notation, we use set notation for indexed P families. ′ For every X ⊆ P , denote by wX the distribution over X that assigns probability w(x)/ x′ ∈X w(x ) to x ∈ X. An orthogonal range search query is specified by an axis-aligned d-dimensional box B. The output of the query comes in three flavors, defined as follows: P • In the counting version, w(P ∩ B) = x∈P ∩B w(x). • In the sampling version, (the index of) an element drawn from wP ∩B . • In the reporting version, (the indices of) the set P ∩ B itself. Standard techniques based on range trees [3, 27] can be adapted to obtain bounds on all three flavors. The following theorem states these bounds with explicit dependence on the dimension d. The classical bounds are immediately recovered when d is constant. Theorem B.1 (Orthogonal range searching). Given an indexed family of points P ⊆ Rd and a weight function w : P → N, in time 2O(d) |P | logmax(1,d−1) |P | one can construct a data structure that, on input an axis-aligned d-dimensional box B, supports the following operations: • Returning w(P ∩ B) in time 2O(d) logmax(1,d−1) |P |. • Sampling from wP ∩B in time 2O(d) logmax(1,d−1) |P |. • Listing P ∩ B with O(1) delay, after an initial warm-up time of 2O(d) logmax(1,d−1) |P |. Proof. We adapt layered range trees (see [27]). Let us first recall how queries on range trees work. The case d = 1 is a simple binary search on an interval, and the bounds follow accordingly. Let d ≥ 2. For a set of n d-dimensional points P with coordinates x1 , . . . , xd , a d-dimensional range tree is defined recursively. The top level is a balanced BST on the first coordinate x1 . Every node ν represents a canonical subset P (ν) and stores an associated (d − 1)-dimensional range tree Td−1 (P (ν)) built on coordinates x2 , . . . , xd . Given a query box B = [a1 , b1 ] × . . . [ad , bd ], the query procedure first decomposes [a1 , b1 ] into O(log n) canonical subsets in the top-level tree. Then it recursively processes the trees associated with these nodes, moving to x2 , then to x3 , and so on, until it reaches the bottom level, which is a BST ordered according to the last coordinate xd . We note that this last structure can equivalently be represented as a sorted array. At each of the first d − 1 dimensions, the query interval can be decomposed into at most 2⌈log2 n⌉ canonical subsets. 40

Consequently, at most (2⌈log2 n⌉)d−1 = 2O(d) logd−1 n bottom-level arrays are reached, and they are pairwise disjoint. The last slice [ad , bd ] locates the endpoints ℓ, r of a contiguous sub-interval in each array A (possibly empty), and all the points whose xd coordinate is in A[ℓ, r] are returned. In the counting version, we simply compute the size of each such sub-interval. The recursive procedure visits all these arrays and yields P ∩ B, or its cardinality |P ∩ B|. A d-dimensional range tree can be constructed in O(2O(d) n logd−1 n) time, and, using fractional cascading, supports unweighted counting queries in O(2O(d) logd−1 (n)) time and reporting queries in O(2O(d) logd−1 n + |P ∩ B|) time [3, 27]. Additionally, we observe that, for every array A = (p1 , . . . , ph ), we can preprocess the prefix P sum SA (j) = jk=1 w(pk ) and store it with each entry A[j]. Since the total size of all bottom-level arrays is 2O(d) n logd−1 n, this can be done in 2O(d) n logd−1 n time. Consider now a query box B = [a1 , b1 ] × . . . [ad , bd ]. Let A1 , . . . , As be the bottom-level arrays reached by the recursive procedure on input B, and, for i ∈ [s], denote by (ℓi , ri ) the endpoints located by the slice [ad , bd ] in the array Ai . A linked-list summary of P ∩ B is a doubly linked list containing one node for each nonempty sub-interval Ai [ℓi , ri ]. Each node stores four pointers: two pointers prev and next, respectively to the previous and the next nodes of the list; two pointers first and last, respectively to Ai [ℓi ] and Ai [ri ]. We observe that, since the nonempty sub-intervals are pairwise disjoint, their union is exactly P ∩ B. Claim B.2. In time 2O(d) n logd−1 n one can preprocess a range tree so that, on input an axis-aligned d-dimensional box B, one can return a linked-list summary of P ∩ B in time 2O(d) logd−1 n. Proof. We run the whole recursive query procedure with B as input. Let A1 , . . . , As be the arrays reached at the bottom level. For each i ∈ [s], Ai [ℓi ] and Ai [ri ] can be located in O(1) additional time through fractional cascading. We do not enumerate the points P ∩ B. Rather, for each sub-interval, we determine whether it is nonempty in O(1) time and, if so, we add a corresponding node in the linked list. Since at most 2O(d) logd−1 n arrays are reached, the whole linked-list summary is constructed in 2O(d) logd−1 n time. Claim B.3. Given a linked-list summary of P ∩ B, one can return w(P ∩ B), list P ∩ B, or sample from wB∩P with the guarantees of Theorem B.1. Proof. To compute w(P ∩B), we traverse the linked-list summary and, for each i, add the sub-interval weight w(Ai [ℓi , ri ]) = SAi (ri )−SAi (ℓi )+w(Ai [ℓi ]) to an accumulator WB . At the end of the traversal, we have WB = w(P ∩ B). To list the elements of P ∩ B, we traverse the linked-list summary and, for each node, scan the associated sub-interval from A[ℓi ] to A[ri ]. The delay is O(1) in the worst case: moving to the next element within a sub-interval takes constant time, and when the end of a sub-interval is reached, the pointer to the next node gives direct access to the first element of the next nonempty sub-interval. To sample from wP ∩B P, we traverse the linked-list summary to obtain the weights Wi := w(Ai [ℓi , ri ]) and WB = i Wi , as in the counting version. First, we choose a sub-interval proportionally to its weight. Then, we sample a random value in the cumulative-weight range of that sub-interval and find the point p containing that weight through a binary search. Each point of w(p) Wi P ∩ B is sampled with probability Pr(p) = W · w(p) Wi = WB . The whole procedure takes time B O(2O(d) logd−1 n + log n) = O(logmax(1,d−1) n).

We observe that the sampling procedure of Theorem B.1 does not guarantee constant sampling time. We show next that, by paying an additional logarithmic factor in both the preprocessing and the warm-up time, weighted samples from P ∩ B can be generated in O(1) time. 41

Corollary B.4. Let P be an indexed family of n points in Rd≥1 , and let w : P → N be a weight function. There exists a data structure that can be constructed from P in 2O(d) n logd n time and, on input an axis-aligned d-dimensional box B, supports weighted sampling from P ∩ B in warm-up time 2O(d) logd n and, thereafter, O(1) time per sample. Proof. We start by constructing a d−dimensional range tree on P , as in Theorem B.1. Let T be the set of all trees at P the bottom level. For every T ∈ T , and for every node v ∈ T , we precompute (bottom-up) W (v) = v′ ∈P (v) w(v ′ ), that is, the sum of the weights of all the points in its canonical subset P (v). For each node such that W (v) > 0, we also construct an alias table for the points in P (v) (this can be done in O(|P (v)|) time). SincePevery point occurs in at most 1 + ⌈log n⌉ canonical subsets at each of the first d − 1 levels, we have T ∈T |T | ≤ n(1 + ⌈log n⌉)d−1 = O(2O(d) n logd−1 n); furthermore, within each bottom-level tree, every point occurs in at most 1 + ⌈log n⌉ alias tables. Hence, the total size of all alias tables is 2O(d) n logd n, and the whole preprocessing takes time 2O(d) n logd n. Consider now a query box B = [a1 , b1 ] × · · · × [ad , bd ]. We run the standard query procedure on the range tree until the bottom level. At most 2O(d) logd−1 n bottom-level trees are reached. In each of them, the interval [ad , bd ] is decomposed into at most 2⌈log n⌉ canonical subsets. The total number of canonical subsets in all trees is, therefore, q := 2O(d) logd n. We observe that they are pairwise disjoint and their union is exactly P ∩ B. Let v1 , . .P . , vq be the nodes representing these canonical subsets. In the warm-up phase, we compute WB = qi=1 W (vi ) and create a second alias table on the vi , so that Pr(vi ) = WW(vBi ) . This can be done in 2O(d) logd n time. Note that P P P P WB = qi=1 W (vi ) = qi=1 p∈P (vi ) w(p) = p∈P ∩B w(p). To sample from wP ∩B , we first sample a node vi with probability proportional to its weight W (vi ) using the second alias table. Then, we sample a point p from P (vi ) using the precomputed alias table. w(p) Both operations take O(1) time. It holds Pr(p) = WW(vBi ) · Ww(p) (vi ) = WB for every p ∈ P ∩ B.

C

Results on Stabbing

Let B be a family of N axis-parallel boxes in Rd , and let w : B → N be aP weight function. For a point q ∈ Rd , define B(q) = {B ∈ B : q ∈ B}. For any B ′ ⊆ B, let w(B ′ ) = B∈B′ w(B). Definition C.1. Given a family B of axis-parallel boxes in Rd and a weight function w : B → N, a weighted stabbing query with q ∈ Rd asks to: • compute w(B(q)) (counting), • list the elements of B(q) (reporting),   w(B) • sample from the distribution w(B(q))

B∈B(q)

(sampling).

It is the weighted version of a classical problem in computational geometry, see for instance [27, Section 10.4] and [20, Section 1]. With an approach similar to the one of Section B, we can adapt classical stabbing techniques to solve these three versions of the weighted variant. Ultimately, we prove the following theorem. Theorem C.2. For any family of axis-parallel boxes B = {B1 , . . . , BN } in Rd and weight function w : B → N, in time 2O(d) N logd N one can build a data structure that, given q ∈ Rd , supports the following operations: • return w(B(q)) in time 2O(d) logd N , 42

• list B(q) with O(1) delay after an initial warm-up time of 2O(d) logd N ,   w(B) in time 2O(d) logd N . • sample from the distribution w(B(q)) B∈B(q)

Moreover, for counting only, a log N factor can be removed from both preprocessing and query. We recall the definition of weighted union stabbing introduced in Section 5.2.1. Definition C.3. Let P be a family of intervals over [n], let Q be a family of intervals over [m], and let ω : [m] → N be a weighting of [m]. A weighted union stabbing query with q ∈ [n] asks to: • return ω(U (q)) (counting), • list the elements of U (q) (reporting),   ω(u) • sample from the distribution ω(U (q))

u∈U (q)

(sampling).

We prove that there exists a data structure that supports these three operations efficiently on any weighted union stabbing instance. Theorem C.4. For any family of intervals P = {P1 , . . . , PN }, Q = {Q1 , . . . , QN } over [n] and [m] respectively, and ω : [m] → N, there exists a data structure that can be built in time O(n+m+N log m) and, on input q ∈ [n], supports the following operations: • return ω(U (q)) in time O(1). • list U (q) in total time O(|U (q)| log m) and with O(log m) delay.   ω(u) • sample from the distribution ω(U in time O(log m). (q)) u∈U (q)

The rest of the section is organized as follows. In Section C.1 we recall how a segment tree works, this is the standard structure to answer stabbing queries. Then, in Section C.2 and Section C.3 we show how to modify this structure in order to support efficient weighted stabbing and weighted union stabbing query, effectively proving Theorem C.2 and Theorem C.4.

C.1

Segment tree

In this section, we briefly recall how multidimensional segment trees work. Let us first recall how one-dimensional segment trees work. Let I be a family of N intervals over R. By standard coordinate compression, we reduce it to a problem in the discrete domain [n], with n = O(N ), in time O(N log N ). A segment tree Tn is a balanced binary tree where each node x is associated with an interval Jx ⊆ [n]. The root represents [n]. A node x with interval Jx = [a, b] is internal if a < b, in which case its left child has interval [a, ⌊ a+b 2 ⌋] and its right child has interval a+b [⌊ 2 ⌋ + 1, b]. Each node keeps pointers to its children (if any). Leaves have singleton intervals {p}, with p ∈ [n]. Hence Tn has O(n) nodes and height O(log n). Each interval I ∈ I is stored at its canonical nodes, namely the nodes x such that Jx ⊆ I and either x is the root or Jx′ ̸⊆ I, where x′ is the parent of x. We denote this set by Can(I). The intervals associated with the nodes in Can(I) form a partition of I, and |Can(I)| = O(log n). Thus, every input interval is stored at O(log n) nodes. Given q ∈ [n], the stabbing query follows the root-to-leaf path corresponding to q and returns the intervals stored at the visited nodes. The query thus visits O(log n) nodes and

43

retrieves O(log n) pairwise disjoint lists whose union is exactly I(q). The segment tree, including the lists of stored intervals, can be built in O(N log N ) space and time. Now let B = {B1 , . . . , BN } be a family of axis-aligned boxes in Rd , where Bi = Ii,1 ×· · ·×Ii,d . A ddimensional segment tree storing B is defined recursively as follows. First, a one-dimensional segment tree over the first coordinate is built, where each box Bi is assigned to Can(Ii,1 ). Recursively, at step j, every node x of a segment tree on the j-th coordinate stores an associated (d − j)-dimensional segment tree built on Bi′ = Ii,j+1 × · · · × Ii,d for each box Bi assigned to x. Again, by standard coordinate compression, the tree can be built in 2O(d) N logd N time. Let q = (q1 , . . . , qd ) ∈ Rd be a query point, the query procedure follows the root-to-leaf path of q1 on the top-level segment tree, and recursively does the same thing on the next coordinate for each tree associated to the visited nodes. Intuitively, after processing the first j coordinates, the visited structures represent exactly the boxes Bi such that (q1 , . . . , qj ) ∈ Ii,1 × · · · × Ii,j . Since a box can appear at most once in every root-to-leaf path, when the procedure reaches the bottom level, the lists contain disjoint elements and their union is exactly B(q). Since O(log n) nodes are visited in each path, at most 2O(d) logd N bottom-level lists are reached. We summarize all these standard facts in the next remark. Remark C.5. Let B = {B1 , . . . , BN } be a family of axis-aligned boxes in Rd . A d-dimensional segment tree storing B can be built in time and space 2O(d) N logd N . Given q ∈ Rd , the tree identifies at most 2O(d) logd N pairwise disjoint lists whose union is exactly B(q), in time 2O(d) logd N . In the next section, we show a simple way to adapt this standard structure in order to support counting, listing and sampling weighted stabbing queries.

C.2

Proof of Theorem C.2

Let T (B, ω) be the d-dimensional segment tree containing B. Remark C.5 reminds us that this can be done in time 2O(d) N logd N . We claim that, by spending additional 2O(d) N logd N time in the preprocessing phase, T (B, ω) is able to answer weighted stabbing queries within the claimed bounds. The proof is organized as follows: we first exhibit the preprocessing procedure and then prove that the newly obtained structure can efficiently answer to stabbing queries. Preprocessing. Let Lx be a bottom-level list associated with a node x. Recall that, by construction, Lx stores the boxes Bi1 , . . . , Bij assigned to x. For each bottom-level list Lx , we store ω(Lx ) = P O(d) N logd N time. Indeed, by Remark C.5, B∈Lx ω(B) and its prefix sums. This can be done in 2 the entire structure, including all bottom-level lists, has size 2O(d) N logd N . Thus, a single traversal of these lists is sufficient to compute both their total weights and prefix sums within the claimed time. Query. We prove the claimed bounds for each query type. • counting: query T (B, ω) on q and retrieve lists L1 , . . . , Lk . Computing and returning Pk ω(L ) is sufficient to answer the query. Indeed, by Remark C.5, the lists are pairi i=1 P wise disjoint and their union is exactly B(q). Thus, ki=1 ω(Li ) = ω(B(q)). The same remark guarantees that these lists are retrieved in time 2O(d) logd N . • reporting: query T (B, ω) on q and retrieve all non-empty lists L1 , . . . , Lk . Build a linked list over L1 , . . . , Lk , then scan this list and output each element. Correctness follows from Remark C.5, since the union of these non-empty lists is exactly B(q), and they are pairwise disjoint. Moreover, the warm-up phase takes 2O(d) logd N time, since retrieving and linking the non-empty lists takes the same asymptotic time as querying T (B, ω). Once the linked list is constructed, each element can be reported with O(1) delay. 44

• sampling: query T (B, ω) on q and retrieve the lists L1 , . . . , Lk . Choose a list Li with probability ω(B ) ω(Li ) Pk . Then, sample a box Bj ∈ Li with probability ω(Lji ) . Again, from Remark C.5 j=1 ω(Lj )

we have that L1 ⊎ · · · ⊎ Lk = B(q), thus the probability of sampling Bj ∈ Li is Pr(Bj ) = ω(B ) ω(Bj ) ω(Li ) Pk · ω(Lji ) = ω(B(q)) . Moreover, retrieving the lists takes 2O(d) logd N time, choosing a h=1 ω(Lh )

list takes O(k) time, and sampling a box within the chosen list takes O(log N ) time by binary search on its prefix sums. Since k ≤ 2O(d) logd N , the total query time is 2O(d) logd N . For counting, both preprocessing and query time can be improved by a factor of log N . In the two-dimensional case, we replace the second-dimensional segment tree associated with each node of the first-dimensional segment tree with a sorted list of signed interval endpoints, augmented with prefix sums of weights. For each box Bi = [a, b] × [c, d] assigned to a node x, we insert events (c, +ω(Bi )) and (d, −ω(Bi )) into the list associated with x, breaking ties so that starting events precede queries and ending events follow them. Each box contributes to O(log N ) such lists, which can be constructed in O(N log N ) total time by sorting the endpoints once. Fractional cascading then allows us to perform all predecessor searches along a first-dimensional segment-tree path in O(log N ) total time, and the answer is obtained by summing the corresponding prefix sums. Applying this construction to the last two dimensions of the multidimensional segment tree yields preprocessing time 2O(d) N logd−1 N and query time 2O(d) logd−1 N , for d ≥ 2.

C.3

Proof of Theorem 5.9

x the subtree rooted at a node x. Moreover, for Let Tm be a segment tree over [m], and denote by Tm every node x, store the weight [  x µ(x) = ω {Jy : y ∈ Tm ∩ Can(Q)} . (30)

We call the resulting structure a union segment tree, and denote it by Tµ (Q, ω). Thus, µ(x) is the total weight covered by the canonical nodes in the subtree rooted at x. This is essentially the weighted version of the structure used by Bentley to solve Klee’s measure problem, which asks for the area of the union of axis-parallel rectangles ([54, Section 8.4]). Indeed, Bentley’s algorithm can be adapted to answer counting union stabbing queries. We show that, by using the standard technique of path copying, the same structure can also support listing and sampling queries. We first show how to answer these queries on a union segment tree for a fixed family Q. Then, we use path copying to obtain a persistent structure supporting all three query types for any q ∈ [n]. C.3.1

Querying the union tree

Let Tµ (Q, ω) be the union segment tree over (Q, ω). Recall that Can(Q) contains all canonical nodes of the intervals in Q. Although their intervals cover Q∪ , they may overlap. We say that a node x is a high canonical node if x ∈ Can(Q) and no proper ancestor of x belongs to Can(Q). In other words, high canonical nodes are the first canonical nodes encountered when descending from the root. We show that their intervals partition Q∪ , and that µ(x) gives the weight covered within Jx whenever no canonical node has been encountered above x. Claim C.6. Let F be the set of high canonical nodes of Tµ (Q, ω). Then the intervals {Jx : x ∈ F } form a partition of Q∪ . Moreover, for every node x having no proper ancestor in Can(Q) X µ(x) = ω(Jx ∩ Q∪ ) = ω(Jy ). (31) x y∈F ∩Tm

45

S Proof. By definition, Q∪ = y∈Can(Q) Jy . Every canonical node has a highest canonical ancestor, S which belongs to F , thus Q∪ = y∈F Jy . Moreover, byU definition of F , two distinct nodes of F cannot appear on the same path, and therefore Q∪ = y∈F Jy . This proves the first part of the claim. Now let x have no proper ancestor in Can(Q).S Then every canonical node intersecting Jx must appear in Tµx (Q, ω), therefore Jx ∩ Q∪ = y∈Can(Q)∩Tmx Jy and consequently µ(x) =
S ω y∈Can(Q)∩Tmx Jy = ω(Jx ∩ Q∪ ). Finally, since the intervals of the nodes in F partition Q∪ , we P obtain ω(Jx ∩ Q∪ ) = y∈F ∩Tmx ω(Jy ). Claim C.6 allows us to traverse Q∪ by descending from the root, skipping subtrees of weight zero and stopping at the first canonical node of each branch. Indeed, these are exactly the high canonical nodes, whose intervals partition Q∪ . Moreover, at every node visited before stopping, µ(x) gives the weight of the portion of Jx covered by Q∪ , which we exploit for counting and sampling. Claim C.7. Given the root r of Tµ (Q, ω), one can: 1. return ω(Q∪ ) in time O(1), 2. list Q∪ in total time O(|Q∪ | · log m) and O(log m) delay,   ω(u) in time O(log m). 3. sample from the distribution ω(Q ∪) ∪ u∈Q

Proof. For each of the three query types, we first introduce the procedure and then show that it is correct and runs within the claimed bounds. Counting. By Claim C.6, µ(r) = ω(Jr ∩ Q∪ ) = ω(Q∪ ) since Jr = [m]. Thus, it suffices to return µ(r). This can be done in O(1) time. Listing. Starting from the root, recursively visit a node as follows: if µ(x) = 0 return. If x ∈ Can(Q), then list all the elements of Jx ; otherwise, recurse on its children. The procedure stops at the first canonical node of each branch, thus visiting exactly the high canonical nodes of positive weight. By Claim C.6, these intervals partition Q∪ , thus every element of Q∪ is listed exactly once. Since the tree has height O(log m) and |F | ≤ |Q∪ |, the total running time is O(|Q∪ | log m). Finally, between two consecutive outputs, the traversal visits at most O(log m) nodes, yielding O(log m) delay. Sampling. If µ(r) = 0, report Q∪ = ∅. Otherwise, start at x = r and, while x ∈ / Can(Q), move to its left child xl with probability µ(xl )/µ(x), and to its right child xr otherwise. Once a canonical node y is reached, sample an element u ∈ Jy with probability ω(u)/ω(Jy ), using the prefix sums. Let y be the selected node, by Claim C.6 every encountered node x before y satisfies µ(x) = µ(xl ) + µ(xr ). ω(Jy ) Hence, the probability of reaching y telescopes to Pr[y] = µ(y) µ(r) = ω(Q∪ ) . Consequently, every u ∈ Jy is sampled with probability Pr[u] = Pr[y] · Pr[u | y] =

ω(Jy ) ω(u) ω(u) · = . ∪ ω(Q ) ω(Jy ) ω(Q∪ )

Since F partitions Q∪ , this is the required distribution. Finally, the procedure is a single traversal of a root-to-leaf path, and thus takes time at most O(log m). Let x be a visited node, computing the probability of the next nodes takes O(1) time. Finally, with a simple binary search Step 3 requires O(log m) time. Hence, O(log m) total time.

46

C.3.2

Making the tree persistent

Claim C.8. Given a weighted union-stabbing instance (P, Q, ω), one can construct in time O(n + m + N log m) an implicit representation of {Tµ (Q(q), ω), q ∈ [n]} such that the root of each tree can be accessed in O(1) time. Moreover, for every node x of Tµ (Q(q), ω), membership in Can(Q(q)) can be tested in O(1) time. Proof. The proof is organized as follows: we introduce the data structure in the first three paragraphs. Then, we prove its correctness and bounds. Construction. Build a segment tree Tm on [m], with every node x storing two integers, namely C(x) and µ̂(x), both initially set to zero. We also preprocess the prefix sums of ω, so that ω(Jx ) can be computed in O(1) time for every node x Update. We define a procedure Update(x, I, δ), where x is a node, I ⊆ [m] is an interval, and δ ∈ {−1, +1} indicates insertion or removal. If Jx ∩ I = ∅, the procedure returns x unchanged. Otherwise, it creates a copy x′ of x, initially retaining its children. If Jx ⊆ I, it sets C(x′ ) ← C(x)+δ; otherwise, it recursively updates the children of x′ using Update(xl , I, δ) and Update(xr , I, δ). Finally, it sets   if C(x′ ) > 0, ω(Jx ) µ̂(x′ ) = 0 (32) if C(x′ ) = 0 and x′ is a leaf,   ′ ′ µ̂(xl ) + µ̂(xr ) otherwise, and returns x′ . Thus, Update(x, I, +1) and Update(x, I, −1) implement insertion and removal, respectively, while preserving all previous versions of the tree. Sweep. For every i ∈ [N ], let Pi = [ai , bi ], create an insertion event of (Qi , +1) at ai and, if bi < n, a removal event (Qi , −1) at bi + 1. We group the events by position with a bucket sort on [n]. Let r0 be the root of Tm . For q = 1, . . . , n, set rq ← rq−1 , and then rq ← Update(rq , I, δ) for every event (I, δ). Finally, output r1 , . . . , rn . Correctness. Let q ∈ [n]. The root rq can be accessed in O(1) time, and every node x reachable from rq is either a node of Tm or a copy of one, with the same interval Jx , whose children are reached through the pointers. Let x be a node reachable from rq . We first show that x ∈ Can(Q(q)) can be checked by testing C(x) > 0. Indeed note that, by definition, each insertion or removal changes the counter by δ exactly at the canonical nodes of the corresponding interval. Thus, since after the events at positions 1, . . . , q the intervals inserted are exactly those in Q(q), the following equality holds (33)

C(x) = |{j ∈ [N ] : q ∈ Pj , x ∈ Can(Qj )}|.

In words, C(x) counts how many inserted intervals have x as a canonical node. Thus, C(x) > 0 if and only if x ∈ Can(Q(q)), giving the claimed constant time membership test. It remains to show that, for every x reachable from rq , the value stored in x is its label in Tm (Q, ω); that is, µ̂(x) = µ(x). By construction, every node x satisfies µ̂(x) = ω(Jx ) if C(x) > 0, µ̂(x) = 0 if C(x) = 0 and x is a leaf, and µ̂(x) = µ̂(xl ) + µ̂(xr ). By definition, µ satisfies the same recursion with x ∈ Can(Q(q)) in place of C(x) > 0. Indeed, if x ∈ Can(Q(q)), then µ(x) = ω(Jx ), x ; if x ∈ since Jx itself appears in the union defining µ(x) and Jy ⊆ Jx for every y ∈ Tm / Can(Q(q)) is a leaf, then the union is empty and µ(x) = 0; if x ∈ / Can(Q(q)) is internal, then every canonical x lies in T xl or in T xr , whose intervals are contained in the disjoint sets J and J , hence node of Tm xl xr m m 47

µ(x) = µ(xl ) + µ(xr ). Since C(x) > 0 if and only if x ∈ Can(Q(q)), by induction on the height of x we conclude that µ̂(x) = µ(x) for every x reachable from rq . Thus, the tree rooted at rq is a representation of Tµ (Q(q), ω). Time complexity. Building Tm on [m] requires O(m) time, while constructing and grouping the events take O(n + N ) time with a bucket sort on [n]. Each update visits O(log m) nodes, as in the standard segment tree insertion procedure (see Section C.1), and performs O(1) work per visited node. Since there are at most 2N events, the total update time is O(N log m). Moreover, each update creates O(log m) nodes, each storing O(1) information. Together with the initial tree, the prefix sums, and the n stored roots, this gives O(n + m + N log m) total time and space.

48

References [1] Amir Abboud, Virginia Vassilevska Williams, and Joshua Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 377–391. [2] Pankaj K. Agarwal, Lars Arge, Haim Kaplan, Eyal Molad, Robert Endre Tarjan, and Ke Yi. An optimal dynamic data structure for stabbing-semigroup queries. SIAM J. Comput., 41:104–127, 2012. [3] Pankaj K. Agarwal and Jeff Erickson. Geometric range searching and its relatives. In Advances in Discrete and Computational Geometry, volume 223 of Contemporary Mathematics, pages 1–56. American Mathematical Society, 1999. [4] Nesreen K. Ahmed, Jennifer Neville, Ryan A. Rossi, and Nick G. Duffield. Efficient graphlet counting for large networks. In 2015 IEEE International Conference on Data Mining (ICDM), pages 1–10. IEEE Computer Society, 2015. [5] Jungho Ahn, Debsoumya Chakraborti, Kevin Hendrey, and Sang-il Oum. Twin-width of subdivisions of multigraphs. SIAM Journal on Discrete Mathematics, 39(2):783–833, 2025. [6] Sinan G. Aksoy, Cliff A. Joslyn, Carlos Ortiz Marrero, Brenda Praggastis, and Emilie Purvine. Hypernetwork science via high-order hypergraph walks. EPJ Data Science, 9(1):16, 2020. [7] Josh Alman and Virginia Vassilevska Williams. Truly subquadratic 3SUM and truly subcubic APSP via triangles in sparse lopsided graphs, 2026. arXiv:2610.06783. [8] Alexandr Andoni, Shunhua Jiang, and Omri Weinstein. A framework for building data structures from communication protocols. In Proc., ACM Symposium on Theory of Computing (STOC), pages 256–267, 2025. [9] Alessia Antelmi, Gennaro Cordasco, Mirko Polato, Vittorio Scarano, Carmine Spagnuolo, and Dingqi Yang. A survey on hypergraph representation learning. ACM Comput. Surv., 56(1), 2023. [10] Alexis Baudin, Clémence Magnien, and Lionel Tabourier. BBK: A simpler, faster algorithm for enumerating maximal bicliques in large sparse bipartite graphs, 2024. arXiv:2405.04428. [11] Austin R. Benson, Rediet Abebe, Michael T. Schaub, Ali Jadbabaie, and Jon Kleinberg. Simplicial closure and higher-order link prediction. Proceedings of the National Academy of Sciences, 115(48):E11221–E11230, 2018. [12] Suman K. Bera, Lior Gishboliner, Yevgeny Levanzov, C. Seshadhri, and Asaf Shapira. Counting subgraphs in degenerate graphs. Journal of the ACM (JACM), 69(3), 2022. [13] Suman K. Bera, Noujan Pashanasangi, and C. Seshadhri. Near-linear time homomorphism counting in bounded degeneracy graphs: The barrier of long induced cycles. In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2315–2332, 2021. [14] Marco Bressan. Faster subgraph counting in sparse graphs. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. 49

[15] Marco Bressan. Faster algorithms for counting subgraphs in sparse graphs. Algorithmica, 83:2578–2605, 2021. [16] Marco Bressan, Julian Brinkmann, Holger Dell, Marc Roth, and Philip Wellnitz. The parameterised complexity of counting small sub-hypergraphs. In Proc., ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2002–2014, 2026. [17] Marco Bressan, Stefano Clemente, and Giacomo Fumagalli. Counting HyperGraphlets via color coding: a quadratic barrier and how to break it. Proc. VLDB Endow., 19(9):2073–2085, August 2026. [18] Ümit Çatalyürek, Karen Devine, Marcelo Faraj, Lars Gottesbüren, Tobias Heuer, Henning Meyerhenke, Peter Sanders, Sebastian Schlag, Christian Schulz, Daniel Seemaier, and Dorothea Wagner. More recent advances in (hyper)graph partitioning. ACM Comput. Surv., 55(12), 2023. [19] Moses Charikar, Piotr Indyk, and Rina Panigrahy. New algorithms for subset query, partial match, orthogonal range searching, and related problems. In Proc., International Colloquium on Automata, Languages and Programming (ICALP), volume 2380, pages 451–462, 2002. [20] Bernard Chazelle. Filtering search: A new approach to query-answering. In 24th Annual Symposium on Foundations of Computer Science (sfcs 1983), pages 122–132, Nov 1983. [21] Lu Chen, Chengfei Liu, Rui Zhou, Jiajie Xu, and Jianxin Li. Efficient exact algorithms for maximum balanced biclique search in bipartite graphs. In Proceedings of the 2021 International Conference on Management of Data, pages 248–260, 2021. [22] Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM Journal on Computing (SICOMP), 14(1):210–223, 1985. [23] Jaewan Chun, Geon Lee, Kijung Shin, and Jinhong Jung. Random walk with restart on hypergraphs: fast computation and an application to anomaly detection. Data Min. Knowl. Discov., 38(3):1222–1257, 2024. [24] Jonathan Cohen. Graph twiddling in a mapreduce world. Computing in Science & Engineering, 11(4):29, 2009. [25] Richard Cole, Lee-Ad Gottlieb, and Moshe Lewenstein. Dictionary matching and indexing with errors and don’t cares. In Proc., ACM Symposium on Theory of Computing (STOC), pages 91–100, 2004. [26] B. Courcelle and R. Vanicat. Query efficient implementation of graphs of bounded clique-width. Discrete Applied Mathematics, 131(1):129–150, 2003. [27] Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer, Berlin, Heidelberg, third edition, 2008. [28] David Eppstein. Arboricity and bipartite subgraph listing algorithms. Information Processing Letters, 51(4):207–211, 1994. [29] Paul W. Goldberg, Martin C. Golumbic, Haim Kaplan, and Ron Shamir. Four strikes against physical mapping of DNA. Journal of Computational Biology, 2(1):139–152, 1995.

50

[30] Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, and Ely Porat. Conditional lower bounds for space/time tradeoffs. In Algorithms and Data Structures, pages 421–436, Cham, 2017. Springer International Publishing. [31] Shweta Jain and C Seshadhri. A fast and provable method for estimating clique counts using Turán’s theorem. In Proceedings, International World Wide Web Conference (WWW), pages 441–449, 2017. [32] T.S. Jayram, Subhash Khot, Ravi Kumar, and Yuval Rabani. Cell-probe lower bounds for the partial match problem. Journal of Computer and System Sciences, 69(3):435–447, 2004. [33] Madhav Jha, C Seshadhri, and Ali Pinar. Path sampling: A fast and provable method for estimating 4-vertex subgraph counts. In Proc. 24th International World Wide Web Conference (WWW), pages 495–505. International World Wide Web Conferences Steering Committee, 2015. [34] Geon Lee, Fanchen Bu, Tina Eliassi-Rad, and Kijung Shin. A survey on hypergraph mining: Patterns, tools, and generators. ACM Comput. Surv., 57(8), 2025. [35] Geon Lee, Minyoung Choe, and Kijung Shin. How do hyperedges overlap in real-world hypergraphs? - patterns, measures, and generators. In Proc., International World Wide Web Conference (WWW), pages 3396–3407, 2021. [36] Geon Lee, Jihoon Ko, and Kijung Shin. Hypergraph motifs: Concepts, algorithms, and discoveries. Proceedings of the VLDB Endowment, 13(12):2256–2269, July 2020. [37] Geon Lee, Seokbum Yoon, Jihoon Ko, Hyunju Kim, and Kijung Shin. Hypergraph motifs and their extensions beyond binary. The VLDB Journal, 33(3):625–665, May 2024. [38] Jongshin Lee, Kwang-Il Goh, Deok-Sun Lee, and B. Kahng. (k,q)-core decomposition of hypergraphs. Chaos, Solitons & Fractals, 173:113645, 2023. [39] Xu T. Liu, Jesun Firoz, Sinan G. Aksoy, Ilya Amburg, Andrew Lumsdaine, Cliff A. Joslyn, Brenda Praggastis, and Assefaw H. Gebremedhin. High-order line graphs of non-uniform hypergraphs: Algorithms, applications, and experimental analysis. In International Parallel and Distributed Processing Symposium, pages 784–794, 2022. [40] Quintino Francesco Lotito, Martina Contisciani, Caterina De Bacco, Leonardo Di Gaetano, Luca Gallo, Alberto Montresor, Federico Musciotto, Nicolò Ruggeri, and Federico Battiston. Hypergraphx: a library for higher-order network analysis. Journal of Complex Networks, 11(3):cnad019, 2023. [41] David W Matula and Leland L Beck. Smallest-last ordering and clustering and graph coloring algorithms. Journal of the ACM (JACM), 30(3):417–427, 1983. [42] Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson. On data structures and asymmetric communication complexity. In Proc., ACM Symposium on Theory of Computing (STOC), pages 103–111, 1995. [43] C. St. J. A. Nash-Williams. Decomposition of finite graphs into forests. Journal of the London Mathematical Society, 39(1):12, 1964. [44] OpenAI. The Exponential Time Hypothesis is false. https://github.com/openai/math/ blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/ paper.pdf, October 2026. 51

[45] Mark Ortmann and Ulrik Brandes. Efficient orbit-aware triad and quad census in directed and undirected graphs. Applied Network Science, 2(1), 2017. [46] Noujan Pashanasangi and C Seshadhri. Efficiently counting vertex orbits of all 5-vertex subgraphs, by EVOKE. In Proc. 13th International Conference on Web Search and Data Mining (WSDM), pages 447–455, 2020. [47] Mihai Pătraşcu. Towards polynomial lower bounds for dynamic problems. In Proc. 42nd Annual ACM Symposium on the Theory of Computing, 2010. [48] Mihai Pătraşcu. Unifying the landscape of cell-probe lower bounds. SIAM Journal on Computing (SICOMP), 40(3):827–847, 2011. [49] Daniel Paul-Pena and C. Seshadhri. A dichotomy hierarchy for linear time subgraph counting in bounded degeneracy graphs. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 48–87, 2025. [50] Daniel Paul-Pena and C. Seshadhri. Near-linear time subhypergraph counting in bounded degeneracy hypergraphs. In Proc., ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3652–3687, 2026. [51] Daniel Paul-Pena, Vaishali Surianarayanan, Deeparnab Chakrabarty, and C. Seshadhri. Counting hypertriangles through hypergraph orientations, January 2026. arXiv:2601.03573. [52] Ali Pinar, C Seshadhri, and Vaidyanathan Vishal. ESCAPE: Efficiently counting all 5-vertex subgraphs. In Proceedings, International World Wide Web Conference (WWW), pages 1431–1440, 2017. [53] Brenda Praggastis, Sinan Aksoy, Dustin Arendt, Mark Bonicillo, Cliff Joslyn, Emilie Purvine, Madelyn Shapiro, and Ji Young Yun. HyperNetX: A python package for modeling complex network data as hypergraphs. Journal of Open Source Software, 9(95):6016, 2024. [54] Franco P Preparata and Michael I Shamos. Computational geometry: an introduction. Springer Science & Business Media, 2012. [55] R. Rivest. Partial match retrieval algorithms. SIAM Journal on Computing (SICOMP), 5(1):19–50, 1976. [56] Nicole Schweikardt, Luc Segoufin, and Alexandre Vigny. Enumeration for FO queries over nowhere dense graphs. J. ACM, 69(3), June 2022. [57] C. Seshadhri. Some vignettes on subgraph counting using graph orientations. In Proceedings of the International Conference on Database Theory (ICDT), pages 3:1–3:10, 2023. [58] Julian Shun. Practical parallel hypergraph algorithms. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 232–249, 2020. [59] Tak Wah Lam and Ka Hing Lee. An improved scheme for set equality testing and updating. Theoretical Computer Science, 201(1):85–97, 1998. [60] Szymon Toruńczyk. Aggregate queries on sparse databases. In Dan Suciu, Yufei Tao, and Zhewei Wei, editors, Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, Portland, OR, USA, June 14-19, 2020, pages 427–443. ACM, 2020. 52

[61] Nate Veldt, Austin R. Benson, and Jon Kleinberg. Minimizing localized ratio cut objectives in hypergraphs. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1708–1718, 2020. [62] Nate Veldt, Austin R. Benson, and Jon Kleinberg. Hypergraph cuts with general splitting functions. SIAM Review, 64(3):650–685, 2022. [63] Haozhe Yin, Kai Wang, Wenjie Zhang, Ying Zhang, Ruijia Wu, and Xuemin Lin. Efficient computation of hyper-triangles on hypergraphs. Proceedings of the VLDB Endowment, 18(3):729– 742, 2024.

53

Related documents

• Graph Homomorphisms and Universal Algebra#1109003
• Arboricity games: the core and the nucleolus#1537054
• Hypergraphs with the smallest Hall ratio are still hard to colour#1355480
• An Error Taxonomy for Property Graph Data#1387371
• An Error Taxonomy for Property Graph Data#1375122