Maximum Strong Independent Sets in Hypergraphs: Reductions, Bounds, and Greedy Certificates

1 Introduction

• Local incompatibility blocks make strong independence a natural model when noisy or local evidence does not establish transitive equivalence.In multi-band LSH-MinHash deduplication, collision buckets provide local evidence, while connected-component contraction can over-merge unrelated vertices through chains of collisions.Source: §1 · p. 1
• 99.43% of the puncturing bound is reached by the layered greedy solver in the reported full-corpus ablations, across ClueWeb22 and HPLT.The companion study reports results within 0.5% in 16 of 20 rows and within 0.6% in all rows.Source: §1 · p. 2
• The framework combines exact reductions and block-weight bounds with puncturing, covering, and layered greedy clustering, with guarantees under explicit incidence conditions.The analysis includes validity, termination, fixed-point, feasibility, maximality, conditional optimality, witness-matching, and incidence-local complexity guarantees.Source: §1 · p. 2
• Related work addresses hardness and approximation, local search, relaxations, and reductions; this paper instead focuses on incidence-structural tools.The objective is classical, while the block-weight bounds, residual certificate-search algorithms, and certificate-guided clustering schedule are presented as new tools.Source: §1 · p. 2
• Incidence-based certificates upper-bound the optimum and guide greedy clustering without pairwise conflict graphs, LP/SDP relaxations, or generic local-search oracles.The toolkit includes block-weight bounds, weight-1 preclusion, support-superset sharpening, puncturing, covering reweighting, and witness matching.Source: §1 · p. 2

2 Problem Formulation and Preliminaries

• The strong-independence objective treats each block as a local incompatibility constraint, not as part of a transitive equivalence relation.The paper also describes each block as a clique in the pairwise graph induced by block membership.Source: §2 · pp. 3–4
• Vertex incidence profiles help characterize upper bounds and derive the block-native greedy clustering algorithm.Vertices appearing in many blocks are described as more entangled because retaining one consumes feasibility across multiple local constraints.Source: §2 · p. 4
• In the running example, connected-component contraction would merge the whole instance into one component and retain only one representative.The example uses a connected block-overlap chain to illustrate the contraction outcome.Source: §2 · p. 4

Block weights

• After dominance reduction, the running example separates into weight layers 1, 2, 3, and 4; unreduced support-superset distractors disguise two weight-4 blocks as weight-3 blocks.Source: §3 · p. 5

Dominance and incidence-twin compression

• Dominance deletion and incidence-twin compression preserve the optimal retention value: a vertex with a smaller-support witness can be removed, and equal-support vertices can be quotiented.Full dominance closure can be expensive, so the paper uses twin compression as shared preprocessing and applies dominance suppression in bounded, layer-revealed form later.Source: §3 · pp. 6–7

Canonical optimal form for weight-1 blocks

• An optimal feasible set can include a degree-1 vertex from every weight-1 block, giving each such block a canonical root.Source: §3 · p. 7

Pivot dominance closure and canonical inclusion

• After removing vertices dominated by pivot a, a block condition on its residual blockers guarantees an optimum containing a; when the block equals that residual set, every optimum excluding a has exactly one such blocker to swap.In this equality case, deleting the dominated vertices before applying the next section’s block-weight bound gives a weakly smaller computable upper bound, though improvement is typically marginal.Source: §3 · pp. 8–9

Dominance-reduced incidence-block optimality certificate

• Under the stated partition and representative-support conditions, the representatives form a maximum feasible set for both the dominance-reduced and original families.Source: §3 · p. 10

• Every feasible O in B− has |O| ≤ m; since feasible Z has size m, α(B)=α(B−)=m, and Z remains feasible in B.Source: §3 · p. 11
• U(B)=31/6 is larger because f and g artificially lower weights of B9 and B10; dominance reduction removes this distortion.The later greedy layered clustering algorithm intrinsically achieves the same suppression by having low-weight roots a, b, and e absorb u, f, and g before higher-weight layers are processed.Source: §3 · p. 11
• Except for incidence-twin compression and the weight-1 canonical form, exact characterization rules are optional; scalable certificates and algorithms do not require costly dominance-closure preprocessing.These rules can shrink or partially canonicalize an instance without changing its optimum.Source: §3 · p. 11

4.1 Closed-Form and Low-Weight Certificates

• The closed-form block-weight certificate upper-bounds every feasible retained set by charging each retained vertex across its incident blocks.The proof distributes one unit of charge evenly over each vertex’s incident blocks; feasibility limits each block to charge from at most one retained vertex.Source: §4.1 · p. 12
• Weight-1 preclusion yields a computable bound that is never weaker than the closed-form bound.It accounts for vertices in weight-1 blocks separately and applies the block-weight bound to the residual family.Source: §4.1 · p. 13
• For residual weight-2 structure, a matching of degree-2 vertices across block incidences certifies optimality when it saturates the integer closed-form bound.This is sufficient, not an unconditional weight-2 preclusion rule or a guaranteed bound improvement.Source: §4.1 · p. 14

4.2 Layered Superset Sharpening and Puncturing

• Iterative puncturing searches residual block families, recomputes intrinsic weights, and keeps the smallest valid upper-bound certificate encountered.The residual search uses the closed-form and weight-1 certificates as reusable primitives.Source: §4.1 · p. 14
• Layered superset sharpening processes block-weight layers and deletes higher-degree vertices whose supports contain a revealed block-weight witness’s support.The pass targets support-superset distractors exposed by the current witnesses rather than performing global dominance closure.Source: §4.2 · p. 15

4. Layered Superset Sharpening

• Every support-superset deletion made by layered sharpening preserves the optimum, and the terminal family has no higher-degree support superset for an inspected block-weight witness.The fixed point is limited to supports inspected by the pass; other containments may remain.Source: §4 · p. 16
• One sharpening pass costs O(IF + T∩), from incidence scans and intersections for newly revealed supports.The method avoids a global pairwise support-comparison table.Source: §4 · pp. 16–17

Iterative Puncturing

• Puncturing blocks and recomputing weights gives a valid upper-bound certificate, because deleting blocks relaxes the remaining feasibility constraints.The punctured-family proposition also permits weight-1 preclusion and applies the closed-form bound to the residual instance.Source: §4 · p. 17
• The iterative search processes weight layers from high to low, accepts punctures that do not increase the certificate, and returns the smallest recorded valid bound.Zero-gain punctures can expose weight-1 blocks for preclusion at the next rebuild.Source: §4 · p. 18

2. Record the current certificate. Update

• Recomputing the certificate after each puncture allows zero-gain moves that expose weight-1 blocks, which can tighten the bound after the next rebuild.In the example, increasing-current-nmin order finds exposure blocks; puncturing A4 exposes weight-1 structure, and a later rebuild precludes L3 and L4.Source: §2 · pp. 19–20
• Every certificate recorded by iterative puncturing upper-bounds the maximum strong independent set size, and the algorithm terminates after finitely many punctures and preclusion steps.Each accepted puncture, preclusion, or nontrivial compression or sharpening step removes live blocks or vertices from a finite incidence family.Source: §2 · p. 19

4.3 Covering Certificates

• 2 is the maximum feasible retention value in the uniform-weight-2 example, showing that the closed-form block-weight bound can be loose even without a larger all-x block.The parity blocks force at most one odd-indexed and one even-indexed vertex in any feasible set.Source: §4.3 · p. 20
• The greedy covering algorithm returns an upper bound by selecting blocks that cover retained roots, with lower-weight blocks prioritized and ties favoring more current minimum-weight vertices.The weight-ordering principle says lower-weight blocks are most constraining; the covering schedule starts at the lowest residual weight and chooses the largest current count of minimum-degree vertices.Source: §4.3 · p. 22
• Dropping blocks from a shared-universe family can only relax feasibility; the optimum is preserved when every pair in each omitted block occurs together in a retained block.Any covering subfamily preserves the active vertex universe, so the block-weight bound can be reapplied to that restricted family for a sharper upper bound.Source: §4.3 · pp. 23–24
• Iterated covering produces nested valid upper bounds and stabilizes after finitely many steps at a family whose blocks all have restricted weight 1.The family size is nonincreasing and the iteration stops when the covering family is unchanged.Source: §4.3 · p. 25
• The iterated covering sequence stabilizes, and every block in its terminal family has intrinsic weight 1.At a fixed point, a block of restricted weight greater than 1 would be discarded in a rerun, contradicting that the family is unchanged.Source: §4.3 · p. 25
• The terminal covering family yields an optimal retained set with one restricted-degree-1 vertex per block and size equal to the family size.The selected vertices form a feasible set and attain the optimum for the restricted family.Source: §4.3 · p. 26
• Covering bounds complement closed-form and puncturing bounds; the greedy covering search captures concentration effects but requires repeated residual updates.Its secondary key favors blocks covering more current minimum-degree candidates per unit bound increase, and computation is typically quadratic-scale in residual incidences.Source: §4.3 · pp. 26–27
• In the balanced example, the closed-form bound is sharp, the greedy covering count is 3, and restricted reweighting recovers the exact optimum of 2.The greedy count can overcount because its covering family is non-minimal.Source: §4.3 · pp. 27–28
• A second covering iteration tightens the example’s bound to 2, while another weight-2 example’s gap falls to a constant-size gap.The decreasing-nmin(B) within-layer rule drives the stronger refinements; a weaker order need not do so.Source: §4.3 · p. 28

• The algorithm processes lower block-weight layers first and, within each layer, chooses blocks with the largest current nmin(B), localizing updates to touched incidences.It begins with incidence-twin compression and a weight-1 preclusion pass, then recomputes residual degrees before the layered stage.Source: §5 · p. 28
• Within a selected block, choosing the candidate with the smallest equal-weight collision score minimizes degree-w candidates clustered away and preserves the largest remaining pool for later roots.The collision score is monotone in the number of current degree-w candidates consumed by the root choice.Source: §5 · p. 30
• Absorbing a current block-weight witness also absorbs any active vertex whose support contains that witness’s support, providing local superset suppression without a global containment pass.This guarantee applies to current minimum-degree witnesses, not to arbitrary nonminimum vertices incidentally absorbed; higher-degree nonminimum superset effects are outside its scope.Source: §5 · pp. 31–32
• A degree-w vertex-to-block index and bucketed nmin priorities let the algorithm update affected blocks locally, making within-layer processing essentially linear in active layer incidences.Each degree-w vertex is deleted from the index at most once, and current-layer incidences are touched when their degree-w endpoint is attached away.Source: §5 · p. 32
• On this connected family, the greedy layered clustering algorithm exactly attains the dominance-reduced closed-form bound (optimal value 5), whereas connected-component contraction retains only one vertex.Weight-2 representatives b and e suppress f and g; before suppression, they gate blocks B9 and B10 to apparent weight 3, and afterward those blocks recover true reduced weight 4.Source: §5 · pp. 32–33

5 Greedy Layered block-Weight Clustering

• In the alternating pair-and-parity example, the closed-form bound is loose, while puncturing, covering, and greedy clustering identify the same two-representative structure.The example has α(B) = 2.Source: §5 · p. 34
• Under Theorem 9’s suppression, weight-alignment, and same-layer tie-break conditions, greedy clustering selects the representatives that form a maximum strong independent set.The theorem’s proof identifies the root set as {z1, . . . , zm} and gives α(B) = m.Source: §5 · pp. 35–36
• The block-root uniqueness invariant ensures each block contains at most one active root, making the greedy output feasible; every non-root is blocked from being added, so the output is maximal.The proof of maximality assigns each non-root to a block already containing a root.Source: §5 · pp. 36–37
• Every maximal feasible set meets each connected component of the block-overlap graph, so the greedy output has size at least the number of those components.This is a lower bound, not a claim that component contraction solves the strong-independence objective.Source: §5 · p. 37
• The layer schedule prioritizes lower-weight blocks because they contribute more to the closed-form upper bound, then favors larger nmin within a layer.The within-layer priority follows the minimum-weight covering-pressure rationale.Source: §5 · p. 38
• Unlike vertex-centric hypergraph MIS methods, this approach organizes its certificates and greedy schedule around the incidence relation, block lists, support lists, and root assignments.Source: §5 · p. 38

6.1 Exactness and Algorithm-Aware Bounds

• When blocks are pairwise disjoint, the greedy algorithm is optimal because it retains one representative per nonempty block.With no overlap, choosing a root in one block cannot remove or constrain vertices in another.Source: §6.1 · p. 38
• The ratio |RG|/U(B) measures how closely the greedy feasible set approaches the explicit structural upper bound, without requiring exact optimum computation.Both |RG| and U(B) are computed directly from materialized incidence data.Source: §6.1 · p. 38
• Theorem 11 gives a finer, algorithm-aware upper bound using the greedy algorithm’s layer-by-layer assignments rather than only static block weights.The comparison assumes d(v) ≥ 1 for every vertex.Source: §6.1 · p. 39

6.2 Complexity

• Preprocessing takes O(I) time, and placing each residual block in its initial weight set takes O(Mres) time.Here I is total vertex-block incidence and Mres is the number of residual blocks.Source: §6.2 · p. 40
• With an integer-keyed bucketed queue or equivalent fixed-layer updates, the layered greedy stage runs in O(Jres + Tindex + Tscore).Jres is the total incidence scanned across residual block states; Tindex and Tscore account for index maintenance and collision-score evaluations.Source: §6.2 · pp. 40–41
• The implementation is incidence-local: its dominant cost is scanning live incidences during residual layer processing, without constructing induced subhypergraphs or dual graphs.A global within-layer sort is unnecessary under the described updates.Source: §6.2 · p. 41

7 Conclusion

• The framework combines exact reductions, block-weight upper bounds, puncturing and covering certificates, and layered greedy clustering with stated feasibility, maximality, witness-matching, complexity, and conditional optimality guarantees.The guarantees apply under explicit incidence conditions.Source: §7 · p. 41
• The paper argues that local hyperedge constraints should be handled through incidence structure rather than a coarser graph-level surrogate.The theory focuses on hyperedges functioning as local incompatibility blocks, not transitive equivalence classes.Source: §7 · p. 41
• Future work includes sharpening worst-case approximation guarantees, characterizing when puncturing and covering certificates are tight, and developing graph-native certificates.For ordinary graph MIS, the paper highlights recovering block-like incidence decompositions and certificate-guided schedules as a substantial question.Source: §7 · p. 41