Scalable Approximate Algorithm for Dynamic Densest Subhypergraphs with Solution-Guided Maintenance

Scalable Approximate Algorithm for Dynamic Densest Subhypergraphs with Solution-Guided Maintenance Jingbang Chen∗

Chenhao Ma

Yingli Zhou

CUHK-Shenzhen & SLAI Shenzhen, China

CUHK-Shenzhen Shenzhen, China

CUHK-Shenzhen Shenzhen, China

arXiv:2609.39778v1 [cs.DB] 30 Sep 2026

Abstract Hypergraphs model interactions involving groups of entities, and finding highly connected groups is a fundamental task in analyzing these data. When interactions arrive and expire, maintaining a dense group can require frequent and expensive changes to the underlying representation. We propose CAP, a scalable algorithm that explicitly maintains a (1 + 𝜖)-approximate densest subhypergraph under hyperedge insertions and deletions. The algorithm keeps a solution candidate together with an endpoint allocation that bounds the optimum density. The candidate’s density guides maintenance: an update triggers repair only when this bound is too large to establish the required approximation. Local searches redistribute load or find a denser candidate, allowing CAP to retain useful solutions across many updates. We give an analysis that relates maintenance work to the size of the regions searched and the density lost by the maintained solution. It identifies conditions under which local repair remains inexpensive and provides a theoretical explanation for the observed efficiency. Experiments on real-world hypergraphs show speedups of up to nearly four orders of magnitude over the evaluated dynamic baselines, while supporting frequent queries and high accuracy. CAP also remains competitive with specialized dynamic graph methods on ordinary graphs, with speedups of up to approximately 64× on the tested workloads.

CCS Concepts • Information systems → Data mining; • Theory of computation → Dynamic graph algorithms.

Keywords dynamic hypergraphs, densest subgraph, incremental maintenance, approximation certificates

1

Introduction

A hypergraph represents relationships among groups of entities: its vertices are entities, and each hyperedge connects all participants in one interaction. Unlike an ordinary graph edge, a hyperedge can contain more than two vertices. This representation occurs naturally in scientific collaboration, where a paper joins its coauthors, and in online activity, where an event associates a group of users or tags [6]. Hypergraphs also model protein complexes [35] and support learning from relationships among multiple objects [25]. Keeping each group interaction intact preserves information that a collection of pairwise links can lose, making hypergraphs a useful model across social, biological, and information systems [4]. A central task in such systems is to find a densely connected group. In an ordinary graph, the densest-subgraph problem seeks a ∗ Corresponding author.

set of vertices with the largest ratio of edges inside the set to the number of vertices in it. This simple objective balances the number of interactions captured against the size of the group. Densestsubgraph methods and their variants are used to identify communities [17], detect coordinated or anomalous activity [31], and identify regulatory motifs and gene-annotation patterns [26, 36, 46]. The corresponding hypergraph problem counts hyperedges whose endpoints all belong to the selected set. It finds groups participating in many complete interactions, rather than merely many pairwise connections. Algorithms for this objective include peeling, flow, and localized methods [5, 16, 33]. In temporal data, however, interactions are continually added and removed, so the dense group must be maintained as the hypergraph changes. This dynamic setting has motivated algorithms for evolving hypergraphs [7, 32]. Existing dynamic approaches maintain degree decompositions, orientations, or endpoint allocations whose local conditions imply an approximation guarantee. Hu et al. [32] give guarantees depending on hyperedge size; Bera et al. [7] obtain a near-one approximation and provide a practical implementation. Chekuri et al. [15] develop faster dynamic orientation techniques. Their maintenance rules restore local conditions after updates. Our key observation is that an update can violate such a condition while the current solution still satisfies the requested approximation. Retaining useful dense sets already helps ordinary-graph methods avoid some recomputations [21, 55]. For dynamic hypergraphs, we ask how the maintained solution can guide allocation repair while preserving the required approximation after every update. We address this opportunity with CAP, a fully dynamic algorithm for maintaining an explicit approximate densest subhypergraph. It stores a solution candidate and distributes each hyperedge’s contribution among its endpoints. This allocation provides an upper bound on the optimum density, while the candidate provides a lower bound—an established relationship [7, 10]. After an insertion or deletion, CAP updates the affected allocation and the candidate’s density. If the two bounds remain close enough, it keeps the candidate and finishes the update. Otherwise, a local search either moves load to vertices with spare capacity or identifies a denser set to use as the new candidate. The solution is maintained explicitly, so a query can directly return its vertices. Maintenance is solutionguided because the candidate’s current density guides both when repair is needed and when it can stop. We also develop an analysis tailored to this maintenance policy. A bound that charges every update for the whole hypergraph misses the savings from retaining a useful solution and searching only a local region. Our analysis separates the cost of an individual search from the amount of repair caused by changes in solution density. For example, deleting an edge outside the maintained solution does not lower its density and cannot trigger an overload; when

Chen et al.

the solution loses only a small fraction of its internal edges, its allowable load changes only slightly. Together with bounds on the high-load region reached by a search, this explains when the maintenance cost can be small even in a large hypergraph. These conditions provide theoretical support for the strong performance observed in our experiments. Our contributions are summarized as follows. • We propose CAP, a solution-guided algorithm that maintains an explicit (1 + 𝜖)-approximate densest subhypergraph after every insertion or deletion. It supports hyperedges of different sizes and returns the maintained solution directly at queries. • We analyze the work actually performed by local maintenance. The resulting bounds identify small high-load regions and limited decreases in solution density as conditions for inexpensive repair, explaining how the algorithm can benefit from the structure of a stream. • We evaluate CAP against dynamic hypergraph baselines and exact snapshot solvers. It achieves speedups of up to approximately 5.9 × 103 over the dynamic baselines on completed comparisons, with studies of query frequency, data size, accuracy, and its maintenance policy. It also remains competitive with specialized methods on ordinary graphs, reaching speedups of approximately 64×. Outline. Section 2 reviews related work, and Section 3 defines the problem and notation. Section 4 presents CAP and establishes its correctness. Section 5 analyzes solution-guided maintenance, and Section 6 evaluates its efficiency and solution quality. Section 7 concludes the paper.

2

Related Work

Densest-subgraph discovery. Densest-subgraph discovery has a substantial literature spanning theory, database algorithms, and applications, as covered by tutorials, surveys, and comparative studies [22, 27, 36, 40, 62]. Beyond Charikar’s classical greedy 2approximation [14], practical methods use iterative peeling [11], core-based pruning [23, 55], convex optimization [20, 30], spectral methods [24], and parallel computation [41, 48]. Other work studies local algorithms [1], density-friendly decompositions [49], locally densest subgraphs [45, 50, 56], and indexing all densest solutions [13]. Directed densest-subgraph discovery has also received sustained attention, including core-based and convex approaches by Ma et al. [42, 43] and recent algorithms by Zhou et al. and Liang et al. [38, 64]. Variants impose size constraints [2, 34], anchor the solution around specified vertices [19, 65], or measure density through cliques [51, 60, 61]. Clique-based objectives also support locally dense solutions [54, 63]. Densest subhypergraphs. Chekuri et al. [16] study peeling and flow algorithms through supermodular density, which includes fully contained-edge hypergraph density. Huang et al. [33] develop formulations based on negative supermodularity and strongly localized methods, along with exact global solvers. Bengali et al. [5] allow arbitrary monotonic partial-edge rewards and give an exact flow implementation for the convex regime. Our objective is the special case in which only fully contained hyperedges contribute. These static solvers can answer a dynamic query by recomputing

on the current snapshot, but do not reuse the maintained allocation across updates. Dynamic densest subhypergraphs. Hu et al. [32] maintain dense subsets in evolving hypergraphs, with approximation factors 𝑟 (1 + 𝜖) for incremental updates and 𝑟 2 (1 + 𝜖) for fully dynamic updates. Bera et al. [7] obtain a near-one factor independent of hyperedge rank, including weighted hypergraphs, and provide the Udshp implementation. Their algorithms use orientations and local endpointload conditions. A preliminary version of Chekuri et al. [15] discusses a hypergraph extension that reduces update and space costs using compact representations of replicated edges and local labels; it also maintains an implicit vertex-list representation of an approximate dense set. We compare with Udshp and a reconstruction of this hypergraph extension. Leng et al. [37] study hypergraph density decomposition and give algorithms for insertions and deletions. Their maintained object is a hierarchy of integer density layers. CAP instead maintains an explicit approximate global solution and uses its density to control changes to an endpoint allocation. Dynamic densest subgraphs and orientations. For ordinary graphs, Bhattacharya et al. [9] maintain approximate density through hierarchical decompositions, while Epasto et al. [21] retain dense sets to reduce recomputation in evolving graphs. Sawlani and Wang [47] establish a near-one fully dynamic approximation through orientations. The adaptive-orientation results of Chekuri et al. [15] and their engineering study [28] further develop local balance approaches for graphs. Greedy dynamic orientations and their implementations have also been studied [8, 12]. Xu et al. [55] maintain a density-threshold core containing an optimum, using a retained dense set and local tests to avoid some recomputations. A solver can refine that candidate into an exact or approximate answer. Thus, reusing a useful solution is established prior work; our policy uses its density to govern a persistent allocation and maintain a near-one guarantee after every update. Dynamic variants maintain solutions on directed graphs [43], dense regions under edge-weight changes [3], top-𝑘 solutions [44], dense subgraphs in graph collections [52], temporal subgraphs [39], anchored solutions [58], and density decompositions [57]. Exact dynamic orientations use directed searches and can skip changes when the maximum degree remains feasible [29]. Pseudoarboricity maintenance [59] provides another specialized graph baseline. Related static work computes orientations minimizing the maximum indegree [53].

3

Preliminaries

In this section, we introduce the notation and specify the dynamic densest-subhypergraph problem. We then give its linear programming formulation and discuss the allocation bounds and residual paths used in our algorithm.

3.1

Hypergraphs and Density

A hypergraph 𝐺 = (𝑉 , 𝐸) consists of a vertex set 𝑉 and a collection of hyperedges 𝐸. Each hyperedge 𝑒 is a nonempty subset of 𝑉 . Let 𝑛 = |𝑉 | and 𝑚 = |𝐸|. We assume 𝑛 ≥ 1 and fix an upper bound Í 𝑟 ≥ 2 on hyperedge size. The incidence volume is 𝐼 = 𝑒 ∈𝐸 |𝑒 |, and deg(𝑣) is the number of hyperedges containing 𝑣. An ordinary graph is the special case in which every edge has two endpoints

Scalable Approximate Algorithm for Dynamic Densest Subhypergraphs with Solution-Guided Maintenance

(𝑟 = 2). Our model also permits singleton hyperedges and parallel hyperedges. Parallel hyperedges have distinct identifiers and contribute separately to all edge counts. For 𝑆 ⊆ 𝑉 , let 𝐸 (𝑆) = {𝑒 ∈ 𝐸 : 𝑒 ⊆ 𝑆 } be its induced hyperedges. The density of a nonempty set 𝑆 and the optimal density are 𝜌 (𝑆) =

|𝐸 (𝑆)| , |𝑆 |

∑︁

(𝑣 ∈ 𝑉 ),

𝑒 ∋𝑣

Problem Specification

Problem 3.1 (Dynamic densest subhypergraph). Given 0 < 𝜖 ≤ 1, maintain a vertex set 𝐶 after each update such that 𝜌 (𝐶) ≥ 𝜌 ∗ /(1 + 𝜖). A query reports the vertices of 𝐶 and their density. When 𝐸 = ∅, the answer is 𝐶 = ∅. We call the maintained set 𝐶 a witness: its density is an explicit lower bound on the optimum. We write 𝑘 = |𝐶 |, 𝑀 = |𝐸 (𝐶)|, and 𝐿 = 𝜌 (𝐶), so 𝐿 = 𝑀/𝑘 when 𝐶 ≠ ∅ and 𝐿 = 0 when 𝐶 = ∅. The algorithm also maintains an upper bound 𝑈 on 𝜌 ∗ . The condition 𝑈 ≤ (1 +𝜖)𝐿 then certifies the required approximation. The witness is maintained after every update, even when queries occur less frequently. Reporting its vertices costs Θ(1 + 𝑘), including constant time for an empty answer.

Linear Programming Formulation

At a fixed snapshot, the densest-subhypergraph problem has the following linear programming formulation [7]. A variable 𝑦 𝑣 gives the weight of vertex 𝑣, and 𝑧𝑒 gives the weight of hyperedge 𝑒: ∑︁ (P) max 𝑧𝑒 𝑒 ∈𝐸

s.t. 𝑧𝑒 ≤ 𝑦 𝑣 ∑︁ 𝑦 𝑣 ≤ 1,

(2) 𝑓𝑒,𝑣 ≤ 𝐷

𝑓𝑒,𝑣 ≥ 0.

∅≠𝑆 ⊆𝑉

We consider a fixed vertex universe and a sequence of hyperedge insertions and deletions. An insertion introduces a new edge identifier together with its endpoints; a deletion removes an active identifier. The sequence may contain arbitrary legal insertions and deletions. All graph quantities below refer to the current snapshot; we omit the time index when the snapshot is clear.

3.3

(𝑒 ∈ 𝐸),

𝑣 ∈𝑒

𝜌 ∗ = max 𝜌 (𝑆).

Thus, a hyperedge contributes one to the numerator exactly when all its endpoints belong to 𝑆. For convenience, we set 𝜌 (∅) = 0.

3.2

constraint. The dual is (D) min 𝐷 ∑︁ s.t. 𝑓𝑒,𝑣 ≥ 1

(𝑒 ∈ 𝐸, 𝑣 ∈ 𝑒), (1)

𝑣 ∈𝑉

𝑦 𝑣 , 𝑧𝑒 ≥ 0. The first constraint allows an edge to contribute only to the extent supported by every endpoint. The second normalizes the total vertex weight, turning the density ratio into a linear objective. Lemma 3.2 (Exact density formulation [7]). The optimum of Equation (1) equals 𝜌 ∗ . Thus the linear program captures the original density objective exactly. This equality lets us certify a combinatorially maintained set by comparing its density with a feasible dual allocation. We interpret the dual of Equation (1) as an orientation. Associate 𝑓𝑒,𝑣 ≥ 0 with each constraint 𝑧𝑒 ≤ 𝑦 𝑣 and 𝐷 ≥ 0 with the normalization

For each edge, excess mass above one can be removed without increasing any vertex load. Thus an optimal dual solution can satisfy Í 𝑣 ∈𝑒 𝑓𝑒,𝑣 = 1. Such an endpoint allocation is a fractional orientation: an integral orientation assigns the whole unit to one incident vertex, while a fractional orientation can split it among several vertices. By strong duality, the minimum possible maximum load over fractional orientations equals 𝜌 ∗ . Thus, any induced vertex set gives a lower bound on the optimum, while any fractional orientation gives an upper bound through its maximum load.

3.4

Allocation Bounds and Residual Paths

We next describe how to store the orientation, use it to certify an approximate solution, and adjust it through residual paths. We represent a fractional orientation using integer endpoint shares. Following the integer representation of fractional orientations [15], fix a positive integer 𝑏 and store shares 𝑥𝑒,𝑣 ∈ Z ≥0 satisfying ∑︁ ∑︁ 𝑥𝑒,𝑣 = 𝑏, 𝑞𝑣 = 𝑥𝑒,𝑣 . 𝑣 ∈𝑒

𝑒 ∋𝑣

The fraction assigned to 𝑣 by 𝑒 is 𝑥𝑒,𝑣 /𝑏, and 𝑞 𝑣 is its scaled load. Setting 𝑓𝑒,𝑣 = 𝑥𝑒,𝑣 /𝑏 gives a feasible solution to Equation (2) with 𝐷 = max𝑣 𝑞 𝑣 /𝑏. These quantized allocations form a subset of the dual feasible solutions; strong duality refers to optimization over all fractional orientations. Shares are counters; they do not require 𝑏 copies of an edge. Lemma 3.3 (Allocation upper bound [7, 10]). Every feasible allocation satisfies 𝜌 ∗ ≤ 𝑈 , where 𝑈 = max𝑣 ∈𝑉 𝑞 𝑣 /𝑏. The allocation need not minimize its maximum load: any feasible one already gives a valid upper bound. To certify the approximation, we compare this upper bound with the density of the maintained set. The witness 𝐶 supplies a feasible primal solution of value 𝐿, and the maintained orientation supplies a feasible dual solution of value 𝑈 . The approximation certificate is therefore the primal–dual bound 𝐿 ≤ OPT(P) = 𝜌 ∗ = OPT(D) ≤ 𝑈 ≤ (1 + 𝜖)𝐿. In Section 4, we maintain this certificate through combinatorial changes to the witness and endpoint shares. For example, suppose 𝐿 = 3 and 𝑈 = 3.2, as illustrated in Figure 1(a). Since 3 ≤ 𝜌 ∗ ≤ 3.2 and 3.2 ≤ (1 + 0.1) · 3, the maintained set is already a (1 + 0.1)-approximation. The certificate does not require knowing 𝜌 ∗ exactly or further reducing 𝑈 . Residual paths. A positive incidence is a pair (𝑒, 𝑢) with 𝑥𝑒,𝑢 > 0. 𝑒 It permits a residual step 𝑢 → − 𝑣 to any 𝑣 ∈ 𝑒: some of 𝑒’s share can move from 𝑢 to 𝑣. Consider a residual path of length ℓ ≥ 1 with distinct vertices and distinct hyperedges: 𝑒1

𝑒2

𝑒ℓ

𝑣 0 −→ 𝑣 1 −→ · · · −→ 𝑣 ℓ .

Chen et al. (a) A sufficient approximation certificate

𝜌 ∗ ∈ [𝐿, 𝑈 ] 𝐿 =3 𝜖 = 0.1 :

𝑈 = 3.2

(1 + 𝜖 )𝐿 = 3.3

𝑈 ≤ (1 + 𝜖 )𝐿 certifies 𝐶 .

(b) Redistributing shares along a residual path

𝑒1 : 𝑎 = 1

𝑒2 : 𝑎 = 1

𝑢

𝑣

𝑤

16 → 15

15 → 15

14 → 15

Integer loads 𝑞 𝑣 before → after (𝑏 = 5)

Figure 1: Allocation tools. (a) The interval [𝐿, 𝑈 ] contains the optimal density and certifies the maintained set at 𝜖 = 0.1. (b) A valid residual path on distinct hyperedges transfers one share at each step; the middle load is unchanged. Arrows show share transfers, not directions of the input hyperedges.

Moving a positive integer amount 𝑎 ≤ min𝑖 𝑥𝑒𝑖 ,𝑣𝑖 −1 at every step preserves each edge’s total allocation. The load of 𝑣 0 decreases by 𝑎, the load of 𝑣 ℓ increases by 𝑎, and the intermediate loads are unchanged. Figure 1(b) illustrates a two-edge path: transferring one share along each edge changes the three loads from (16, 15, 14) to (15, 15, 15). This is the basic operation used to repair an allocation. Residual closure under positive incidences is also used in hypergraph extraction algorithms [10].

4

(Section 4.3). A successful search returns a path for transferring load. If no destination is reachable, the reached set becomes a denser witness and increases the inner threshold; the outer capacity cannot decrease. An occasional peeling pass can also improve the witness (Section 4.4). The procedure returns once all loads are at most 𝑐; Section 4.5 proves that it always reaches this point. We analyze the maintenance cost in Section 5.

Witness-Guided Dynamic Maintenance

We formally propose our main algorithm called CAP (Capacitated Augmenting Paths) for Problem 3.1. We now give an overview of the algorithm. For a requested accuracy 0 < 𝜖 ≤ 1, we fix the integer precision 𝑏 ≥ ⌈2𝑟 /𝜖⌉ and two multipliers 𝛼 = 1 + 𝜖 and 𝛾 = 1 + 𝜖/2. The lower bound on 𝑏 ensures 𝑏𝐿 ≥ 2/𝜖 after witness normalization (Section 4.1). For a nonempty witness of density 𝐿, define an outer capacity 𝑐 = ⌊𝛼𝑏𝐿⌋ and an inner threshold 𝑡 = ⌊𝛾𝑏𝐿⌋. The outer capacity 𝑐 specifies the stopping condition: repair is needed exactly when some 𝑞 𝑣 > 𝑐. The inner threshold 𝑡 specifies where to move load: the search seeks a destination with 𝑞 𝑣 < 𝑡, although the transfer may increase its load up to 𝑐. We call this choice reserve destinations. The main idea is to use the density of the current witness to decide when the allocation needs repair. For a query, we directly output the maintained witness 𝐶. By Lemma 3.3, a maximum load of at most (1+𝜖)𝑏𝐿 already certifies 𝐶. If an update violates this condition, there are two ways to restore it: reduce the maximum load by moving shares, or increase the density of the witness. A residual search (Algorithm 2) identifies which of these actions to take. After every edge update processed by Algorithm 1, the maintained set has density at least 𝜌 ∗ /(1 + 𝜖) (Theorem 4.3). Specifically, Algorithm 1 has three steps. First, it updates the shares of the inserted or deleted edge and the induced-edge count of 𝐶 (Section 4.2). Second, it normalizes a witness whose density is too small and computes the resulting capacity (Section 4.4). Third, while a load exceeds this capacity, it searches from an overloaded vertex

4.1

Initialization

To implement CAP, we store the shares of each active edge, the loads 𝑞 𝑣 , and an indexed maximum heap over these loads. We also store 𝐶, membership marks, and the exact induced-edge count 𝑀. Each vertex has a list of its positive incidences, with inverse positions for updating the list when a share becomes zero or positive. Full incidence lists support edge updates and witness refresh. A counter 𝐷 records positive-incidence inspections since the last refresh. Thresholds are evaluated by exact integer cross-products; the analysis assumes that all intermediate arithmetic values are representable. We call a state stable when the allocation is feasible, the witness count is exact, and all loads are at most 𝑐; the empty state is stable with zero loads and zero bounds. At the end of each update, the stable allocation and witness satisfy 𝐿 ≤ 𝜌 ∗ ≤ 𝑈 ≤ 𝛼𝐿.

(3)

Starting from an empty graph, we set all loads to zero, 𝐶 = ∅, 𝑀 = 𝐿 = 𝑈 = 0, and 𝐷 = 0. An initial nonempty graph is built by inserting its edges through Algorithm 1. Before repairing a nonempty graph, we ensure 𝐿 ≥ 1/𝑟 . If necessary, we use the endpoints of a surviving edge as the witness and count all edges it induces. This normalization guarantees 𝑏𝐿 ≥ 2/𝜖.

4.2

Processing Insertions and Deletions

The implementation details of processing edge updates are shown in Algorithm 1. The procedure consists of the following steps: (1) Applying the update (Lines 1 to 6). (2) Preparing the certificate (Lines 7 to 10). (3) Restoring the certificate (Lines 11 to 24). (4) Returning the solution (Line 25). 4.2.1 Applying the Update. For an insertion, we increase 𝑀 exactly when all endpoints of 𝑒 lie in 𝐶 (Line 2). We then insert the edge and allocate its 𝑏 units by discrete water filling (Line 3). This rule gives priority to the least-loaded endpoints of 𝑒. More precisely, let 𝑞 𝑣 denote the load before insertion and start with 𝑥𝑒,𝑣 = 0 for every 𝑣 ∈ 𝑒. Repeatedly increase 𝑥𝑒,𝑣 by one for an endpoint minimizing Í 𝑞 𝑣 + 𝑥𝑒,𝑣 , breaking ties by endpoint order, until 𝑣 ∈𝑒 𝑥𝑒,𝑣 = 𝑏. We then add these shares to the endpoint loads. A binary search for the filling level computes the same allocation in batches. For a deletion, we decrease 𝑀 under the same containment condition (Line 5) and remove the edge’s shares from the endpoint loads (Line 6). Both branches update the affected incidence lists and heap keys. 4.2.2 Preparing the Certificate. If no edge remains, we return the empty witness and zero bounds (Line 8). Otherwise, we normalize the witness when needed (Line 9): we replace an empty witness or

Scalable Approximate Algorithm for Dynamic Densest Subhypergraphs with Solution-Guided Maintenance

Algorithm 1: CAP: process an edge update Input: An insertion or deletion of edge 𝑒; maintained state Output: A witness 𝐶 and bounds 𝐿, 𝑈 1 if inserting 𝑒 then 2 𝑀 ← 𝑀 + 1[𝑒 ⊆ 𝐶 ]; 3 Insert 𝑒 and water-fill its 𝑏 units among its endpoints; 4 else 5 𝑀 ← 𝑀 − 1[𝑒 ⊆ 𝐶 ]; 6 Subtract 𝑥𝑒,𝑣 from every 𝑞 𝑣 , 𝑣 ∈ 𝑒, and remove 𝑒; if 𝐸 = ∅ then 8 Set 𝐶 ← ∅, 𝑀, 𝐿, 𝑈 ← 0; return ;

7

Normalize 𝐶 if 𝐶 = ∅ or 𝑀/|𝐶 | < 1/𝑟 ; Set 𝐿 ← 𝑀/|𝐶 |, 𝑐 ← ⌊𝛼𝑏𝐿⌋; 𝑓 ← false; 11 while max𝑣 𝑞 𝑣 > 𝑐 do 12 if refresh is enabled, 𝐷 > 4(𝑛 + 𝑟𝑚), and 𝑓 = false then 13 Refresh 𝐶 by peeling; 𝐷 ← 0; 𝑓 ← true; 14 Recompute 𝐿, 𝑐; 15 if max𝑣 𝑞 𝑣 ≤ 𝑐 then 16 break; 9

10

17 18 19 20 21 22 23 24 25

𝑧 ← arg max𝑣 𝑞 𝑣 ; 𝑡 ← ⌊𝛾𝑏𝐿⌋; Search from 𝑧 with threshold 𝑡 using Algorithm 2; Add the search’s positive-incidence inspections to 𝐷; if the search returns a path 𝜋 to 𝑤 then Transfer the amount in Equation (4) along 𝜋 ; else Í 𝐶 ← 𝑅; 𝑀 ← 𝑣 ∈𝑅 𝑞 𝑣 /𝑏; Recompute 𝐿 ← 𝑀/|𝐶 | and 𝑐 ← ⌊𝛼𝑏𝐿⌋; 𝑈 ← max𝑣 𝑞 𝑣 /𝑏; return (𝐶, 𝐿, 𝑈 );

one of density below 1/𝑟 by the endpoints of a surviving edge and compute their induced-edge count. Section 4.4.1 gives the details. We then compute 𝐿 and 𝑐, and reset 𝑓 to false (Line 10). This flag permits at most one peeling refresh during the current update. An insertion never lowers the density of the retained witness. Only the inserted edge adds load, so it creates at most 𝑏 units of excess above the new capacity. Deleting an edge 𝑒 ⊈ 𝐶 leaves the witness density and capacity unchanged while reducing loads; it therefore requires no repair. Deleting an edge 𝑒 ⊆ 𝐶 can lower the capacity throughout the graph. We consequently test the global maximum load after normalization and enter the repair loop only when this maximum exceeds 𝑐 (Line 11). 4.2.3 Restoring the Certificate. Each iteration first checks whether the accumulated inspection count 𝐷 exceeds 4(𝑛 + 𝑟𝑚) and no refresh has occurred during this update (Line 12). If so, a peeling pass seeks a denser witness, which can raise the capacity without moving load (Line 13; details in Section 4.4.2). We reset 𝐷, set 𝑓 to true, and recompute 𝐿, 𝑐. If the new capacity already bounds every load, the loop ends (Lines 14 to 16). Otherwise, we select a maximum-load vertex 𝑧, compute the inner threshold 𝑡, and invoke the residual search (Lines 17 and 18). This search either finds a path from 𝑧 to a vertex 𝑤 with 𝑞 𝑤 < 𝑡, or returns the entire reached set 𝑅 when no such destination exists. Section 4.3 describes this breadth-first process in Algorithm 2. Loads

remain fixed during the search; its positive-incidence inspections are added to 𝐷 (Line 19). On success, we transfer load along the returned path (Line 21). Let 𝜋 be the parent path from 𝑧 to the destination 𝑤, and let 𝑥𝑖 be the donor share on its 𝑖th step. We transfer n o 𝑎 = min 𝑞𝑧 − 𝑐, 𝑐 − 𝑞 𝑤 , min 𝑥𝑖 (4) 𝑖 ∈𝜋

𝑒

units along every step. On a step 𝑢 → − 𝑣, this subtracts 𝑎 from 𝑥𝑒,𝑢 and adds 𝑎 to 𝑥𝑒,𝑣 . Positive-incidence lists are adjusted when shares cross zero. Only the loads and heap keys of 𝑧 and 𝑤 change. The destination may end above 𝑡; the transfer is bounded by the outer capacity 𝑐. For example, suppose 𝑟 = 3, 𝜖 = 0.5, 𝑏 = 12, and 𝐿 = 1, giving 𝑐 = 18 and 𝑡 = 15. A root of load 20 can transfer two units to a destination of load 14 if every donor share on the path is at least two. The new endpoint loads are 18 and 16. The destination exceeds 𝑡 after the transfer, but both endpoints satisfy the capacity 𝑐. On failure, we replace 𝐶 by 𝑅 and obtain its exact edge count as Í 𝑀 = 𝑣 ∈𝑅 𝑞 𝑣 /𝑏 (Line 23). Lemma 4.2 proves both this identity and 𝜌 (𝑅) > 𝐿. We recompute the density and capacity (Line 24), then repeat the maximum-load test. The new capacity cannot decrease, and the load sum avoids a separate containment scan over the reached set. 4.2.4 Returning the Solution. Once all loads fit within 𝑐, we set 𝑈 = max𝑣 𝑞 𝑣 /𝑏 and return the maintained set 𝐶 together with 𝐿 and 𝑈 (Line 25). The stopping condition and allocation bound give 𝐿 ≤ 𝜌 ∗ ≤ 𝑈 ≤ (1+𝜖)𝐿. Section 4.5 proves that every update reaches this condition. 4.2.5 Complexity Analysis. For an edge of size 𝑠, containment testing and share removal inspect 𝑂 (𝑠) incidences. Batch water filling takes 𝑂 (𝑠 [log(𝑠 + 1) + log(𝑏 + 1)]) time, and updating the heap keys costs 𝑂 (𝑠 log(𝑛 + 1)). Deletion also updates inverse incidence positions in 𝑂 (𝑠 log(𝑟 + 1)) time. These costs are incurred even when no residual search is needed. Restoring the certificate additionally pays for every search and path transfer. Section 4.3.3 gives the search cost in terms of the incidences examined. For a path of ℓ steps, the parent pointers identify donor shares, and binary search locates receiving shares in the sorted endpoint lists. Thus a transfer takes 𝑂 (ℓ log(𝑟 + 1) + log(𝑛 + 1)) amortized time, including changes to the two endpoint heap keys. Normalization and optional refresh are accounted for in Sections 4.4.1 and 4.4.2; Section 5.3 combines these costs. Querying the bounds costs 𝑂 (1); reporting 𝐶 costs Θ(1 + |𝐶 |).

4.3

Residual Search

The residual search determines where an overloaded vertex can send load. Algorithm 2 performs a breadth-first search from 𝑧 along positive incidences, using the residual paths defined in Section 3.4. It stops at the first reached vertex whose load is below the destination threshold 𝜃 . If there is no such vertex, it returns the reached set 𝑅. In CAP, 𝜃 = 𝑡; the returned path permits a transfer, while a failed search identifies a denser witness. 4.3.1 Search Procedure. Line 1 initializes 𝑅 and the queue 𝑄 with 𝑧 and starts a fresh expansion stamp. The queue processes vertices

Chen et al.

Algorithm 2: Search(𝑧, 𝜃 ) Input: Root 𝑧 with 𝑞𝑧 > 𝑐; destination threshold 𝜃 ≤ 𝑐 Output: A residual path, or the reached set 𝑅 1 𝑅 ← {𝑧 }; 𝑄 ← [𝑧 ]; mark no edge expanded; 2 while 𝑄 ≠ ∅ do 3 Pop the first vertex 𝑢 from 𝑄; 4 foreach positive incidence (𝑒, 𝑢 ) do 5 if 𝑒 is already expanded then 6 continue; 7 8 9 10 11 12 13

14

Mark 𝑒 expanded; foreach 𝑣 ∈ 𝑒, in stored order do if 𝑣 ∉ 𝑅 then Add 𝑣 to 𝑅; set its parent to (𝑢, 𝑒 ); if 𝑞 𝑣 < 𝜃 then return the parent path from 𝑧 to 𝑣;

If no destination is found, the reached set provides a better witness. This makes failed searches useful: they improve the witness and strictly increase the inner threshold used by subsequent searches (Equation (6)). Lemma 4.2 (Witness improvement). A failed search with threshold 𝑡 returns a set 𝑅 of density 𝜌 (𝑅) > 𝐿 satisfying ∑︁ 𝑞 𝑣 > 𝑡 |𝑅|, (5) 𝑏 |𝐸 (𝑅)| = 𝑣 ∈𝑅

The conclusion supplies the other kind of progress. When load cannot be moved out of the reached set, that set itself improves the witness density and strictly increases the inner threshold. The outer capacity cannot decrease. The load sum also gives its induced-edge count, so this improvement needs no separate containment scan.

Append 𝑣 to 𝑄; return 𝑅 as a failed search;

in breadth-first order (Lines 2 and 3). For each popped vertex 𝑢, we inspect its positive incidences (Line 4), since only edges with 𝑥𝑒,𝑢 > 0 can transfer load away from 𝑢. Lines 6 and 7 skip an edge already expanded by this search and mark a newly encountered edge before examining its endpoints. Each edge is therefore expanded at most once. For every unseen endpoint 𝑣, we add it to 𝑅 and record (𝑢, 𝑒) as its parent (Lines 8 to 10). These parent pointers retain the residual steps by which vertices were reached. If 𝑞 𝑣 < 𝜃 , the parent pointers give a path from 𝑧 to 𝑣, which the search returns immediately (Lines 11 to 12). Otherwise, 𝑣 is appended to 𝑄 for further exploration (Line 13). If the queue becomes empty, every positive incidence reachable from 𝑧 has been examined; we return 𝑅 as a failed search (Line 14). 4.3.2 Effectiveness Analysis. The following two lemmas show that successful searches reduce excess load and failed searches improve the witness. The load gap provided by reserve destinations also yields the transport bound in Section 5.2. Lemma 4.1 (Progress of a successful search). A successful transfer preserves a feasible allocation and decreases the integer excess Í 𝑋𝑐 = 𝑣 (𝑞 𝑣 − 𝑐)+ by 𝑎 ≥ 1. Thus a successful search makes measurable progress: it removes 𝑎 units of overload without creating overload at the destination. This bounds the number of successful searches by the total excess repaired. Proof. The first expansion of an edge reaches all its unseen endpoints at the same BFS layer, unless the search terminates. These endpoints are siblings in the parent tree; a parent path thus uses an edge at most once. Its minimum donor share bounds the transfer on each edge. All intermediate load changes cancel. The root loses 𝑎 excess units, and the destination receives at most its available capacity 𝑐 − 𝑞 𝑤 . □

Proof. Every edge with a positive owner in 𝑅 exposes all its endpoints before the queue becomes empty. Hence crossing edges assign no mass to 𝑅, whereas each induced edge assigns all 𝑏 units there. Every reached vertex has load at least 𝑡, and the root exceeds 𝑐 ≥ 𝑡, giving the strict inequality. Since 𝑏𝐿 ≥ 2/𝜖, 𝑡 = ⌊𝑏𝐿+𝜖𝑏𝐿/2⌋ ≥ 𝑏𝐿. Thus 𝜌 (𝑅) > 𝐿. □ 4.3.3 Time Analysis. For one search, let 𝑃 count inspected positive incidences, including those skipped because their edge was already expanded, and let 𝐽 count endpoints inspected during edge expansions. Vertex and edge stamps avoid clearing all marks before a search. Every vertex other than the root is discovered during an endpoint inspection, and is queued at most once. Hence queue operations, marking, and parent recording take 𝑂 (1 + 𝐽 ) time; the two incidence loops take 𝑂 (𝑃 + 𝐽 ) time. A returned path has at most 𝐽 steps, so following its parent pointers is covered by the same bound. Thus the search takes 𝑂 (1 + 𝑃 + 𝐽 ) time. Summing the loads of a failed reached set also takes 𝑂 (1 + 𝐽 ) time. Updating the allocation and installing a new witness are charged separately in Section 5.3. Each vertex is expanded at most once and each edge is stamped after its first expansion, so 𝑃 ≤ 𝐼 and 𝐽 ≤ 𝐼 for the current incidence volume 𝐼 . This gives an 𝑂 (1 + 𝐼 ) worst-case bound for a single search. Section 5.1 sharpens the bound using the high-load region visited by the search; Section 5.2 bounds the transport needed across successful searches. We also bound the number of failed searches during one update. By Lemma 4.2, a failure produces a new density 𝐿 ′ with 𝑏𝐿 ′ > 𝑡. The recomputed threshold therefore satisfies 𝑡 ′ = ⌊(1 + 𝜖/2)𝑏𝐿 ′ ⌋ ≥ 𝑡 + ⌊𝜖𝑡/2⌋. Normalization gives 𝑡 ≥ 2/𝜖. Since ⌊𝑎⌋ ≥ 𝑎/2 for 𝑎 ≥ 1, each failure yields 𝑡 ′ ≥ 𝑡 + ⌊𝜖𝑡/2⌋ ≥ (1 + 𝜖/4)𝑡 .

(6)

If 𝑡 0 is the threshold before the first search in an update, its number of failed searches is consequently at most
  log ⌊(1 + 𝜖/2)𝑏𝜌 ∗ ⌋/𝑡 0 . log(1 + 𝜖/4) Here the graph is fixed during repair, so the threshold is at most ⌊(1 + 𝜖/2)𝑏𝜌 ∗ ⌋ and cannot decrease between searches. This count applies to a fixed update; Section 5.3 accounts for threshold decreases across an entire update sequence.

Scalable Approximate Algorithm for Dynamic Densest Subhypergraphs with Solution-Guided Maintenance

4.4

Maintaining and Refreshing the Witness

We discuss the details of two steps in Algorithm 1: normalization (Line 9) and budgeted refresh (Line 13). Normalization ensures the minimum witness density needed by the thresholds, whereas refresh seeks a denser witness to reduce subsequent repair work. 4.4.1 Normalization. The normalization step (Line 9) chooses a surviving edge 𝑒 and sets 𝑆 = 𝑒 when the witness is empty or 𝐿 < 1/𝑟 . The set may induce several hyperedges, so we compute |𝐸 (𝑆)| exactly. We inspect positive incidences at vertices of 𝑆, deduplicate encountered edges with a stamp, and test each encountered edge for containment. A test stops at the first endpoint outside 𝑆. Every induced edge has a positive owner in 𝑆 and is counted once. Installing this witness restores 𝐿 ≥ 1/|𝑒 | ≥ 1/𝑟 . 4.4.2 Budgeted Refresh. A denser witness can avoid subsequent repairs. We occasionally run minimum-degree hypergraph peeling and select the densest remaining suffix of its removal order. The suffix replaces 𝐶 only if its density is strictly larger. During peeling, an edge is removed once, when its first endpoint is removed, so suffix densities are exact. The allocation is retained. The refresh is triggered before a search when accumulated positive scans exceed 4(𝑛 + 𝑟𝑚). We install the improved witness, reset 𝐷, and set 𝑓 to true (Line 13). Recomputing 𝐿 and 𝑐 may already certify the current allocation, in which case the repair loop ends (Line 14). At most one refresh occurs in an update. A pass costs 𝑂 ((𝑛 + 𝐼 ) log(2 +𝑛 + 𝐼 )), which is charged to the accumulated scans in Section 5.3. Both normalization and refresh never decrease the current witness density and therefore cannot create an overload by lowering the capacity.

4.5

Correctness

Updates and transfers preserve feasible shares (Lemma 4.1); successful searches reduce excess load, while failed searches increase the witness density (Lemma 4.2); and the stopping condition gives the approximation certificate (Lemma 3.3). The only remaining issue is to show that repair cannot continue indefinitely. The proof of Theorem 4.3 below establishes this. Theorem 4.3 (All-update guarantee). Let 0 < 𝜖 ≤ 1 and 𝑏 ≥ ⌈2𝑟 /𝜖⌉. For CAP, every legal update terminates with an explicit set 𝐶 satisfying 𝜌 (𝐶) ≤ 𝜌 ∗ ≤ 𝑈 ≤ (1 + 𝜖)𝜌 (𝐶). Proof. Insertion and removal preserve the allocation of surviving edges; Lemma 4.1 establishes the same property for transfers. Í During repair the graph is fixed. Define excess 𝑋𝑐 = 𝑣 (𝑞 𝑣 − 𝑐)+ . Every successful transfer decreases 𝑋𝑐 by its positive integer amount. A witness improvement cannot increase 𝑋𝑐 . Recall that 𝑡 = ⌊(1 + 𝜖/2)𝑏𝐿⌋. Normalization gives 𝑏𝐿 ≥ 2/𝜖, hence 𝑡 ≥ 2/𝜖. On any failed search, the new witness density 𝐿 ′ satisfies 𝑏𝐿 ′ > 𝑡. Therefore ⌊(1 + 𝜖/2)𝑏𝐿 ′ ⌋ ≥ 𝑡 + ⌊𝜖𝑡/2⌋ ≥ 𝑡 + 1. The witness strictly improves, and the inner threshold increases strictly. It is bounded by ⌊(1 + 𝜖/2)𝑏𝜌 ∗ ⌋ on this fixed graph. There are finitely many failures, at most the initial excess in successful searches, and at most one optional refresh per update. Repair thus terminates with max𝑣 𝑞 𝑣 ≤ 𝑐, which yields the claimed certificate by allocation duality and 𝑐 = ⌊(1 + 𝜖)𝑏𝐿⌋. □

We summarize the time and space complexity in Section 5. Deriving the maintenance-time bound requires quantifying the search work and load transport of witness-guided repair, so we devote Section 5 to this analysis.

5

Analysis of Solution-Guided Maintenance

Theorem 4.3 proves that CAP maintains a (1 + 𝜖)-approximate solution after every update. We now analyze the work required to maintain this guarantee. A bound that charges every update for the whole hypergraph hides the main benefit of CAP: an update can finish without a search, and a search can stop after inspecting only a small part of the allocation. We analyze these savings through the work performed by the maintenance procedure. We first give a general update-time guarantee, then refine it to identify the work saved by solution-guided maintenance. Consider 𝑁 ≥ 1 legal updates from an empty hypergraph, with 𝑏 = ⌈2𝑟 /𝜖⌉ and 0 < 𝜖 ≤ 1. A nonempty initial graph is charged as a sequence of insertions. Theorem 5.1 (General amortized update time). CAP has amortized update time   log(𝑛 + 𝑟𝑚 ∗ ) + log(1/𝜖) , 𝑂 𝑟𝑚 ∗ 𝐼 ∗ 𝜖 where 𝑚 ∗ and 𝐼 ∗ are the maximum active hyperedge count and incidence volume over the update sequence, respectively. The bound excludes the one-time 𝑂 (𝑛) initialization cost. Theorem 5.1 follows by bounding every search using the full active incidence volume and every update using the maximum possible transport. To capture the savings from local searches and retaining the current solution, we instead count the work actually performed. Theorem 5.2 (Maintenance work and qeries). After every update, CAP maintains a set of density at least 𝜌 ∗ /(1 + 𝜖). Its total maintenance time is  𝑛 + 𝑟𝑚 ∗  , (7) 𝑇maint = 𝑂 𝑛 + (𝑅up + 𝑆 scan + 𝑍 norm ) log 𝜖 where 𝑅up counts the endpoints of updated edges, 𝑆 scan counts positive-incidence and endpoint inspections in residual searches, and 𝑍 norm counts the same inspections when installing fallback witnesses. Reading its density takes 𝑂 (1) time, and reporting its vertices takes Θ(1 + |𝐶 |) time per query. The proof of Theorems 5.1 and 5.2 is given in Appendix B. The input term 𝑅up depends only on the updated edges. The search term 𝑆 scan combines how much a search examines (Section 5.1) with how often repair needs to move load or replace the solution (Sections 5.2 and 5.3). The normalization term 𝑍 norm is paid only when a fallback solution requires a new induced-edge count. Section 5.3 bounds these three terms and combines them into an amortized update bound. Memory Analysis. CAP stores vertex loads, the indexed heap, witness membership, and search marks and parent pointers in 𝑂 (𝑛) words. Each active incidence stores an allocation share and a constant number of entries and inverse positions in the incidence lists. Together with the endpoint arrays and active-edge records, these

Chen et al.

Í occupy 𝑂 (𝐼 ) words, where 𝐼 = 𝑒 ∈𝐸 |𝑒 | is the current incidence volume. Searches and peeling use 𝑂 (𝑛 + 𝐼 ) temporary space. Thus, a compacted representation uses 𝑂 (𝑛 + 𝐼 ) words in total.

5.1

Bounding Search Work by Locality

We first bound 𝑆 scan in Equation (7). A search expands only vertices whose load reaches its destination threshold 𝑡. Since 𝑞 𝑣 ≤ 𝑏 deg(𝑣), let ℎ bound the number of vertices with 𝑏 deg(𝑣) ≥ 𝑡 at the start of any search, and let 𝑄 bound the maximum load at those times. If no search occurs, set ℎ = 𝑄 = 0. Let 𝐴 be the total amount transported and 𝐹 the number of failed searches. A transfer of 𝑎 units contributes 𝑎 to 𝐴, once per path. Lemma 5.3 (Search work from local regions). The total search work satisfies 𝑆 scan ≤ (1 + min{𝑟, ℎ})ℎ𝑄 (𝐴 + 𝐹 ) + 𝐴.

(8)

The proof of Lemma 5.3 is given in Appendix A.1. The factor (1 + min{𝑟, ℎ})ℎ𝑄 bounds the work of one search, apart from its final destination test. The factor 𝐴 + 𝐹 bounds how many searches occur. Thus a small high-load region reduces the work per search; the next subsection bounds the transport that can cause searches to repeat. A large crossing edge need not cause a full endpoint scan: only its prefix up to the first eligible destination is tested. The bound still counts every inspected positive incidence, including one whose edge was expanded earlier in the same search. For example, suppose only 20 vertices meet the degree threshold for expansion. Every fully scanned edge then has at most 20 endpoints. Even if the final edge has 1,000 endpoints, the search tests at most 21 of them before finding a destination. Thus the endpoint multiplier is controlled by the small searchable region, not by the largest edge. The factor 𝑄 still accounts for how many positive shares these vertices may own. This situation can arise when a small, highly active community is surrounded by many low-degree vertices. Once the maintained solution sets a sufficiently high threshold, those low-degree vertices cannot be expanded. The bound therefore explains how a large hypergraph can admit inexpensive local searches; it does not require the whole graph to be small.

5.2

Bounding Transport by Density Changes

To make Lemma 5.3 useful, we next bound 𝐴. An insertion adds only 𝑏 units of load and never lowers the retained solution density, so it transports at most 𝑏 units. A deletion can lower the solution density and hence the capacities. We charge its transport according to the density loss and the load exposed to the lower threshold. Write 𝑠 = 𝛼𝑏𝐿 and 𝛽 = 𝛾/𝛼. For a deletion 𝑑, let 𝑠 old be the previous scale, 𝑞e the loads just after removing the edge, and 𝑠 0 the scale after witness normalization but before transport. If the graph becomes empty or 𝑠 0 ≥ 𝑠 old , set 𝑍𝑑 = 0; otherwise define   ∑︁ 1 + 2/𝑠 old 𝑠 old 𝑍𝑑 = −1 𝑞e𝑣 . (9) 𝑏 𝑠0 𝑞e𝑣 +1>𝛽𝑠 0

The ratio measures the relative drop in solution density. The sum includes only load exposed to the new threshold, and division by 𝑏

expresses this load in edge units. Thus a small density drop affecting little load has a small exposure charge 𝑍𝑑 . Lemma 5.4 (Transport controlled by density loss). For an update sequence starting from empty, with 𝑏 = ⌈2𝑟 /𝜖⌉ and 0 < 𝜖 ≤ 1, total transport satisfies ! 𝑟 ∑︁ 𝑟 𝑍𝑑 , (10) 𝐴 = 𝑂 𝑁+ + 2 𝜖 𝜖 𝑑 Í where 𝑁 + is the number of insertions and 𝑑 𝑍𝑑 is the total exposure charge over all deletions in the update sequence. The insertion term depends only on the new mass. The deletion term depends on the actual density loss and exposed load, rather than on all active edges at every deletion. For example, deleting an edge outside the current solution gives 𝑍𝑑 = 0. If the solution contains 𝑀 edges and loses one while retaining its vertices, its density falls by a fraction 1/𝑀. For 𝑀 ≥ 2, normalization can only improve this remaining density, so 𝑠 old /𝑠 0 − 1 ≤ 1/(𝑀 − 1). A solution with 100 edges therefore incurs a relative-scale charge of at most 1/99, whereas a two-edge solution can incur a charge of one. The same single-edge deletion can thus have very different effects on repair. Only vertices whose load exceeds the shifted new threshold contribute to the other factor in 𝑍𝑑 . Many low-load vertices do not increase this charge. These two effects explain when aggregate transport can be small: the dense solution persists through many updates, and its occasional density losses expose little load. This is a plausible pattern in a temporal interaction stream where individual interactions expire while a well-connected group remains active. We define a potential that assigns a quadratic cost to loads above a shifted destination threshold. Each transfer decreases this potential by an amount proportional to the mass transported. Bounding the increases caused by insertions and density losses, then summing over the update sequence, bounds total transport. The full proof of Lemma 5.4 is given in Appendix A.2. Lemma A.4 retains the boundary potentials for a nonempty initial state. The degree-tail specialization in Appendix A.4 further bounds 𝑍𝑑 using 𝑞e𝑣 ≤ 𝑏 degafter (𝑣): only vertices of sufficiently high degree can contribute exposed load. In an 𝑟 -uniform hypergraph, deleting the sole induced edge of a normalized witness has zero exposure, as shown in Lemma A.4. Combining the transport bound with Lemma 5.3 now gives the search-work bound used in the running-time analysis. Lemma 5.5 (Search work under solution-guided maintenance). Under the assumptions of Lemma 5.4, with ℎ, 𝑄, 𝐹 as in Lemma 5.3,  𝑆 scan = 𝑂 (1 + min{𝑟, ℎ})ℎ𝑄 h (11) 𝑟 𝑟 ∑︁ i  · 𝐹 + 𝑁+ + 2 𝑍𝑑 . 𝜖 𝜖 𝑑

Proof of Lemma 5.5. Substitute Equation (10) in Equation (8). If a search occurs, ℎ, 𝑄 ≥ 1, so the additive 𝐴 is absorbed by (1 + min{𝑟, ℎ})ℎ𝑄 (𝐴 + 𝐹 ). Otherwise 𝑆 scan = 𝐴 = 𝐹 = 0. □ The bound separates two sources of savings: a small high-load region limits each search, and limited density loss reduces the

Scalable Approximate Algorithm for Dynamic Densest Subhypergraphs with Solution-Guided Maintenance

repeated transport caused by deletions. The failed-search count 𝐹 is bounded next.

5.3

From Repair Work to Running Time

We now combine the search-work bound with the cost of applying updates and normalizing fallback solutions. Let 𝑁 fb count updates that install a fallback solution with an unknown induced-edge count. Lemma 5.6 (Combined amortized update time). For the update sequence of Lemma 5.5, the amortized update time, excluding initialization, is " (1 + min{𝑟, ℎ})ℎ𝑄 𝑂 𝑟+ 𝑁  𝑟 ∑︁  𝑟 𝑍𝑑 · 𝐹 + 𝑁+ + 2 (12) 𝜖 𝜖 𝑑 # ! 𝑛 + 𝑟𝑚 ∗ 𝑁 fb + 𝐼∗ log . 𝑁 𝜖 Proof of Lemma 5.6. Applying an update inspects its endpoints, Í so 𝑅up = updates |𝑒 | ≤ 𝑟 𝑁 . Lemma 5.5 bounds 𝑆 scan . Each fallback scans a positive incidence at most once and stamps each encountered edge before testing its endpoints. Its incidence and endpoint inspection counts are therefore each at most 𝐼 ∗ , giving 𝑍 norm ≤ 2𝐼 ∗ 𝑁 fb . There is at most one such fallback per update; failed searches and peeling already supply their induced-edge counts. Substitute these three bounds in Equation (7), which includes path transfers, heap maintenance, and budgeted peeling. Excluding initialization and dividing by 𝑁 proves the result. □ The expression has three parts: the size of the updated edge, local search work averaged over the sequence, and fallback cost multiplied by how often it occurs. Its middle term combines the two preceding lemmas: a small high-load region lowers the cost per search, while limited density loss restricts how much transport needs to repeat. The last term is small when the maintained solution rarely needs fallback normalization. Failed searches also make progress: each raises the inner threshold by a factor of at least 1+𝜖/4 (Equation (6)), giving 𝑂 (𝜖 −1 log(2+ 𝑟𝑚 ∗ )) failures per update. The sequence-wide bound in Lemma B.1 further charges repeated threshold increases to decreases caused by deletions. For example, deleting an edge outside the current witness leaves its density and capacity unchanged and can only lower loads. Such an update has no search or normalization cost, so its maintenance time is 𝑂 (|𝑒 | log((𝑛 + 𝑟𝑚 ∗ )/𝜖)). The counter bound in Equation (7) captures this case directly, while Equation (12) bounds the contributions over the full sequence. More generally, a stream can be large while most changes preserve a dense community and the repairs remain confined to a small surrounding region. Occasional changes within that community can also be inexpensive when it contains many edges, as the density-loss example in Section 5.2 illustrates. These patterns offer a plausible explanation for the observed efficiency of solution-guided maintenance. The running-time results (Section 6.2) and the reductions in positive scans in the capacity-slack and reserve-destination

ablation (Section 6.7) are consistent with this explanation of the observed efficiency.

6

Evaluation

We evaluate the efficiency and solution quality of CAP on real-world hypergraph datasets and ordinary graphs (𝑟 = 2). We first introduce the datasets, baselines, and query schedules (Section 6.1), and compare running times on dynamic hypergraphs (Section 6.2). We then validate the approximation quality of the returned solutions (Section 6.3), study scalability with query frequency (Section 6.4) and data size (Section 6.5), examine the effect of the accuracy parameter (Section 6.6), evaluate witness-guided repair through an ablation study (Section 6.7), and compare performance on ordinary graphs (Section 6.8).

6.1

Experiment Setting

Datasets. We select five publicly-available real-world hypergraph datasets from the Cornell collection [6]1 : DW, MA, AU, GE, and SO. DW records drug co-occurrences; MA, AU, and SO contain tags assigned to online questions; GE records publication coauthorship. Table 1 shows the statistics of these hypergraph data. We remove hyperedges containing only one vertex and repeated hyperedges that are already active, same as in Udshp [7]. We use the same calendarbased query schedule as Udshp [7]. Specifically, the update operations are generated in the following manners: • Quarter-based windows. DW provides quarterly timestamps. We insert hyperedges in temporal order, delete those from the preceding quarter, and issue queries at quarter boundaries. • Timestamp-based windows. MA, AU, and SO provide event timestamps. We normalize them into 90-day bins, retain bin indices greater than one, and maintain a one-bin window. Incoming tag sets generate insertions, expired hyperedges generate deletions, and queries occur at bin boundaries, including bins without new events. • Year-based windows. GE provides publication years. We maintain a ten-year window, insert incoming publications, delete expired hyperedges, and issue annual queries, including years without new publications. These calendar boundaries yield 32, 29, 33, 210, and 35 queries on DW, MA, AU, GE, and SO, respectively. Queries at empty calendar bins are retained, so several queries can follow the same update. For the query-frequency experiment, we keep the update stream fixed and increase the original number of queries, 𝑄 0 , to 4𝑄 0 and 16𝑄 0 . We divide the update sequence into 15𝑄 0 equal-length intervals and add one query after the midpoint update of each interval. If that position is already queried, we select the nearest unused update position, breaking ties toward the earlier update. The 16𝑄 0 schedule contains all these queries and all original queries. The 4𝑄 0 schedule retains the middle added query from each consecutive group of five, together with all original queries. We use 32, 128, and 512 queries on DW, and 210, 840, and 3,360 queries on GE. We also use six ordinary graph datasets: EM, HT, WV, BC, AS, and SW.2 For EM, HT, and WV, we initialize half of the edges and generate 1 https://www.cs.cornell.edu/~arb/data/ 2 https://snap.stanford.edu/data/; the dynamic AS and SW streams are available from

https://dyreach.taa.univie.ac.at/.

Chen et al.

Table 1: Datasets used in experiments. 𝑛: number of vertices; 𝑟 : maximum edge size; 𝑚 max : peak number of active edges. Dataset (Abbr.)

𝑛 𝑟

𝑚 max

Updates Queries

DAWN (DW) 2,290 16 11,544 529,412 Math (MA) 1,627 5 21,349 611,274 AskUbuntu (AU) 3,021 5 10,458 382,007 Geology (GE) 1,087,111 25 409,152 1,471,530 StackOverflow (SO) 49,918 5 351,521 15,897,567 Email (EM) HepTh (HT) WikiVote (WV) Bitcoin (BC) AS-CAIDA (AS) SimpleWiki (SW)

986 9,875 7,115 5,881 31,379 100,312

32 29 33 210 35

2 8,058 28,032 281 2 13,040 32,986 330 2 50,564 70,381 704 2 2,812 44,434 445 2 53,613 587,677 5,877 2 698,216 1,439,148 14,392

20,000 random edge insertions or deletions on the source topology. For BC, we process ratings in timestamp order using a 90-day window. AS uses changes between consecutive snapshots, and SW uses timestamped hyperlink insertions and deletions. We project these data to undirected, unweighted graphs; in SW, we exclude pairs with an unmatched deletion in their chronological history. The last six rows of Table 1 summarize these graphs. Baselines. The comparison includes CAP and the following five baselines. • Udshp [7]: Our primary dynamic baseline directly addresses the same densest-subhypergraph objective under hyperedge insertions and deletions. To the best of our knowledge, the authors’ implementation is the most recent publicly available implementation for this problem. It maintains a hypergraph orientation and identifies a dense set through local endpoint-load conditions. • CQ [15]: This theoretical paper studies ordinary graphs in its main results. A preliminary version discusses a hypergraph extension in Section 6, omitting the deletion pseudocode.3 We could not locate an accompanying implementation, so we implement its basic amortized core and hypergraph extension in C++. Our version uses unit-copy updates, shared multiplicities, nested label buckets, and load-threshold extraction. We complete hypergraph deletion by selecting a global minimum-load endpoint and processing changed endpoints through a worklist. Implementation details and scope are given in Appendix C. • Exact [7]: This linear-programming algorithm solves the current hypergraph using GLOP and extracts a dense set from the positive-support vertices. • DI [33]: Density Improvement repeatedly solves flow subproblems to increase the density. We use its exact global solver. • ExactFlow [5]: This flow algorithm maximizes density under convex, monotonic hyperedge rewards. We use the reward vector [0, . . . , 0, 1] for fully contained-edge density. We exclude HWC [32] from the baselines mainly because its rankdependent 𝑟 2 (1 + 𝜖𝐻 ) guarantee does not ensure the (1 + 𝜖) approximation required in our comparison. We also considered an adaptation of IDH [37], a dynamic integer-density decomposition 3 https://arxiv.org/abs/2210.02611

method. Our adaptation uses 𝛿 = 1, modified load-based pathreversal maintenance, and extraction of the highest-layer vertex set, with 𝑏 = ⌈(1 + 𝜖)𝑟 /𝜖⌉ explicit copies per hyperedge to meet our approximation target. Even at 𝜖 = 1, this variant did not complete the full update-and-query stream on AU, MA, or DW within a 300-second wall-time limit in our single-run pilots. We therefore exclude it from the baseline comparison. Setting. We run experiments on a machine having an Intel Core i9-10850K CPU and 32 GB of memory, with Windows 11 installed. C++ implementations are compiled with GCC 12.1 and optimization enabled. The two static flow solvers use Julia 1.9.4 with one thread, and Exact uses OR-Tools 9.11.4210. We run experiments serially and report mean total running times only after three complete, independently validated repetitions. Times are rounded to two decimal places, and the smallest reported mean is shown in bold. For hypergraph queries returning full vertex sets, total running time covers maintenance and queries, including static-solver input construction and materialization of returned vertices. It excludes input parsing, initialization, and independent verification; Julia warmup precedes timing. The main, query-frequency, and accuracyparameter comparisons use a 1,800-second whole-process limit, while ablation runs use a 300-second limit. Parameters. For a given 𝜖, CAP targets density 𝜌 ∗ /(1+𝜖) and uses reserve destinations, 𝑏 = ⌈2𝑟 /𝜖⌉, and budgeted peeling. For Udshp, we use the same numerical 𝜖 as its native experimental parameter, with copy count round(𝜖 −2 ) as in the released implementation [7]. For CQ, we derive fixed copy and local-balance parameters from the requested target 𝜌 ∗ /(1 + 𝜖) (Appendix C). The three static methods solve each query snapshot exactly from scratch and have no approximation parameter. We therefore report one mean per dataset, shared across the five 𝜖 rows. We set DI’s numerical flow tolerance to 10−8 and ExactFlow’s to 10−6 .

6.2

Efficiency on Dynamic Hypergraphs

We compare running times at 𝜖 ∈ {1, 0.7, 0.5, 0.2, 0.1}. CAP has the lowest running time in all 25 settings in Table 2, while meeting the requested approximation after every update. Against the dynamic baselines, it is 15.5–1869.2× faster than Udshp in the 15 completed native-parameter comparisons. Against CQ, the four completed comparisons yield 2343.5–5926.6× speedups. At 𝜖 = 0.1, both dynamic baselines have TL entries on every dataset, whereas CAP completes all five streams. Tightening 𝜖 from 1 to 0.1 raises CAP’s time by only 1.5–5.9× across these datasets. The advantage also holds against exact snapshot recomputation, despite the relatively sparse calendar queries. At 𝜖 = 0.1, CAP is 3.4–259.6× faster than DI and 5.4–246.9× faster than ExactFlow. The largest gains occur on GE, where repeatedly solving the query snapshots is expensive. Even on DW, which has only 32 queries, CAP is 41.2× faster than Exact. Retaining a valid solution therefore benefits both update-heavy streams and streams with expensive query snapshots.

6.3

Quality Validation

We check that the speedups preserve CAP’s required approximation. An independent integer-allocation observer tracks every update

Scalable Approximate Algorithm for Dynamic Densest Subhypergraphs with Solution-Guided Maintenance

Table 2: Average running time (s). TL: time limit. Dynamic methods Data

Static methods

𝜖 CAP

Udshp

CQ

1 0.7 0.5 0.2 0.1

0.24 0.32 0.35 0.55 0.84

13.52 46.19 168.60 TL TL

1448.21 TL TL TL TL

34.72

MA

1 0.7 0.5 0.2 0.1

0.28 0.33 0.37 0.69 1.59

14.22 47.27 159.40 TL TL

824.18 TL TL TL TL

54.19

AU

1 0.7 0.5 0.2 0.1

0.21 0.25 0.29 0.58 1.25

4.03 11.76 38.49 1079.61 TL

500.08 1112.02 TL TL TL

20.35

GE

1 0.7 0.5 0.2 0.1

2.47 2.43 2.48 3.10 3.70

38.34 57.40 103.25 935.33 TL

TL TL TL TL TL

TL

SO

1 0.7 0.5 0.2 0.1

11.94 13.22 12.52 18.90 36.44

1680.65 TL TL TL TL

TL TL TL TL TL

DW

Table 4: Average running time (s) with varying query counts. TL: time limit.

Exact

DI

ExactFlow

4.69

5.93

Queries

CAP

Udshp

CQ

Exact

DI

ExactFlow

DW

32 128 512

0.35 0.34 0.35

174.39 172.94 190.42

TL TL TL

33.37 72.92 231.53

4.62 11.42 39.30

8.86 22.53 74.20

GE

210 840 3,360

2.58 2.53 2.51

103.25 1107.58 TL

TL TL TL

TL TL TL

959.86 TL TL

912.67 TL TL

8.93

10.34

Table 5: Average running time with a size-only query after every update. CAP time (s) Data 4.26

959.86

TL

320.04

Updates / queries

6.76

912.67

484.23

DW MA AU GE SO

Data

1

0.7

0.5

0.2

0.1

0.01

DW MA AU GE SO

0.5846 0.5299 0.5475 0.5294 0.5627

0.6099 0.6223 0.6545 0.6120 0.6119

0.7150 0.7215 0.7012 0.6667 0.6987

0.8565 0.8776 0.9087 0.8333 0.8664

0.9324 0.9528 0.9483 0.9184 0.9394

0.9964 0.9961 0.9926 0.9913 0.9977

and checks edge mass, vertex loads, and the maintained solution density against 𝑈 = max 𝑞 𝑣 /𝑏. 𝑣

Its ledger is fully rescanned every 1,024 updates and at queries. All original-calendar validation trajectories pass. Table 3 further compares returned densities with exact maximum-closure optima at every calendar query; all tested dataset/accuracy combinations meet 1/(1 + 𝜖). The additional queries in Section 6.4 also meet their requested target. Thus, the runtime advantage is accompanied by validated solution quality, including between scheduled queries.

529,412 611,274 382,007 1,471,530 15,897,567

𝜖 = 0.1

𝜖 = 0.01

0.86 1.60 1.26 3.80 37.27

4.97 22.85 14.15 6.48 1586.63

We independently check every returned set from the complete CQ runs against exact snapshot optima; all meet the requested density ratio 1/(1 + 𝜖).

6.4

Table 3: Minimum CAP density divided by the exact optimum across complete validation trajectories. Column headings give 𝜖.

𝐿 ≤ 𝜌 ∗ ≤ 𝑈 ≤ (1 + 𝜖)𝐿,

Data

Scalability with Query Frequency

On DW and GE, we fix 𝜖 = 0.5 and use the query schedules in Section 6.1. Table 4 shows the results. Increasing query frequency sixteenfold leaves CAP’s running time almost unchanged on both datasets. The maintained solution makes each query an output operation, avoiding a new optimization or load-threshold search. With 512 queries on DW, CAP is 113.9– 671.1× faster than the three static methods and 551.9× faster than Udshp under its native parameter. On GE, only CAP completes at the highest frequency; the Udshp, CQ, and static-solver entries are all TL. These results show that explicitly maintaining the solution becomes particularly useful when queries are frequent. Reporting after every update. We further evaluate CAP on all five hypergraph datasets with 𝜖 ∈ {0.1, 0.01}. We keep every insertion and deletion unchanged and issue exactly one query immediately after each update. Each query returns only the current solution size |𝐶 |, using the maintained cardinality without enumerating its vertices. Thus, the number of queries equals the number of updates. Table 5 reports the total running time for maintenance and these size-only responses. At 𝜖 = 0.1, even the largest stream, SO, takes only 37.27 seconds for 15.9 million updates and responses. Stricter accuracy can make maintenance more expensive: at 𝜖 = 0.01, the same stream takes 1586.63 seconds, whereas GE still finishes in 6.48 seconds. The constant-time size query removes enumeration cost; it does not

80

100

1

Accuracy parameter ε

Retained vertices (%)

Figure 2: Average running time of CAP with varying data size (𝜖 = 0.1). The vertical axis is logarithmic.

Figure 3: Average running time with varying precision on GE. Arrows mark the 1,800-second whole-process limit.

remove the dataset-dependent cost of maintaining a more accurate solution.

6.6

CAP

Average running time (s)

6.5

Scalability with Data Size

We evaluate CAP on GE and SO, the two datasets with the largest peak numbers of active hyperedges, at 𝜖 = 0.1. For each dataset, we uniformly shuffle the vertex set with a fixed random seed and retain its first ⌊𝑘 |𝑉 |/100⌋ vertices for 𝑘 ∈ {20, 40, 60, 80, 100}. Each nested sample induces a stream containing exactly the original hyperedges whose endpoints all belong to the sample. We preserve their insertion/deletion order, the full calendar query schedule (including empty snapshots), and the original rank upper bound. Queries return full vertex sets. The 100% points reuse the complete measurements from Section 6.2. Figure 2 shows increasing running time as the samples grow, with CAP completing even the full SO stream in 36.44 seconds. From 20% to 100% vertex retention on SO, the update count grows 96.2× but running time grows only 38.7×. This behavior is consistent with maintenance that often processes updates locally, rather than rescanning the entire active hypergraph. Vertex-induced sampling changes both the edge set and its rank distribution, so the horizontal axis is a sampling fraction rather than a direct measure of input volume.

Effect of the Accuracy Parameter

We vary 𝜖 over 1, 0.7, 0.5, 0.2, 0.1, 0.08, 0.06, 0.04, 0.02, and 0.01 on GE, the dataset with the most vertices. Figure 3 shows that tightening accuracy by two orders of magnitude increases CAP’s time by only 2.6×. At 𝜖 = 0.01, it completes in 6.36 seconds and its minimum density ratio exceeds the required 1/1.01. In contrast, Udshp has TL entries from 𝜖 = 0.1 onward, and CQ already has TL at 𝜖 = 1. Even at the strictest setting, CAP remains 151.0× and 143.5× faster than DI and ExactFlow, respectively. Thus, high accuracy preserves a substantial advantage on this large hypergraph without requiring a proportional increase in running time. This robustness is dataset dependent: at 𝜖 = 0.01, DI is faster on DW, MA, and AU, and ExactFlow is faster on MA and AU.

1

60

10

0.5

40

100

1 0.7

20

ε ≤ 0.1

TL: 1,800 s

1000

0.0

0.1

CQ

2

1

Udshp

CQ: TL (ε ≤ 1)

0.0

10

CAP

0 0.0.1 8 0.0 6 0.0 4

SO

0.2

GE

Average running time (s)

Average running time (s)

Chen et al.

CAP-Tight >300 92.96

100 28.15

37.99

27.74

7.64

10

3.74 1.61

1

1.28

0.85

DW

MA

AU

GE

SO

Figure 4: Average running time in the ablation study (𝜖 = 0.1).

6.7

Ablation Study

We study witness-guided repair on DW, MA, AU, GE, and SO with 𝜖 = 0.1. We compare CAP’s outer capacity and reserve destinations (Section 4) with a tighter variant: • CAP: Outer capacity ⌊(1 + 𝜖)𝑏𝐿⌋; destinations have load below ⌊(1 + 𝜖/2)𝑏𝐿⌋. • CAP-Tight: Capacity ⌈𝑏𝐿⌉; any destination below that capacity is accepted. All completed runs meet the required approximation at every query. Figure 4 shows the combined benefit of the larger outer capacity and reserve destinations. CAP is 2.0–57.9× faster on the four datasets where both variants complete, with 3.6–158.0× fewer positiveincidence scans. On SO, CAP-Tight exceeds 300 seconds, while CAP completes. The lower scan counts are consistent with reduced repair work from the combined use of the larger outer capacity and reserve destinations.

6.8

Results on Ordinary Graphs

We also evaluate CAP on six ordinary graph streams with 𝜖 = 0.1. We compare it with ImprovedDynOpt [29] and INS/DEL [59], which maintain an optimal graph orientation and pseudoarboricity, respectively. We sum the recorded running times over the complete

Scalable Approximate Algorithm for Dynamic Densest Subhypergraphs with Solution-Guided Maintenance

Table 6: Average total running time (s) on ordinary graphs. Speedup is baseline time divided by CAP time. EM

Algorithm

WV

BC

AS

SW

Total time (s) 0.02 0.19 0.68 0.78 0.33 11.08

HT

CAP ImprovedDynOpt INS/DEL

0.03 0.08 0.73

0.11 0.30 0.15

1.61 1.52 6.04

5.24 4.53 334.62

ImprovedDynOpt INS/DEL

CAP speedup over each baseline 2.2× 29.3× 4.1× 2.7× 21.1× 14.2× 57.9× 1.4×

0.9× 3.7×

0.9× 63.8×

update stream, including the initial edge insertions. The measured cost includes CAP’s updates and the baselines’ updates plus scalar queries every 100 operations; CAP’s scalar reads and vertex enumeration are untimed. We check solution quality at sampled queries. Table 6 shows that CAP’s benefit extends to ordinary graphs: it is 1.4–63.8× faster than INS/DEL on all six streams and 2.2–29.3× faster than ImprovedDynOpt on four. The advantage is not universal: ImprovedDynOpt is modestly faster on AS and SW. Thus, CAP remains competitive with specialized graph implementations while supporting general hyperedges.

7

Conclusion

Witness-conditioned repair gives a unified way to maintain a certified dense set on graphs and hypergraphs. Its useful regime is described by certificate slack, actual deletion-induced scale loss, and positive residual support. The native-parameter experiments show substantial running-time savings against the released hypergraph implementation on the evaluated sources. Static recomputation remains competitive at fine precision on smaller streams. The ablation study shows that the combination of the larger outer capacity and reserve destinations reduces repair work on the evaluated hypergraphs.

Acknowledgments The authors thank Sergey Kudria for early discussions on the densest-subgraph problem in ordinary graphs.

AI Acknowledgment The authors acknowledge the use of OpenAI GPT Astra for assistance with literature search, algorithm and proof development, implementation, experimental orchestration, analysis, and manuscript drafting. The authors take full responsibility for the correctness of the mathematical claims and proofs, the experimental results, and all other content of this paper.

References [1] Reid Andersen. 2010. A local algorithm for finding dense subgraphs. ACM Transactions on Algorithms 6, 4, Article 60 (2010), 12 pages. doi:10.1145/1824777. 1824780 [2] Reid Andersen and Kumar Chellapilla. 2009. Finding Dense Subgraphs with Size Bounds. In Algorithms and Models for the Web-Graph. Springer Berlin Heidelberg, 25–37. doi:10.1007/978-3-540-95995-3_3 [3] Albert Angel, Nick Koudas, Nikos Sarkas, Divesh Srivastava, Michael Svendsen, and Srikanta Tirthapura. 2014. Dense subgraph maintenance under streaming

edge weight updates for real-time story identification. The VLDB Journal 23, 2 (2014), 175–199. doi:10.1007/s00778-013-0340-z [4] Federico Battiston, Giulia Cencetti, Iacopo Iacopini, Vito Latora, Maxime Lucas, Alice Patania, Jean-Gabriel Young, and Giovanni Petri. 2020. Networks beyond pairwise interactions: Structure and dynamics. Physics Reports 874 (2020), 1–92. doi:10.1016/j.physrep.2020.05.004 [5] Vedangi Bengali, Nikolaj Tatti, Iiro Kumpulainen, Florian Adriaens, and Nate Veldt. 2026. The Densest SWAMP Problem: Subhypergraphs with Arbitrary Monotonic Partial Edge Rewards. In Machine Learning and Knowledge Discovery in Databases. Research Track (Lecture Notes in Computer Science, Vol. 16015). Springer Nature Switzerland, 75–91. doi:10.1007/978-3-032-06066-2_5 [6] Austin R. Benson, Rediet Abebe, Michael T. Schaub, Ali Jadbabaie, and Jon Kleinberg. 2018. Simplicial closure and higher-order link prediction. Proceedings of the National Academy of Sciences 115, 48 (Nov. 2018), E11221–E11230. doi:10. 1073/pnas.1800683115 [7] Suman K. Bera, Sayan Bhattacharya, Jayesh Choudhari, and Prantar Ghosh. 2022. A New Dynamic Algorithm for Densest Subhypergraphs. In Proceedings of the ACM Web Conference 2022 (WWW ’22). ACM, 1093–1103. doi:10.1145/3485447. 3512158 [8] Edvin Berglin and Gerth Stølting Brodal. 2020. A Simple Greedy Algorithm for Dynamic Graph Orientation. Algorithmica 82, 2 (2020), 245–259. doi:10.1007/ s00453-018-0528-0 [9] Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Charalampos Tsourakakis. 2015. Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC ’15). ACM, 173–182. doi:10.1145/2746539.2746592 [10] Yuly Billig. 2025. Eigenvalue Approach to Dense Clusters in Hypergraphs. Journal of Graph Theory 109, 3 (2025), 353–365. doi:10.1002/jgt.23218 [11] Digvijay Boob, Yu Gao, Richard Peng, Saurabh Sawlani, Charalampos Tsourakakis, Di Wang, and Junxing Wang. 2020. Flowless: Extracting Densest Subgraphs Without Flow Computations. In Proceedings of The Web Conference 2020 (WWW ’20). ACM, 573–583. doi:10.1145/3366423.3380140 [12] Jannick Borowitz, Ernestine Großmann, and Christian Schulz. 2023. Engineering Fully Dynamic Δ-Orientation Algorithms. In SIAM Conference on Applied and Computational Discrete Algorithms (ACDA23). Society for Industrial and Applied Mathematics, 25–37. doi:10.1137/1.9781611977714.3 [13] Lijun Chang and Miao Qiao. 2020. Deconstruct Densest Subgraphs. In Proceedings of The Web Conference 2020 (WWW ’20). ACM, 2747–2753. doi:10.1145/3366423. 3380033 [14] Moses Charikar. 2000. Greedy Approximation Algorithms for Finding Dense Components in a Graph. In Approximation Algorithms for Combinatorial Optimization (Lecture Notes in Computer Science, Vol. 1913), Klaus Jansen and Samir Khuller (Eds.). Springer Berlin Heidelberg, 84–95. doi:10.1007/3-540-44436-X_10 [15] Chandra Chekuri, Aleksander Bjørn Christiansen, Jacob Holm, Ivor van der Hoog, Kent Quanrud, Eva Rotenberg, and Chris Schwiegelshohn. 2024. Adaptive Out-Orientations with Applications. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 3062–3088. doi:10.1137/1.9781611977912.110 [16] Chandra Chekuri, Kent Quanrud, and Manuel R. Torres. 2022. Densest Subgraph: Supermodularity, Iterative Peeling, and Flow. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 1531–1555. doi:10.1137/1.9781611977073.64 [17] Jie Chen and Yousef Saad. 2012. Dense Subgraph Extraction with Application to Community Detection. IEEE Transactions on Knowledge and Data Engineering 24, 7 (2012), 1216–1230. doi:10.1109/tkde.2010.271 [18] Aleksander Bjørn Christiansen, Ivor van der Hoog, and Eva Rotenberg. 2025. Local Density and Its Distributed Approximation. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 327), Olaf Beyersdorff, Michał Pilipczuk, ˜ Kim Thăng ´ (Eds.). Schloss Dagstuhl – LeibnizElaine Pimentel, and Nguyên Zentrum für Informatik, Dagstuhl, Germany, 25:1–25:20. doi:10.4230/LIPIcs. STACS.2025.25 [19] Yizhou Dai, Miao Qiao, and Lijun Chang. 2022. Anchored Densest Subgraph. In Proceedings of the 2022 International Conference on Management of Data (SIGMOD/PODS ’22). ACM, 1200–1213. doi:10.1145/3514221.3517890 [20] Maximilien Danisch, T.-H. Hubert Chan, and Mauro Sozio. 2017. Large Scale Density-friendly Graph Decomposition via Convex Programming. In Proceedings of the 26th International Conference on World Wide Web (WWW ’17). International World Wide Web Conferences Steering Committee, 233–242. doi:10.1145/3038912. 3052619 [21] Alessandro Epasto, Silvio Lattanzi, and Mauro Sozio. 2015. Efficient Densest Subgraph Computation in Evolving Graphs. In Proceedings of the 24th International Conference on World Wide Web (WWW ’15). International World Wide Web Conferences Steering Committee, 300–310. doi:10.1145/2736277.2741638 [22] Yixiang Fang, Wensheng Luo, and Chenhao Ma. 2022. Densest subgraph discovery on large graphs: applications, challenges, and techniques. Proceedings of the

Chen et al.

VLDB Endowment 15, 12 (2022), 3766–3769. doi:10.14778/3554821.3554895 [23] Yixiang Fang, Kaiqiang Yu, Reynold Cheng, Laks V. S. Lakshmanan, and Xuemin Lin. 2019. Efficient algorithms for densest subgraph discovery. Proceedings of the VLDB Endowment 12, 11 (2019), 1719–1732. doi:10.14778/3342263.3342645 [24] Wenjie Feng, Shenghua Liu, Danai Koutra, and Xueqi Cheng. 2024. Unified Dense Subgraph Detection: Fast Spectral Theory Based Algorithms. IEEE Transactions on Knowledge and Data Engineering 36, 3 (2024), 1356–1370. doi:10.1109/tkde. 2023.3272574 [25] Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao. 2019. Hypergraph Neural Networks. Proceedings of the AAAI Conference on Artificial Intelligence 33, 01 (2019), 3558–3565. doi:10.1609/aaai.v33i01.33013558 [26] Eugene Fratkin, Brian T. Naughton, Douglas L. Brutlag, and Serafim Batzoglou. 2006. MotifCut: regulatory motifs finding with maximum density subgraphs. Bioinformatics 22, 14 (2006), e150–e157. doi:10.1093/bioinformatics/btl243 [27] Aristides Gionis and Charalampos E. Tsourakakis. 2015. Dense Subgraph Discovery: KDD 2015 Tutorial. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’15). ACM, 2313–2314. doi:10.1145/2783258.2789987 [28] Ernestine Grossmann, Henrik Reinstädtler, Eva Rotenberg, Christian Schulz, Ivor van der Hoog, and Juliette Vlieghe. 2025. From Theory to Practice: Engineering Approximation Algorithms for Dynamic Orientation. In 33rd Annual European Symposium on Algorithms (ESA 2025) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 351), Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman (Eds.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 65:1–65:18. doi:10.4230/LIPIcs.ESA.2025.65 [29] Ernestine Großmann, Henrik Reinstädtler, Christian Schulz, and Fabian Walliser. 2025. Engineering Fully Dynamic Exact Δ-Orientation Algorithms. In 2025 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics, 15–28. doi:10.1137/ 1.9781611978339.2 [30] Elfarouk Harb, Kent Quanrud, and Chandra Chekuri. 2022. Faster and Scalable Algorithms for Densest Subgraph and Decomposition. In Advances in Neural Information Processing Systems 35 (NeurIPS 2022). Neural Information Processing Systems Foundation, Inc. (NeurIPS), 26966–26979. doi:10.52202/068431-1955 [31] Bryan Hooi, Hyun Ah Song, Alex Beutel, Neil Shah, Kijung Shin, and Christos Faloutsos. 2016. FRAUDAR: Bounding Graph Fraud in the Face of Camouflage. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’16). ACM, 895–904. doi:10.1145/2939672. 2939747 [32] Shuguang Hu, Xiaowei Wu, and T-H. Hubert Chan. 2017. Maintaining Densest Subsets Efficiently in Evolving Hypergraphs. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management (CIKM ’17). ACM, 929–938. doi:10.1145/3132847.3132907 [33] Yufan Huang, David F. Gleich, and Nate Veldt. 2024. Densest Subhypergraph: Negative Supermodular Functions and Strongly Localized Methods. In Proceedings of the ACM Web Conference 2024 (WWW ’24). ACM, 881–892. doi:10.1145/3589334.3645624 [34] Samir Khuller and Barna Saha. 2009. On Finding Dense Subgraphs. In Automata, Languages and Programming. Springer Berlin Heidelberg, 597–608. doi:10.1007/ 978-3-642-02927-1_50 [35] Steffen Klamt, Utz-Uwe Haus, and Fabian Theis. 2009. Hypergraphs and Cellular Networks. PLOS Computational Biology 5, 5 (2009), e1000385. doi:10.1371/journal. pcbi.1000385 [36] Tommaso Lanciano, Atsushi Miyauchi, Adriano Fazzone, and Francesco Bonchi. 2024. A Survey on the Densest Subgraph Problem and its Variants. Comput. Surveys 56, 8 (2024), 1–40. doi:10.1145/3653298 [37] Xiaoyu Leng, Hongchao Qin, and Rong-Hua Li. 2026. Density Decomposition on Hypergraphs. arXiv:2604.07794 [cs.SI] doi:10.48550/arxiv.2604.07794 [38] Luocheng Liang, Yingli Zhou, and Yixiang Fang. 2026. Accelerated Coordinate Descent for Directed Densest Subgraph Discovery. In Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1. ACM, 783–794. doi:10.1145/3770854.3780186 [39] Xuanming Liu, Tingjian Ge, and Yinghui Wu. 2022. A Stochastic Approach to Finding Densest Temporal Subgraphs in Dynamic Graphs. IEEE Transactions on Knowledge and Data Engineering 34, 7 (2022), 3082–3094. doi:10.1109/tkde.2020. 3025463 [40] Wensheng Luo, Chenhao Ma, Yixiang Fang, and Laks V. S. Lakshmanan. 2023. A Survey of Densest Subgraph Discovery on Large Graphs. doi:10.48550/ARXIV. 2306.07927 [41] Wensheng Luo, Zhuo Tang, Yixiang Fang, Chenhao Ma, and Xu Zhou. 2023. Scalable Algorithms for Densest Subgraph Discovery. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 287–300. doi:10.1109/icde55515. 2023.00029 [42] Chenhao Ma, Yixiang Fang, Reynold Cheng, Laks V. S. Lakshmanan, Xiaolin Han, and Xiaodong Li. 2024. Accelerating directed densest subgraph queries with software and hardware approaches. The VLDB Journal 33, 1 (2024), 207–230. doi:10.1007/s00778-023-00805-0

[43] Chenhao Ma, Yixiang Fang, Reynold Cheng, Laks V. S. Lakshmanan, Wenjie Zhang, and Xuemin Lin. 2021. On Directed Densest Subgraph Discovery. ACM Transactions on Database Systems 46, 4, Article 13 (2021), 45 pages. doi:10.1145/ 3483940 [44] Muhammad Anis Uddin Nasir, Aristides Gionis, Gianmarco De Francisci Morales, and Sarunas Girdzijauskas. 2017. Fully Dynamic Algorithm for Top-k Densest Subgraphs. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management (CIKM ’17). ACM, 1817–1826. doi:10.1145/3132847. 3132966 [45] Lu Qin, Rong-Hua Li, Lijun Chang, and Chengqi Zhang. 2015. Locally Densest Subgraph Discovery. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’15). ACM, 965–974. doi:10.1145/2783258.2783299 [46] Barna Saha, Allison Hoch, Samir Khuller, Louiqa Raschid, and Xiao-Ning Zhang. 2010. Dense Subgraphs with Restrictions and Applications to Gene Annotation Graphs. In Research in Computational Molecular Biology. Springer Berlin Heidelberg, 456–472. doi:10.1007/978-3-642-12683-3_30 [47] Saurabh Sawlani and Junxing Wang. 2020. Near-optimal fully dynamic densest subgraph. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC ’20). ACM, 181–193. doi:10.1145/3357713.3384327 [48] Pattara Sukprasert, Quanquan C. Liu, Laxman Dhulipala, and Julian Shun. 2024. Practical Parallel Algorithms for Near-Optimal Densest Subgraphs on Massive Graphs. In 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics, 59–73. doi:10.1137/1.9781611977929.5 [49] Nikolaj Tatti. 2019. Density-Friendly Graph Decomposition. ACM Transactions on Knowledge Discovery from Data 13, 5, Article 54 (2019), 29 pages. doi:10.1145/ 3344210 [50] Tran Ba Trung, Lijun Chang, Nguyen Tien Long, Kai Yao, and Huynh Thi Thanh Binh. 2023. Verification-Free Approaches to Efficient Locally Densest Subgraph Discovery. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 1–13. doi:10.1109/icde55515.2023.00008 [51] Charalampos Tsourakakis. 2015. The K-clique Densest Subgraph Problem. In Proceedings of the 24th International Conference on World Wide Web (WWW ’15). International World Wide Web Conferences Steering Committee, 1122–1132. doi:10.1145/2736277.2741098 [52] Elena Valari, Maria Kontaki, and Apostolos N. Papadopoulos. 2012. Discovery of Top-k Dense Subgraphs in Dynamic Graph Collections. In Scientific and Statistical Database Management. Springer Berlin Heidelberg, 213–230. doi:10.1007/978-3642-31235-9_14 [53] V. Venkateswaran. 2004. Minimizing maximum indegree. Discrete Applied Mathematics 143, 1-3 (Sept. 2004), 374–378. doi:10.1016/j.dam.2003.07.007 [54] Xiaojia Xu, Haoyu Liu, Xiaowei Lv, Yongcai Wang, and Deying Li. 2024. An Efficient and Exact Algorithm for Locally h-Clique Densest Subgraph Discovery. Proceedings of the ACM on Management of Data 2, 6 (2024), 1–26. doi:10.1145/ 3698800 [55] Yichen Xu, Chenhao Ma, Yixiang Fang, and Zhifeng Bao. 2024. Efficient and effective algorithms for densest subgraph discovery and maintenance. The VLDB Journal 33, 5 (2024), 1427–1452. doi:10.1007/s00778-024-00855-y [56] Yi Yang, Chenhao Ma, Reynold Cheng, Laks V. S. Lakshmanan, and Xiaolin Han. 2026. Finding Locally Densest Subgraphs: Convex Programming with Edge and Triangle Density. The VLDB Journal 35, 1, Article 7 (2026). doi:10.1007/s00778025-00958-0 [57] Qi Zhang, Rong-Hua Li, Yalong Zhang, Hongchao Qin, and Guoren Wang. 2025. Density decomposition on large static and dynamic graphs: algorithms and applications. The VLDB Journal 34, 6, Article 63 (2025). doi:10.1007/s00778-02500942-8 [58] Qi Zhang, Yalong Zhang, Rong-Hua Li, and Guoren Wang. 2024. Approximate Anchored Densest Subgraph Search on Large Static and Dynamic Graphs. Proceedings of the VLDB Endowment 18, 3 (2024), 623–636. doi:10.14778/3712221.3712230 [59] Yalong Zhang, Rong-Hua Li, Qi Zhang, Hongchao Qin, Lu Qin, and Guoren Wang. 2024. Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs. Proceedings of the VLDB Endowment 17, 11 (July 2024), 2722–2734. doi:10.14778/3681954.3681958 [60] Yingli Zhou, Qingshuo Guo, and Yixiang Fang. 2025. Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory. Proceedings of the VLDB Endowment 18, 10 (2025), 3490–3503. doi:10.14778/3748191.3748210 [61] Yingli Zhou, Qingshuo Guo, Yixiang Fang, and Chenhao Ma. 2024. A Countingbased Approach for Efficient k-Clique Densest Subgraph Discovery. Proceedings of the ACM on Management of Data 2, 3, Article 119 (2024), 27 pages. doi:10.1145/ 3654922 [62] Yingli Zhou, Qingshuo Guo, Yi Yang, Yixiang Fang, Chenhao Ma, and Laks V. S. Lakshmanan. 2024. In-Depth Analysis of Densest Subgraph Discovery in a Unified Framework. Proceedings of the VLDB Endowment 18, 4 (2024), 1131–1144. doi:10.14778/3717755.3717771 [63] Yingli Zhou, Taohua Huang, and Yixiang Fang. 2026. Efficient Locally h-Clique Densest Subgraph Discovery via Divide-and-Conquer. Proceedings of the VLDB Endowment 19, 10 (2026), 2577–2590. doi:10.14778/3828612.3828616

Scalable Approximate Algorithm for Dynamic Densest Subhypergraphs with Solution-Guided Maintenance

[64] Yingli Zhou, Luocheng Liang, and Yixiang Fang. 2025. Efficient and Scalable Directed Densest Subgraph Discovery. Proceedings of the ACM on Management of Data 3, 6, Article 320 (2025), 27 pages. doi:10.1145/3769785 [65] Yingli Zhou, Youran Sun, and Yixiang Fang. 2026. Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance. Proceedings of the ACM on Management of Data 4, 3, Article 167 (2026), 27 pages. doi:10.1145/3802044

A

(𝑞𝑧 − 𝑎𝑠 ) 2 − (𝑞𝑧 − 𝑎 − 𝑎𝑠 ) 2 = 2𝑎(𝑞𝑧 − 𝑎 − 𝑎𝑠 ) + 𝑎 2 ≥ 2𝑎(𝑐 − 𝑎𝑠 ) + 𝑎 2 . Subtracting the destination’s increase and dividing by 𝑠 leaves at least 2𝑎(1 − 𝛽) = 𝛿𝑎. □

Transport Bounds and Supporting Derivations

We collect the proofs of the search-work and transport bounds, using the notation of Sections 5.1 and 5.2. We also give the supporting update-charge inequalities and the degree-tail bound.

A.1

ends at 𝑞𝑧 − 𝑎 ≥ 𝑐. Since 𝑐 − 𝑎𝑠 ≥ (𝑠 − 1) − (𝛽𝑠 − 1) = (1 − 𝛽)𝑠 > 0, its decrease before division by 𝑠 is

Proof of the Local Search-Work Bound

Proof of Lemma 5.3. Consider one search and set 𝐻 = {𝑣 : 𝑏 deg(𝑣) ≥ 𝑡 }, so |𝐻 | ≤ ℎ. Let 𝑃 count inspected positive incidences, 𝐸 distinct expanded hyperedges, and 𝐽 endpoint tests. All expanded vertices have load at least 𝑡 and belong to 𝐻 . Each positive incidence carries at least one integer unit, so their total number is bounded by the sum of loads over 𝐻 . Also, every expanded edge consumes an inspected incidence. Therefore 𝑃 ≤ ℎ𝑄 and 𝐸 ≤ 𝑃. A fully expanded edge contains only vertices of load at least 𝑡: otherwise the search would have stopped at an eligible destination. Such an edge lies in 𝐻 and has at most min{𝑟, ℎ} endpoints. The last edge of a successful search may leave 𝐻 , but scanning it stops at the first lower-load endpoint. If 𝜎 indicates success, these observations give 𝐽 ≤ min{𝑟, ℎ}𝐸 + 𝜎,

Each unit transported thus releases at least 𝛿 units of potential. This converts a sequence of repairs into an accounting of the potential introduced by updates. Convex load potentials have precedent [18]; here the scale follows the maintained solution and can decrease after a deletion. A.2.2 Properties of the Shifted Potential. Write 𝑎𝑠 = 𝛽𝑠 − 1. From 𝑏𝐿 ≥ 2/𝜖, we obtain 𝑠≥

2(1 + 𝜖) 2 = , 𝜖 𝛿

𝑎𝑠 = (1 + 𝜖/2)𝑏𝐿 − 1 ≥

2 . 𝜖

In particular, 𝑎𝑠 ≥ 0 and 1/𝑠 ≤ 𝛿/2. For 𝑞 > 𝑎𝑠 , the derivative of (𝑞 − 𝑎𝑠 ) 2 /𝑞 is 1 − 𝑎𝑠2 /𝑞 2 ≥ 0. For 𝑞 ≤ 𝑎𝑠 , its positive-part version is zero. Consequently, for every stable load 0 < 𝑞 ≤ 𝑐 ≤ 𝑠, (𝑞 − 𝑎𝑠 )+2 (𝑠 − 𝑎𝑠 ) 2 ≤ = (1 − 𝛽 + 1/𝑠) 2 . 𝑠𝑞 𝑠2 Í Summing over vertices and using 𝑣 𝑞 𝑣 = 𝑏𝑚 gives Φ𝑠 (𝑞) ≤ (1 − 𝛽 + 1/𝑠) 2𝑏𝑚 ≤ 𝛿 2𝑏𝑚.

(A.2)

𝑃 + 𝐽 ≤ (1 + min{𝑟, ℎ})ℎ𝑄 + 𝜎.

The last inequality uses 1 − 𝛽 = 𝛿/2. We also need monotonicity in the witness scale. For a fixed load 𝑞, an active summand satisfies

Let 𝐾 be the number of successful searches. Summing over all 𝐾 + 𝐹 searches yields

(𝑞 + 1) 2 𝜕 (𝑞 + 1 − 𝛽𝑠) 2 =− + 𝛽 2 < 0. 𝜕𝑠 𝑠 𝑠2

𝑆 scan ≤ (1 + min{𝑟, ℎ})ℎ𝑄 (𝐾 + 𝐹 ) + 𝐾 . Each successful transfer moves a positive integer amount, so 𝐾 ≤ 𝐴, which proves Equation (8). □

An inactive summand is zero, and the two pieces meet continuously with zero derivative. Thus increasing 𝑠 with the allocation fixed cannot increase potential, including when a coordinate becomes inactive.

A.2

A.2.3

Proof of the Transport Bound

A.2.1 Potential Decrease under a Transfer. Set 𝛿 = 𝜖/𝛼, so that 𝑐 = ⌊𝑠⌋, 𝑡 = ⌊𝛽𝑠⌋, and 1 − 𝛽 = 𝛿/2. We use the potential 1 ∑︁ Φ𝑠 (𝑞) = (𝑞 𝑣 − 𝛽𝑠 + 1)+2 , (𝑥)+ = max{𝑥, 0}, 𝑠 𝑣 and assign potential zero to an empty state. It charges only loads above 𝛽𝑠 − 1, quadratically in their excess. An eligible destination has 𝑞 𝑤 < 𝑡 and contributes zero before the transfer. The shift by one handles integer rounding. Lemma A.1 (Potential decrease of a reserve transfer). At a fixed scale 𝑠, a successful reserve path of amount 𝑎 satisfies Φ𝑠 (𝑞 before ) − Φ𝑠 (𝑞 after ) ≥ 𝛿𝑎.

(A.1)

Proof of Lemma A.1. Write 𝑎𝑠 = 𝛽𝑠 − 1. Only the root 𝑧 and destination 𝑤 change their loads. An eligible integer destination satisfies 𝑞 𝑤 ≤ 𝑡 − 1 ≤ 𝑎𝑠 , so its initial contribution is zero and its final unscaled contribution is at most 𝑎 2 . By Equation (4), the root

(A.3)

Single-Update Charges.

Lemma A.2 (Insertion charge). A complete insertion transports at most 𝑏 units and increases the stable potential by at most 2𝛿𝑏. This bounds both effects of an insertion: the repair performed now and the potential it can leave for later repairs. Since an inserted edge adds exactly 𝑏 units, the first bound is independent of the number of other edges in the graph. Proof of Lemma A.2. Let 𝑠𝑖 and 𝑠 𝑓 be the initial and final scales. An insertion cannot decrease witness density, so 𝑠 𝑓 ≥ 𝑠𝑖 when the initial state is nonempty. Fix 𝑠 𝑓 throughout this argument and define ℎ(𝑞) =

(𝑞 − 𝛽𝑠 𝑓 + 1)+2 . 𝑠𝑓

Extend it above 𝑠 𝑓 by its tangent: ( ℎ(𝑞), 𝑞 ≤ 𝑠𝑓 , 𝑔(𝑞) = ℎ(𝑠 𝑓 ) + ℎ ′ (𝑠 𝑓 )(𝑞 − 𝑠 𝑓 ), 𝑞 > 𝑠 𝑓 .

Chen et al.

The tangent extension 𝑔 is convex and nondecreasing. Its derivative increases up to ℎ ′ (𝑠 𝑓 ) and is constant thereafter, so it is globally Lipschitz with constant 𝜅 = 2(1 − 𝛽 + 1/𝑠 𝑓 ) ≤ 2𝛿. The new edge adds nonnegative amounts summing to 𝑏. Their total Í increase in 𝑣 𝑔(𝑞 𝑣 ) is therefore at most 𝜅𝑏. Every subsequent transfer obeys 𝑞𝑧 − 𝑎 ≥ 𝑐 ≥ 𝑞 𝑤 + 𝑎. For a convex function, transferring 𝑎 from the larger coordinate towards the smaller under this condition gives 𝑔(𝑞𝑧 − 𝑎) + 𝑔(𝑞 𝑤 + 𝑎) ≤ 𝑔(𝑞𝑧 ) + 𝑔(𝑞 𝑤 ). Thus transfers can only decrease the sum, and witness changes leave it unchanged because the allocation is fixed. Initial and final loads are at most 𝑠 𝑓 , where 𝑔 = ℎ. Writing these vectors as 𝑞𝑖 , 𝑞 𝑓 , respectively, yields Φ𝑠 𝑓 (𝑞 𝑓 ) ≤ Φ𝑠 𝑓 (𝑞𝑖 ) + 2𝛿𝑏 ≤ Φ𝑠𝑖 (𝑞𝑖 ) + 2𝛿𝑏. The second inequality follows from Equation (A.3). For an initially empty graph, 𝑞𝑖 = 0 and 𝑔(0) = 0, giving the same bound from initial potential zero. This argument depends on the total inserted mass 𝑏, so it also covers mixed edge sizes. For transport, the old loads satisfy the old capacity and insertion never lowers that capacity. Adding 𝑏 units can create at most 𝑏 units of excess. Each successful path reduces excess by its amount (Lemma 4.1); later capacity increases cannot create excess. Total insertion transport is at most 𝑏. □

The second step uses 𝑞e𝑣 + 2 ≤ 𝑠 old + 2. If 𝑠 0 ≥ 𝑠 old instead, scale monotonicity gives an increase of at most zero, agreeing with 𝑍𝑑 = 0. After normalization, every witness replacement or peeling refresh can only increase the scale. Each successful reserve transfer reduces potential by at least 𝛿 times its amount (Lemma A.1). Adding these changes to the removal and scale-change bounds proves Equation (A.4). □ A.2.4 Summing the Update Charges. Insertions add only bounded potential, while the exposure charge 𝑍𝑑 bounds the increase caused by lowering the scale after a deletion. These charges pay for all transport in the sequence. Proof of Lemma 5.4. An insertion transports at most 𝑏 and increases stable potential by at most 2𝛿𝑏. A deletion transporting 𝐴𝑑 units satisfies 𝛿𝐴𝑑 ≤ 𝑏𝑍𝑑 + Φbefore − Φafter . These single-update inequalities are proved in Lemmas A.2 and A.3. Let 𝐴+ and 𝐴 − be transport over insertions and deletions, respectively, and Φ 𝑓 the final stable potential. Starting from empty gives initial potential zero. Summing the deletion inequalities cancels intermediate potentials except for the increases at insertions, yielding ∑︁ 𝛿𝐴 − ≤ 𝑏 𝑍𝑑 − Φ 𝑓 + 2𝛿𝑏𝑁 + . 𝑑

Lemma A.3 (Deletion charge). A deletion 𝑑 with reserve destinations satisfies 𝛿𝐴𝑑 ≤ 𝑏𝑍𝑑 + Φbefore − Φafter,

(A.4)

Since Φ 𝑓 ≥ 0 and 𝐴+ ≤ 𝑏𝑁 + , we obtain 𝑏 ∑︁ 𝐴 ≤ 3𝑏𝑁 + + 𝑍𝑑 . 𝛿 𝑑

where 𝐴𝑑 is the transport during that deletion.

Now use 𝑏 = 𝑂 (𝑟 /𝜖) and 1/𝛿 = (1 + 𝜖)/𝜖 = 𝑂 (1/𝜖).

The repair is paid for by two sources: the new exposure charge 𝑏𝑍𝑑 and a decrease in stored potential. The bound accounts for both in the same inequality, allowing the potential changes to cancel when we sum over consecutive updates. Proof of Lemma A.3. Removing the edge decreases every affected load, so it cannot increase potential at the old scale. If the graph becomes empty, there is no transport and the final potential is zero, proving the inequality. Otherwise the raw post-removal vector 𝑞e satisfies 𝑞e𝑣 ≤ 𝑠 old for every vertex. First consider 𝑠 0 < 𝑠 old . Both endpoints of this scale interval are normalized, so 𝛽𝑢 ≥ 1 for 𝑠 0 ≤ 𝑢 ≤ 𝑠 old . On an active coordinate, Equation (A.3) gives −

(𝑞 + 1) 2 𝑞(𝑞 + 2) 𝜕 (𝑞 + 1 − 𝛽𝑢) 2 = − 𝛽2 ≤ . 𝜕𝑢 𝑢 𝑢2 𝑢2

The last step uses 1/𝑢 2 ≤ 𝛽 2 . A coordinate can activate on this interval only if it belongs to 𝐽𝑑 = {𝑣 : 𝑞e𝑣 + 1 > 𝛽𝑠 0 }. Integrating also accounts for coordinates that are initially inactive:   1 1 ∑︁ Φ𝑠0 (e 𝑞 ) − Φ𝑠old (e 𝑞) ≤ − 𝑞e𝑣 (e 𝑞 𝑣 + 2) 𝑠 0 𝑠 old 𝑣 ∈ 𝐽 𝑑   ∑︁  2 𝑠 old −1 𝑞e𝑣 ≤ 1+ 𝑠 old 𝑠0 𝑣∈𝐽 𝑑

= 𝑏𝑍𝑑 .

A.3

□

Boundary States and Witness Destruction

We now sum the insertion and deletion charges. The intermediate potentials cancel, leaving only the initial and final stable states. Lemma A.4 (Transport with boundary potentials). Starting from an empty or normalized certified state with 𝑏 ≥ ⌈2𝑟 /𝜖⌉ and 0 < 𝜖 ≤ 1, let 𝑁 + be the number of insertions and Φ0, Φ 𝑓 the initial and final stable potentials. Set the potential of an empty state to zero. Total transport satisfies Í Φ0 − Φ 𝑓 + 𝑏 𝑑 𝑍 𝑑 𝐴 ≤ 3𝑏𝑁 + + . 𝛿 In an 𝑟 -uniform hypergraph, deleting the sole induced edge of a normalized witness contributes zero exposure. Proof of Lemma A.4. Let 𝐴+ and 𝐴 − be transport summed over insertions and deletions. By Lemma A.2, 𝐴+ ≤ 𝑏𝑁 + , and the sum of potential increases over insertions is at most 2𝛿𝑏𝑁 + . The sum of all update-wise potential changes is Φ 𝑓 − Φ0 . Summing Equation (A.4) therefore gives ∑︁ ∑︁ 𝛿𝐴 − ≤ 𝑏 𝑍𝑑 − (Φafter − Φbefore ) 𝑑

≤𝑏

∑︁ 𝑑

𝑑

𝑍𝑑 + Φ0 − Φ 𝑓 + 2𝛿𝑏𝑁 + .

Scalable Approximate Algorithm for Dynamic Densest Subhypergraphs with Solution-Guided Maintenance

Adding 𝐴+ ≤ 𝑏𝑁 + and dividing the deletion bound by 𝛿 proves the stated 3𝑏𝑁 + bound. It retains both boundary potentials and applies to every finite prefix of the update sequence. In an 𝑟 -uniform hypergraph, a one-edge witness has size 𝑘 ≥ 𝑟 , while normalization gives 1/𝑘 ≥ 1/𝑟 . Hence 𝑘 = 𝑟 and its old density is exactly 1/𝑟 . Any surviving edge supplies at least this density, so replacing a destroyed witness cannot lower the scale. An empty result has zero exposure by definition. □ Exposure is confined to a degree tail because 𝑞e𝑣 ≤ 𝑏 degafter (𝑣). For destruction in mixed ranks, if the old witness has size 𝑘 and the fallback edge has size 𝑓 , then 𝑠 old /𝑠 0 ≤ 𝑓 /𝑘; in particular, 𝑓 ≤ 𝑘 gives zero exposure. Thus the charge depends on the exposed degree tail and the drop in witness density. Combining its transport bound with Equation (8) bounds the associated search work. The new charge need not be smaller on every destructive deletion: one may replace 𝑍𝑑 there by min{𝑍𝑑 , 𝛿 (1+𝛿)𝑚 after }, using the old excess and stable-potential bounds before telescoping. Indeed, after removal there are 𝑏𝑚 after units in total and capacity only increases during repair, so 𝐴𝑑 ≤ 𝑏𝑚 after . The final state satisfies Φafter ≤ 𝛿 2𝑏𝑚 after , while Φbefore ≥ 0. Consequently 𝛿𝐴𝑑 + Φafter − Φbefore ≤ 𝛿 (1 + 𝛿)𝑏𝑚 after . Both this inequality and the 𝑏𝑍𝑑 bound concern the same deletion and the same endpoint potentials, so their right-hand sides may be minimized before summing. An empty result has 𝑚 after = 0.

A.4

A Degree-Tail Specialization

The exposure bound gives a more explicit guarantee when few vertices have degree near the repair threshold. Consider an internal deletion whose old witness has 𝑀 ≥ 2 edges and 𝑘 vertices. Set 𝑀 ′ = 𝑀 − 1, 𝑠 = 𝑠 old = 𝛼𝑏𝑀/𝑘, and 𝑠 ′ = 𝛼𝑏𝑀 ′ /𝑘. Let 𝐻𝑑 = {𝑣 : 𝑏 degafter (𝑣) > 𝛽𝑠 ′ − 1}. Normalization ensures 𝑠 0 ≥ 𝑠 ′ , so every coordinate contributing to 𝑍𝑑 lies in 𝐻𝑑 . Moreover, 𝑠/𝑠 0 − 1 ≤ 1/𝑀 ′ and 𝑞e𝑣 ≤ 𝑠. Hence |𝐻𝑑 | 𝑠 +2 |𝐻𝑑 | ≤ 2(1 + 2𝜖) . 𝑏𝑀 ′ 𝑘 The last step uses 𝑀/𝑀 ′ ≤ 2 and 1/𝑠 ≤ 𝛿/2. 𝑍𝑑 ≤

deletion, Equation (A.5) gives 𝑍𝑑 = 𝑂 (𝜂). Substitute their sum in Lemma A.4, drop Φ 𝑓 ≥ 0, and use 1/𝛿 = (1 + 𝜖)/𝜖 = 𝑂 (1/𝜖). □ For mixed ranks, the same bound retains the additional term Í (𝑏/𝛿) 𝑑:𝑀𝑑 =1 𝑍𝑑 for witness destruction. The degree-tail condition permits many low-degree vertices; it concerns the degree threshold at each deletion and need not follow from a fitted power-law exponent. This is a transport bound; search and endpoint costs are incorporated in Section 5.3.

B

Search Counts and Complete Time Accounting

We first bound the number of searches over an update sequence, then add the costs of normalization, heap maintenance, and occasional peeling. Throughout this subsection, ℎ bounds the high-load region at every search and I = 𝐼 denotes the active incidence volume. Making the search count explicit. Start from an empty state or a normalized certified state, and let 𝜌¯ ≥ 1/𝑟 bound the optimum over all states, including the initial state. Before an update, stability ¯ An insertion adds only 𝑏 units, while a deletion gives 𝑞 𝑣 ≤ 𝛼𝑏 𝜌. decreases loads. During repair, a transfer decreases the source load, leaves intermediate loads unchanged, and keeps its destination at ¯ Thus every search has 𝑄 ≤ 𝛼𝑏 𝜌¯ + 𝑏. For an internal most 𝑐 ≤ 𝛼𝑏 𝜌. deletion let 𝑀𝑑 , 𝑘𝑑 be the old witness’s edge count and size. Define ∑︁  𝑎𝑏  ∑︁   𝑎𝑏   𝑎𝑏   𝑉𝑎 = + − . 𝑘𝑑 𝑘𝑑 𝑟 𝑀 ≥2 𝑀 =1 𝑑

𝑑

The quantity 𝑉𝑎 bounds downward changes of the normalized integer target, assigning an empty state the artificial baseline ⌊𝑎𝑏/𝑟 ⌋. For nonempty states this target is ⌊𝑎𝑏𝐿⌋. The first sum covers a witness that loses one of several edges; the second covers loss of its sole edge and subsequent normalization or an empty state. For transport we need only decreases before nonempty repairs, since an emptying update requires no transport. We use 𝑉𝛼 for those outer capacity decreases and 𝑉𝛾 for the destination target.

(A.5)

Corollary A.5 (Uniform hypergraphs with a small degree tail). Consider an 𝑟 -uniform update sequence satisfying the assumptions of Lemma A.4. If |𝐻𝑑 | ≤ 𝜂|𝐶𝑑 | for every internal deletion that leaves an edge in its old witness, then   Φ0 𝑏𝜂 𝐴 = 𝑂 𝑏𝑁 + + + 𝑁− , 𝜖 𝜖 where 𝑁 − is the number of deletions and 𝐶𝑑 is the pre-deletion witness. In particular, the result applies to ordinary graphs (𝑟 = 2). For an empty start and 𝑏 = Θ(𝑟 /𝜖), the bound is 𝑂 ((𝑟 /𝜖)𝑁 + + (𝑟𝜂/𝜖 2 )𝑁 − ) units of transport. The parameter 𝜂 measures the size of the relevant degree tail relative to the witness, so this conclusion is useful when that ratio stays small throughout the sequence. Proof. External deletions leave the witness density unchanged. In a uniform hypergraph, destruction of a normalized one-edge witness has zero exposure by Lemma A.4. For every remaining

Lemma B.1 (Transport and failed-search counts). For CAP, if the high-load region has at most ℎ vertices at every search, then 𝐴 ≤ 𝑏𝑁 + + ℎ𝑉𝛼 , ¯ − ⌊𝛾𝑏/𝑟 ⌋ + 𝑉𝛾 . 𝐹 ≤ ⌊𝛾𝑏 𝜌⌋ The first bound charges successful transport to inserted mass and capacity decreases. The second charges failed searches to upward threshold progress: each failure increases the threshold, and only deletions can make that progress need to be repeated. Together they supply search counts for Equation (8). Proof of Lemma B.1. By Lemma A.2, insertion transport is at most 𝑏. For a deletion requiring repair, let 𝑐 old be its old capacity and 𝑐 start the capacity at its first search, after normalization and any initial peeling. Raw removal only decreases loads, so every load is at most 𝑐 old . At this first search, every overloaded vertex belongs to its high-load region, which contains at most ℎ vertices. The initial excess is therefore at most ℎ(𝑐 old −𝑐 start )+ . During repair, capacities only increase and each successful path reduces excess

Chen et al.

by its amount. This initial excess bounds all transport during the deletion. If 𝑀𝑑 ≥ 2, the old witness retains density (𝑀𝑑 − 1)/𝑘𝑑 before normalization. Subsequent normalization can only improve it. For any 𝑎 > 0, the threshold decrease is consequently at most

receiving shares, and its last for peeling: 𝑂 Π 0 + |𝐶 0 | + 𝑅up [log(𝑟 + 1) + log(𝑏 + 1) + log(𝑛 + 1)] + 𝑃 tot + 𝐽tot + 𝑍 norm + 𝐾 log(𝑛 + 1) ∑︁ + [(ℓ − 1) log(ℎ path + 1) + log(𝑟 + 1)]

(B.1)

paths













𝑎𝑏 (𝑀𝑑 − 1) 𝑎𝑏 𝑎𝑏𝑀𝑑 − ≤ . 𝑘𝑑 𝑘𝑑 𝑘𝑑

+ (𝑃 tot + 𝐷 0 )Λ . We justify each term in Equation (B.1) below.

This follows from ⌊𝑥⌋ − ⌊𝑥 − 𝑦⌋ ≤ ⌈𝑦⌉. If 𝑀𝑑 = 1 and an edge survives, normalization gives density at least 1/𝑟 , so the decrease is at most ⌊𝑎𝑏/𝑘𝑑 ⌋ − ⌊𝑎𝑏/𝑟 ⌋. This quantity is nonnegative since the old normalized witness has 𝑘𝑑 ≤ 𝑟 . External deletions do not decrease the witness density, and deletion of the last active edge requires no transport. Taking 𝑎 = 𝛼 and summing proves the bound on 𝐴. For failed searches, define 𝑡 ∗ = ⌊𝛾𝑏/𝑟 ⌋ and track 𝜏 = 𝑡 in nonempty states and 𝜏 = 𝑡 ∗ in empty states. Normalization always gives 𝑡 ≥ 𝑡 ∗ . Every failure increases this integer target by at least one (Equation (6)). Insertions and density-improving witness replacements cannot decrease it. The same floor-difference calculation with 𝑎 = 𝛾 bounds its total downward variation by 𝑉𝛾 . In particular, on an emptying update the previous state has one active edge, and its target drops by at most ⌊𝛾𝑏/𝑘𝑑 ⌋ − 𝑡 ∗ ; the next insertion cannot take it below 𝑡 ∗ . Thus empty states introduce no ¯ summing target increases additional charge. Since 𝑡 ∗ ≤ 𝜏 ≤ ⌊𝛾𝑏 𝜌⌋, and decreases gives the claimed bound on 𝐹 . □

Lemma A.4 gives an alternative bound on 𝐴 for reserve repair; the smaller bound can be substituted into Equation (8). A fixed-size high-degree core with all other vertices below the actual repair threshold is a sufficient structural regime. Crossing edges are included in the degrees. Snapshot density separation alone does not establish this condition. Fallback and maintenance costs. Failed searches and peeling supply known induced-edge counts. For an unknown-count fallback 𝑆, a separate edge stamp deduplicates encounters in its positive incidence lists before testing containment. The test stops at the first endpoint outside 𝑆. With analogous counters 𝑃𝑆 , 𝐸𝑆 , 𝐽𝑆 , 𝑃𝑆 ≤

∑︁

𝑞𝑣 ,

𝐸 𝑆 ≤ 𝑃𝑆 ,

𝐽𝑆 ≤ min{𝑟, |𝑆 | + 1}𝐸𝑆 .

𝑣 ∈𝑆

Every internal edge has a positive owner in 𝑆 and is counted once. The fallback edge itself is fully tested, so 𝐽𝑆 ≥ |𝑆 | also pays for Í copying and marking the new witness. We retain 𝑍 norm = 𝑆 (𝑃𝑆 + 𝐽𝑆 ), as mixed-rank fallback need not cost 𝑂 (𝑏). Í Let 𝑅up = updates |𝑒 |, 𝐾 count successful searches, Λ = log(2 + 𝑛 + Imax ), 𝐷 0 be inherited refresh debt, and Π 0 be initial containergrowth credit. For each successful path, ℎ path is the size of 𝐻 at its search. With compact or preallocated edge IDs, the single-path implementation has the following detailed accounting. Its first line pays for inherited state credits and edge updates, its second for search inspections, fallbacks, and heap changes, its third for locating

Edge updates and path transfers. For an updated edge of size 𝑠𝑒 , sorting and locating endpoint slots cost 𝑂 (𝑠𝑒 log(𝑟 + 1)). Discrete water filling searches at most 𝑏 + 1 integer levels, scanning the 𝑠𝑒 endpoints in each binary-search step, and costs 𝑂 (𝑠𝑒 log(𝑏 + 1)). Heap changes contribute 𝑂 (𝑠𝑒 log(𝑛 + 1)). Summing 𝑠𝑒 gives the 𝑅up term. Positive-incidence lists use inverse positions, so changing one endpoint share costs amortized constant time apart from its slot lookup. The initial container-growth credit Π0 pays any inherited allocation cost not charged to updates in the sequence. Search exploration contributes 𝑃tot + 𝐽tot . Its parent pointers already identify donor slots. A receiving slot is found by binary search in the sorted endpoints. As in the proof of Lemma 5.3, every nonterminal path edge was fully expanded before a destination was found, so all of its endpoints lie in the high-load region. Only the terminal edge can have rank exceeding ℎ path , giving the displayed sum of lookup costs. Intermediate load changes cancel, so a successful path changes only two heap keys, contributing 𝑂 (log(𝑛 + 1)) per success. Traversing the parent path itself is paid by the search that discovers it. Witness installation and budgeted peeling. A failed search already supplies its reached vertices and induced-edge count. A fallback costs 𝑃𝑆 + 𝐽𝑆 , and a peeling pass supplies its new witness as part of that pass. The total cost of clearing old membership marks is at most the initial |𝐶 0 | plus the total sizes of subsequently installed witnesses. These sizes are charged to the corresponding searches, fallbacks, or peeling passes. At a peeling refresh 𝑗, let 𝐷 𝑗 be the accumulated positive-scan debt, and let 𝑚 𝑗 , I𝑗 describe the current graph. The trigger requires 𝐷 𝑗 > 4(𝑛 + 𝑟𝑚 𝑗 ). Since I𝑗 ≤ 𝑟𝑚 𝑗 , a pass costs 𝑂 ((𝑛 + I𝑗 ) log(2 + 𝑛 + I𝑗 )) = 𝑂 (𝐷 𝑗 Λ). Debt is reset after each pass, so the charged scan intervals are Í disjoint and 𝑗 𝐷 𝑗 ≤ 𝑃 tot + 𝐷 0 . This proves the final term of Equation (B.1), even if the graph size changes between refreshes. It also includes constructing and marking the new peeling witness. Construction, reporting, and space. An empty state takes Θ(𝑛) time to construct. For a nonempty initial graph, we also charge the work of inserting its initial edges. Query materialization adds Θ(1 + |𝐶 |) per reported set. The bounds use representable unit-cost integer arithmetic and compact or preallocated edge identifiers, with allocation charged to the update sequence. A compacted state occupies 𝑂 (𝑛 +𝐼 ) words. The prototype retains deleted edge vectors and allocated container capacities, so its storage also depends on the update history. Independent correctness checking is performed outside the timed updates.

Scalable Approximate Algorithm for Dynamic Densest Subhypergraphs with Solution-Guided Maintenance

Deriving the summary guarantees. Proof of Theorems 5.1 and 5.2. Starting empty gives 𝐶 0 = ∅, 𝐷 0 = 0, and no inherited container-growth credit; initialization costs 𝑂 (𝑛). Write 𝑆 scan = 𝑃tot + 𝐽tot . Every successful search inspects an incidence, so 𝐾 ≤ 𝑆 scan . The incidences along a returned path have already been examined by that search, so the total number of path steps is also at most 𝑆 scan . The nonempty update sequence gives 𝑚 ∗ ≥ 1. Since 𝐼 ∗ ≤ 𝑟𝑚 ∗ and 𝑏 = ⌈2𝑟 /𝜖⌉, all logarithms in Equation (B.1) are 𝑂 (log((𝑛 + 𝑟𝑚 ∗ )/𝜖)). Substitution yields Equation (7), including the cost of peeling. For the coarse bound, a search inspects at most 𝐼 ∗ positive incidences and at most 𝐼 ∗ endpoints: each vertex is expanded once and each edge is stamped after its first expansion. Its inspection cost is at most 2𝐼 ∗ . An insertion transports at most 𝑏 units. During a deletion, the initial excess is at most the remaining total mass 𝑏𝑚 ∗ ; capacities only increase during repair, so deletion transport is at most 𝑏𝑚 ∗ . Integer augmentation therefore bounds successful searches per update by 𝑏𝑚 ∗ . Each failed search increases the inner threshold by a factor of at least 1+𝜖/4 (Equation (6)). The initial threshold is at least ⌊𝛾𝑏/𝑟 ⌋ and the final one is at most ⌊𝛾𝑏𝑚 ∗ ⌋. Hence there are 𝑂 (𝜖 −1 log(2+𝑟𝑚 ∗ )) failures per update. Consequently,  
𝑆 scan = 𝑂 𝑁 𝐼 ∗ 𝑏𝑚 ∗ + 𝜖 −1 log(2 + 𝑟𝑚 ∗ ) . There is at most one fallback normalization per update. Its stamped incidence and endpoint scans each cost at most 𝐼 ∗ , giving 𝑍 norm = 𝑂 (𝑁 𝐼 ∗ ), while 𝑅up ≤ 𝑁𝑟 . Finally, 𝑏 = 𝑂 (𝑟 /𝜖) and log(2 + 𝑟𝑚 ∗ ) = 𝑂 (𝑟𝑚 ∗ ). Substitution in Equation (7) gives   𝑟𝑚 ∗ 𝐼 ∗ 𝑛 + 𝑟𝑚 ∗ 𝑇maint = 𝑂 𝑛 + 𝑁 log . (B.2) 𝜖 𝜖 Excluding initialization and dividing by 𝑁 proves Theorem 5.1. The approximation follows from Theorem 4.3; the density and witness are stored explicitly, giving the stated query costs. □ The main text proves Lemma 5.6 by substituting the locality and transport bounds into Equation (7).

C

CQ Reconstruction and Evaluation Protocol

Our CQ baseline reconstructs the basic amortized graph core, nested label buckets, and shared-copy representation from a preliminary version of Chekuri et al. [15], using the hypergraph extension described in its Section 6. This preliminary version is linked in Section 6.1. Each logical insertion or deletion executes 𝐾 unit-copy operations; copies with the same hyperedge and head share a multiplicity and endpoint labels. There are no bulk transfers or empirically tuned copy counts.

Fixed parameters and extraction. Let 𝑛 be the full stream’s vertexuniverse size and 𝑟 its maximum hyperedge rank. For requested 0 < 𝜖 ≤ 1, we set   log max{2, 𝑛} 𝑞 = (1 + 𝜖) 1/4, 𝑀= , log 𝑞   log(1 + 𝜖) 𝑎 = exp − 1, 𝑃 = (1 + 𝑎) 2, 8𝑀 𝛽 = 3 + 3𝑎,

Δ = (1 + 𝜖) −1/2 − (1 + 𝜖) −1,

and 𝐾 = ⌈𝛽𝑀𝑟 /(𝑞Δ)⌉ + 1. These explicit constants are our conservative choice, not constants specified in the source paper. At quiescence, the label invariants imply 𝑑 (ℎ) ≤ 𝑃 𝑑 (𝑢) +3+2𝑎 ≤ 𝑃 𝑑 (𝑢) + 𝛽 for each copy head ℎ and every endpoint 𝑢. With 𝜇 = max𝑣 𝑑 (𝑣), start at 𝑡 0 = 𝜇 and use 𝑡𝑖+1 = (𝑡𝑖 − 𝛽)/𝑃 and 𝑆𝑖 = {𝑣 : 𝑑 (𝑣) ≥ 𝑡𝑖 }, including all threshold ties. We return 𝑆𝑖+1 at the first index with |𝑆𝑖+1 | ≤ 𝑞|𝑆𝑖 | and compute its fully induced logical-edge density. For a nonempty snapshot satisfying these invariants, 𝜌∗ 𝛽𝑀 𝜌∗ 𝜌 (𝑆𝑖+1 ) ≥ 𝑀 − ≥ , 𝑞𝐾 1+𝜖 𝑞𝑃 using 𝜌 ∗ ≥ 1/𝑟 ; empty snapshots return the empty set. Deletion completion and implementation scope. Section 6 of that preliminary version does not specify hypergraph deletion pseudocode. Our completion selects a global minimum-load endpoint for a unit reorientation, relabels the destination group, and schedules both changed endpoints. A triggering endpoint whose condition remains violated stays on the worklist; residual source-group copies retain their labels. We have not established general termination or the original amortized update-time bound for this worklist. We do not implement the deamortized or full worst-case construction. DiÍ rect group-specific endpoint labels and links require 𝑂 ( 𝑒 ∈𝐸 |𝑒 | 2 ) worst-case live storage, in addition to the vertex state and registry capacity determined by peak simultaneous groups. Retired group identifiers are reused. Extraction scans at most 𝑀 thresholds and Í the active edge incidences, taking 𝑂 (𝑀𝑛 + 𝑝) time for 𝑝 = 𝑒 ∈𝐸 |𝑒 |. Thus, we do not claim the original algorithm’s time or space bounds. Result admission. Each reported CQ mean requires three complete repetitions, with the entire update stream and every scheduled query processed. Independent replay checks the returned sets’ induced densities against exact snapshot optima and the requested rational accuracy. Passing prefixes and single decision trials do not constitute three-run results. The 1,800-second CQ wall limit includes input loading, invariant checks, and allocation output; these are excluded from running time. We sample working-set and private-memory use against a 24 GiB limit rather than impose a hard operating-system cap. Running-time means follow the reporting criteria in Section 6.1.

Related documents

• Scalable Approximate Algorithm for Dynamic Densest Subhypergraphs with Solution-Guided Maintenance#1144945
• Consilience-Driven Automated Scientific Inference on Multilayer Knowledge Hypergraphs: Cross-Domain Intersections of Mathematical Physics, Biomedicine, and Geomythology#290378
• A Phase Transition for Small Dense Subhypergraphs#1049456
• Fast approximate shortest paths in the congested clique#301330
• Scalable Algorithm for Dynamic Quasi-clique Detection#1144814