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

# Maximum Strong Independent Sets in Hypergraphs: Reductions, Bounds, and Greedy Certificates
Source: [https://arxiv.org/html/2609.17951](https://arxiv.org/html/2609.17951)
Yingquan \(Cody\) Wu††thanks:Corresponding author\.Affiliation:MBZUAI Institute of Foundation ModelsAffiliation:Sunnyvale, CA, USAEmail:[mailto:](mailto:)[icodywu@gmail\.com](mailto:[email protected])Jason CongAffiliation:University of California, Los AngelesAffiliation:Los Angeles, CA, USAEmail:[mailto:](mailto:)[cong@cs\.ucla\.edu](mailto:[email protected])

Preprint\. Under review at the Journal of the ACM\.

###### Abstract

We study the maximum strong independent set problem in a finite hypergraph: find the largest vertex set that intersects every hyperedge in at most one vertex\. This objective arises whenever each observed block is a local incompatibility constraint but transitive closure across overlapping blocks is not justified\. A motivating example is multi\-band LSH\-MinHash deduplication, where each collision bucket gives local evidence, while connected\-component contraction can impose spurious global equivalences\. The paper develops an incidence\-structural toolkit for this problem\. We prove exact reductions for dominance, incidence twins, and weight\-1 blocks; derive closed\-form and low\-weight upper bounds; introduce puncturing and covering certificates that sharpen those bounds; and analyze a layered greedy clustering algorithm driven by block weights and residual incidence\. The algorithmic analysis includes feasibility, maximality, conditional optimality, a layered witness\-matching upper bound, and incidence\-local complexity bounds\. The results give correctness, termination, fixed\-point, and optimality certificates for broad incidence families, together with examples showing when different certificates separate or coincide\.

Keywords:maximum independent set, strong independent set, hypergraphs, set packing, structural bounds, greedy algorithms\.

ACM CCS:Theory of computation—Approximation algorithms analysis; Problems, reductions and completeness\. Mathematics of computing—Hypergraphs\.

## 1Introduction

A strong independent set in a hypergraph is a vertex set that contains at most one vertex from each hyperedge\. The corresponding maximum strong independent set problem is a natural abstraction for selection under local block constraints: a block asserts that its vertices are mutually incompatible for simultaneous selection, but overlaps between different blocks do not justify transitive contraction\. This distinction is central in applications where blocks are generated by noisy or local evidence rather than by an equivalence relation\.

One motivating example is large\-scale LSH\-MinHash deduplication\[[1](https://arxiv.org/html/2609.17951#bib.bib1),[2](https://arxiv.org/html/2609.17951#bib.bib2),[4](https://arxiv.org/html/2609.17951#bib.bib4),[3](https://arxiv.org/html/2609.17951#bib.bib3)\]\. A multi\-band LSH pipeline emits collision buckets band by band\. Each bucket is a local incompatibility block, but connected\-component contraction over overlapping buckets can over\-merge unrelated vertices through chains of local collisions\. The correct combinatorial object is therefore the hypergraph whose vertices are items and whose hyperedges are emitted buckets; feasible retention is exactly strong independence\. A companion application study reports ClueWeb22 \(1\.62B documents\) and HPLT \(3\.98B documents\) ablations where, across all full\-corpus rows, the puncturing certificate is strictly stronger than the converged covering certificate, and the layered greedy solver reaches at least99\.43%99\.43\\%of the puncturing bound \(within0\.5%0\.5\\%in 16 of 20 rows, and within0\.6%0\.6\\%in all rows\)\[[7](https://arxiv.org/html/2609.17951#bib.bib7)\]\. The results below use this example only as motivation\. The theory is stated for an arbitrary finite hypergraphH=\(V,ℬ\)H=\(V,\\mathcal\{B\}\)\.

The same incidence\-block objective also appears in fixed\-path routing, weighted set packing and combinatorial\-auction winner determination, and perfect minimal hashing\[[5](https://arxiv.org/html/2609.17951#bib.bib5),[6](https://arxiv.org/html/2609.17951#bib.bib6),[13](https://arxiv.org/html/2609.17951#bib.bib13)\]\. In all cases, feasibility is governed by materialized multiway conflicts rather than by transitive equivalence classes\.

This paper develops a structural and algorithmic framework for maximum strong independent set in such incidence hypergraphs\. The central new contribution is an incidence\-certificate layer for bounding the optimum: a closed\-form block\-weight upper bound, its weight\-1 refinement, layered support\-superset sharpening, iterative puncturing certificates, and covering/reweighting certificates\. These bounds are explicit functions of the materialized vertex\-block incidence lists; they do not rely on solving a linear program \(LP\), semidefinite program \(SDP\), theta\-body relaxation, or exact search subproblem\. Around this certificate layer, we prove exact reductions based on dominance, incidence\-twin compression, canonical handling of weight\-1 blocks, and pivot dominance closure\. We then give algorithms that actively improve and track the certificates: iterative greedy puncturing searches residual block subfamilies for stronger bounds, greedy covering constructs independent upper\-bound witnesses, and greedy layered clustering uses the same block\-weight order to build feasible root sets\. The proofs give validity, termination, fixed\-point, feasibility, maximality, conditional optimality, layered witness\-matching, and incidence\-local complexity guarantees\.

The guiding principle is that the useful structure is not generic graph adjacency alone but the full vertex\-block incidence relation\. In particular, low block weight and incidence support determine both the strongest upper\-bound certificates and the order in which the bound\-improving and clustering algorithms should act\. This perspective separates the structural objective from any particular source of blocks and makes the framework applicable to any setting in which local incompatibility constraints are materialized as a hyperedge family\.

Maximum strong independent set inherits classical hardness phenomena from Karp’s reductions\[[8](https://arxiv.org/html/2609.17951#bib.bib8)\], and sits within a broad approximation, local\-search, and relaxation literature for hypergraph packing problems\[[14](https://arxiv.org/html/2609.17951#bib.bib14),[15](https://arxiv.org/html/2609.17951#bib.bib15),[16](https://arxiv.org/html/2609.17951#bib.bib16),[17](https://arxiv.org/html/2609.17951#bib.bib17),[18](https://arxiv.org/html/2609.17951#bib.bib18)\]\. Bounded\-degree and uniform hypergraph independent\-set algorithms give important general baselines\[[11](https://arxiv.org/html/2609.17951#bib.bib11),[10](https://arxiv.org/html/2609.17951#bib.bib10),[12](https://arxiv.org/html/2609.17951#bib.bib12)\], while recent work studies data reductions for strong maximum independent set in hypergraphs\[[13](https://arxiv.org/html/2609.17951#bib.bib13)\]\. Our focus is complementary: the objective is classical, but the block\-weight bounds, residual certificate\-search algorithms, and certificate\-guided clustering schedule are new incidence\-structural tools\.

Table 1:Comparison with existing approaches for hypergraph strong independent set and set\-packing\-type formulations\.Table[1](https://arxiv.org/html/2609.17951#S1.T1)summarizes the distinction\. Existing set\-packing and hypergraph\-MIS machinery typically optimizes a feasible packing by local exchanges, proves guarantees under rank/degree restrictions, relaxes the independence constraints into an auxiliary convex program, or reduces the instance before exact search\. The contribution here is not another instantiation of those templates\. We introduce an incidence\-certificate layer whose quantities are computed directly from the given vertex–block incidence lists: the closed\-form block\-weight sum, canonical weight\-1 preclusion, layered support\-superset sharpening, iterative puncturing, covering reweighting, and greedy witness\-matching certificates\. These certificates upper\-bound the optimum, explain when the bound is tight, and drive the block\-native greedy clustering schedule without constructing a pairwise conflict graph, solving an LP/SDP/theta relaxation, or invoking a generic local\-search oracle\.

## 2Problem Formulation and Preliminaries

Letℬ=\{B1,…,BM\}\\mathcal\{B\}=\\\{B\_\{1\},\\dots,B\_\{M\}\\\}be a finite block family, and let

V:=⋃B∈ℬBV:=\\bigcup\_\{B\\in\\mathcal\{B\}\}Bbe the active universe\. Any vertex that never appears in any block is unconstrained byℬ\\mathcal\{B\}and is omitted from this optimization\. Define the hypergraph

H=\(V,ℬ\),H=\(V,\\mathcal\{B\}\),\(1\)where elements ofVVare vertices and blocks are hyperedges\. Throughout the theoretical sections, we use “block” and “hyperedge” interchangeably\. Accordingly, when we refer to a maximum independent set objective below, we mean the strong hypergraph version: no hyperedge may contain two selected vertices\.

We use the standing convention that the block family is inclusion\-reduced: for distinct indicesi≠ji\\neq j,

Bi⊈Bj\.B\_\{i\}\\not\\subseteq B\_\{j\}\.\(2\)
Equivalently, if one forms the pairwise graph induced by block membership, each blockBBis treated as a clique on the vertex setBB: every pair inBBis an incompatibility pair under the strong\-independence objective\. This is a local selection constraint, not a transitive equivalence relation outside the stated block family\.

###### Definition 1\(Strong independent set and maximum strong independence number\)\.

A setR⊆VR\\subseteq Vis a strong independent set ofH=\(V,ℬ\)H=\(V,\\mathcal\{B\}\)if

\|R∩B\|≤1∀B∈ℬ\.\|R\\cap B\|\\leq 1\\qquad\\forall B\\in\\mathcal\{B\}\.\(3\)The maximum strong independence number is

α\(ℬ\):=max\{\|R\|:R⊆V,\|R∩B\|≤1∀B∈ℬ\}\.\\alpha\(\\mathcal\{B\}\):=\\max\\\{\|R\|:R\\subseteq V,\\ \|R\\cap B\|\\leq 1\\ \\forall B\\in\\mathcal\{B\}\\\}\.\(4\)

To characterize the upper bounds and to derive our block\-native greedy clustering algorithm, it is useful to record the incidence profile of each vertex\. Intuitively, a vertex that appears in many blocks is globally more entangled: retaining it consumes feasibility across many local clique constraints at once\.

###### Definition 2\(block\-index incidence set and vertex degree\)\.

For each vertexv∈Vv\\in V, define its block\-index incidence set by

I⁡\(v\):=\{i∈\{1,…,M\}:v∈Bi\},I\(v\):=\\\{i\\in\\\{1,\\dots,M\\\}:v\\in B\_\{i\}\\\},\(5\)and its vertex degree by

d⁡\(v\):=\|I⁡\(v\)\|=\|\{B∈ℬ:v∈B\}\|\.d\(v\):=\|I\(v\)\|=\|\\\{B\\in\\mathcal\{B\}:v\\in B\\\}\|\.\(6\)

Example 1\(a\) \(Running example: block family and vertex degrees\)\.We use the following block family as a running example in Sections 3–6:

B1\\displaystyle B\_\{1\}=\{a,u\},\\displaystyle=\\\{a,u\\\},B2\\displaystyle B\_\{2\}=\{b,u,f,p\},B3=\{b,f,q\},\\displaystyle=\\\{b,u,f,p\\\},\\qquad B\_\{3\}=\\\{b,f,q\\\},B4\\displaystyle B\_\{4\}=\{e,g,p\},B5=\{e,g,q\},\\displaystyle=\\\{e,g,p\\\},\\qquad B\_\{5\}=\\\{e,g,q\\\},B6\\displaystyle B\_\{6\}=\{c,x,p\},B7=\{c,y,q\},B8=\{c,x,y\},\\displaystyle=\\\{c,x,p\\\},\\qquad B\_\{7\}=\\\{c,y,q\\\},\\qquad B\_\{8\}=\\\{c,x,y\\\},B9\\displaystyle B\_\{9\}=\{r,f,x,p\},B10=\{r,g,y,q\},\\displaystyle=\\\{r,f,x,p\\\},\\qquad B\_\{10\}=\\\{r,g,y,q\\\},B11\\displaystyle B\_\{11\}=\{r,x,q\},B12=\{r,y,p\}\.\\displaystyle=\\\{r,x,q\\\},\\qquad B\_\{12\}=\\\{r,y,p\\\}\.Its block\-overlap graph, where blocks are adjacent when they intersect, is connected, for example through

B1∩B2≠∅,B2∩B4≠∅,B4∩B6≠∅,B6∩B9≠∅,B9∩B10≠∅,B10∩B11≠∅,B\_\{1\}\\cap B\_\{2\}\\neq\\varnothing,\\quad B\_\{2\}\\cap B\_\{4\}\\neq\\varnothing,\\quad B\_\{4\}\\cap B\_\{6\}\\neq\\varnothing,\\quad B\_\{6\}\\cap B\_\{9\}\\neq\\varnothing,\\quad B\_\{9\}\\cap B\_\{10\}\\neq\\varnothing,\\quad B\_\{10\}\\cap B\_\{11\}\\neq\\varnothing,so connected\-component contraction would merge the whole instance into one connected component and retain only one representative\. The vertex degrees are

d⁡\(a\)\\displaystyle d\(a\)=1,d\(b\)=d\(e\)=d\(u\)=2,\\displaystyle=1,\\qquad d\(b\)=d\(e\)=d\(u\)=2,d⁡\(c\)\\displaystyle d\(c\)=d⁡\(f\)=d⁡\(g\)=3,\\displaystyle=d\(f\)=d\(g\)=3,d⁡\(r\)\\displaystyle d\(r\)=d\(x\)=d\(y\)=4,d\(p\)=d\(q\)=5\.\\displaystyle=d\(x\)=d\(y\)=4,\\qquad d\(p\)=d\(q\)=5\.The verticesu,f,gu,f,gare deliberate support\-superset distractors:

I⁡\(a\)\\displaystyle I\(a\)=\{1\}⊊I⁡\(u\)=\{1,2\},\\displaystyle=\\\{1\\\}\\subsetneq I\(u\)=\\\{1,2\\\},I⁡\(b\)\\displaystyle I\(b\)=\{2,3\}⊊I⁡\(f\)=\{2,3,9\},\\displaystyle=\\\{2,3\\\}\\subsetneq I\(f\)=\\\{2,3,9\\\},I⁡\(e\)\\displaystyle I\(e\)=\{4,5\}⊊I⁡\(g\)=\{4,5,10\}\.\\displaystyle=\\\{4,5\\\}\\subsetneq I\(g\)=\\\{4,5,10\\\}\.Later dominance and low\-weight clustering rules will remove these distractors, revealing the block structure that drives the sharper certificate and the greedy clustering schedule\.

## 3Characterizations of Maximum Strong Independent Sets

This section records incidence reductions and canonical optimality conditions for maximum strong independent sets\. The reductions either preserveα⁡\(ℬ\)\\alpha\(\\mathcal\{B\}\)exactly or identify vertices that can be fixed or suppressed without excluding all optima\. These structural rules are the basis for the upper\-bound certificates and greedy schedules in later sections\.

A recurring structural statistic is the minimum incidence degree inside a block\.

###### Definition 3\(block weight\)\.

For each blockB∈ℬB\\in\\mathcal\{B\}, define

w⁡\(B\):=minv∈B⁡d⁡\(v\)\.w\(B\):=\\min\_\{v\\in B\}d\(v\)\.\(7\)

Example 1\(b\) \(Running example: block weights\)\.For the running example in Example[2](https://arxiv.org/html/2609.17951#S2), the block weights are

w⁡\(B1\)\\displaystyle w\(B\_\{1\}\)=1,w\(B2\)=⋯=w\(B5\)=2,\\displaystyle=1,\\qquad w\(B\_\{2\}\)=\\cdots=w\(B\_\{5\}\)=2,w⁡\(B6\)\\displaystyle w\(B\_\{6\}\)=⋯=w\(B10\)=3,w\(B11\)=w\(B12\)=4\.\\displaystyle=\\cdots=w\(B\_\{10\}\)=3,\\qquad w\(B\_\{11\}\)=w\(B\_\{12\}\)=4\.The apparent weight\-33status ofB9B\_\{9\}andB10B\_\{10\}is caused only by the degree\-33support\-superset distractorsffandgg\. The dominance rule below will justify deleting the distractorsu,f,gu,f,gusinga,b,ea,b,eas witnesses, respectively; in that reduced view the weights become

w−​\(B1\)\\displaystyle w\_\{\-\}\(B\_\{1\}\)=1,w−\(B2\)=⋯=w−\(B5\)=2,\\displaystyle=1,\\qquad w\_\{\-\}\(B\_\{2\}\)=\\cdots=w\_\{\-\}\(B\_\{5\}\)=2,w−​\(B6\)\\displaystyle w\_\{\-\}\(B\_\{6\}\)=w−\(B7\)=w−\(B8\)=3,w−\(B9\)=⋯=w−\(B12\)=4\.\\displaystyle=w\_\{\-\}\(B\_\{7\}\)=w\_\{\-\}\(B\_\{8\}\)=3,\\qquad w\_\{\-\}\(B\_\{9\}\)=\\cdots=w\_\{\-\}\(B\_\{12\}\)=4\.Thus the dominance\-reduced family naturally decomposes into the intended weight layers1,2,3,41,2,3,4, while the unreduced family disguises two true weight\-44blocks as weight\-33blocks\.

###### Definition 4\(Incidence\-twin quotient\)\.

Define an equivalence relation on the active vertex universe by

u∼v⟺I\(u\)=I\(v\)\.u\\sim v\\quad\\Longleftrightarrow\\quad I\(u\)=I\(v\)\.\(8\)SinceV=⋃B∈ℬBV=\\bigcup\_\{B\\in\\mathcal\{B\}\}B, every equivalence class has nonempty support\. Let

V¯:=V/∼\\overline\{V\}:=V/\{\\sim\}be the set of incidence\-twin classes, and write\[v\]\[v\]for the class containingvv\. For each blockBiB\_\{i\}, define its quotient block by

B¯i:=\{\[v\]:v∈Bi\}\.\\overline\{B\}\_\{i\}:=\\\{\[v\]:v\\in B\_\{i\}\\\}\.\(9\)The incidence\-twin quotient family is

ℬ¯:=\{B¯i:i=1,…,M\},\\overline\{\\mathcal\{B\}\}:=\\\{\\overline\{B\}\_\{i\}:i=1,\\dots,M\\\},\(10\)viewed as an indexed block family, with duplicate quotient blocks removable by the inclusion rule above if desired\.

For the next theorem, writeℬ=\{B1,…,BM\}\\mathcal\{B\}=\\\{B\_\{1\},\\dots,B\_\{M\}\\\}and use the incidence setsI⁡\(⋅\)I\(\\cdot\)from Definition[2](https://arxiv.org/html/2609.17951#Thmdefinition2)\. We also use a deletion shorthand: for a vertex subsetS⊆VS\\subseteq V, write

ℬ−S:=\{B∖S:B∈ℬ,B∖S≠∅\},\\mathcal\{B\}\-S:=\\\{B\\setminus S:\\ B\\in\\mathcal\{B\},\\ B\\setminus S\\neq\\varnothing\\\},with empty blocks discarded; for a single vertexbb, writeℬ−\{b\}\\mathcal\{B\}\-\\\{b\\\}\. In the running example, the containments

I⁡\(a\)⊊I⁡\(u\),I⁡\(b\)⊊I⁡\(f\),I⁡\(e\)⊊I⁡\(g\)I\(a\)\\subsetneq I\(u\),\\qquad I\(b\)\\subsetneq I\(f\),\\qquad I\(e\)\\subsetneq I\(g\)are the concrete cases to keep in mind:u,f,gu,f,gare more constrained support\-superset vertices, so an optimum never needs to keep them instead of their smaller\-support witnesses\.

###### Theorem 1\(Dominance and incidence\-twin compression\)\.

The following two vertex\-level reductions preserve the optimal retention value\.

1. \(i\)\(Dominance removal\)If two verticesa,b∈Va,b\\in Vsatisfy I⁡\(a\)⊆I⁡\(b\),I\(a\)\\subseteq I\(b\),\(11\)then removingbbdoes not change the optimal retention value: α⁡\(ℬ\)=α⁡\(ℬ−\{b\}\)\.\\alpha\(\\mathcal\{B\}\)=\\alpha\(\\mathcal\{B\}\-\\\{b\\\}\)\.\(12\)
2. \(ii\)\(Incidence\-twin compression\)For the quotient family in Definition[4](https://arxiv.org/html/2609.17951#Thmdefinition4), α⁡\(ℬ¯\)=α⁡\(ℬ\)\.\\alpha\(\\overline\{\\mathcal\{B\}\}\)=\\alpha\(\\mathcal\{B\}\)\.\(13\)

###### Proof\.

For \(i\), any feasible retained set inℬ−\{b\}\\mathcal\{B\}\-\\\{b\\\}is feasible inℬ\\mathcal\{B\}, soα⁡\(ℬ−\{b\}\)≤α⁡\(ℬ\)\.\\alpha\(\\mathcal\{B\}\-\\\{b\\\}\)\\leq\\alpha\(\\mathcal\{B\}\)\.LetO⋆O^\{\\star\}be an optimal feasible set forℬ\\mathcal\{B\}\. Ifb∉O⋆b\\notin O^\{\\star\}, thenO⋆O^\{\\star\}is feasible forℬ−\{b\}\\mathcal\{B\}\-\\\{b\\\}and we are done\. Assumeb∈O⋆b\\in O^\{\\star\}and define

O′:=\(O⋆∖\{b\}\)∪\{a\}\.O^\{\\prime\}:=\(O^\{\\star\}\\setminus\\\{b\\\}\)\\cup\\\{a\\\}\.\(14\)For any indexi∈I⁡\(a\)i\\in I\(a\), we havei∈I⁡\(b\)i\\in I\(b\)byI⁡\(a\)⊆I⁡\(b\)I\(a\)\\subseteq I\(b\)\. Sinceb∈O⋆b\\in O^\{\\star\}andO⋆O^\{\\star\}is feasible, no other element ofO⋆O^\{\\star\}can lie inBiB\_\{i\}; replacingbbbyaakeeps occupancy at most one in such blocks\. All other blocks are unaffected\. HenceO′O^\{\\prime\}is feasible forℬ\\mathcal\{B\}and\|O′\|=\|O⋆\|\|O^\{\\prime\}\|=\|O^\{\\star\}\|, withb∉O′b\\notin O^\{\\prime\}\. Therefore there exists an optimal solution not usingbb, implyingα⁡\(ℬ−\{b\}\)≥α⁡\(ℬ\)\.\\alpha\(\\mathcal\{B\}\-\\\{b\\\}\)\\geq\\alpha\(\\mathcal\{B\}\)\.Combining both inequalities gives equality\.

For \(ii\), letπ:V→V¯\\pi:V\\to\\overline\{V\}be the projectionπ⁡\(v\)=\[v\]\\pi\(v\)=\[v\]\. First letR⊆VR\\subseteq Vbe feasible forℬ\\mathcal\{B\}\. No two distinct vertices inRRcan lie in the same incidence\-twin class: ifu∼vu\\sim vandu≠vu\\neq v, thenI⁡\(u\)=I⁡\(v\)≠∅I\(u\)=I\(v\)\\neq\\varnothing, souuandvvco\-occur in every block indexed by this common support, contradicting feasibility\. Hence\|π⁡\(R\)\|=\|R\|\|\\pi\(R\)\|=\|R\|\. Moreover, ifπ⁡\(R\)\\pi\(R\)contained two classes in some quotient blockB¯i\\overline\{B\}\_\{i\}, thenRRwould contain two vertices in the original blockBiB\_\{i\}, again contradicting feasibility\. Thusπ⁡\(R\)\\pi\(R\)is feasible forℬ¯\\overline\{\\mathcal\{B\}\}, soα⁡\(ℬ¯\)≥α⁡\(ℬ\)\\alpha\(\\overline\{\\mathcal\{B\}\}\)\\geq\\alpha\(\\mathcal\{B\}\)\.

Conversely, letR¯⊆V¯\\overline\{R\}\\subseteq\\overline\{V\}be feasible forℬ¯\\overline\{\\mathcal\{B\}\}, and choose one representative vertexρ⁡\(C\)∈C\\rho\(C\)\\in Cfrom each classC∈R¯C\\in\\overline\{R\}\. Set

R:=\{ρ⁡\(C\):C∈R¯\}\.R:=\\\{\\rho\(C\):C\\in\\overline\{R\}\\\}\.IfRRcontained two vertices in some original blockBiB\_\{i\}, thenR¯\\overline\{R\}would contain the two corresponding classes inB¯i\\overline\{B\}\_\{i\}, violating feasibility ofR¯\\overline\{R\}\. ThereforeRRis feasible forℬ\\mathcal\{B\}and\|R\|=\|R¯\|\|R\|=\|\\overline\{R\}\|, soα⁡\(ℬ\)≥α⁡\(ℬ¯\)\\alpha\(\\mathcal\{B\}\)\\geq\\alpha\(\\overline\{\\mathcal\{B\}\}\)\. Combining the two inequalities proves equality\. ∎

Part \(ii\) can also be read as repeated application of part \(i\): within each classCC, choose one representativerCr\_\{C\}and delete every otherv∈Cv\\in C, sinceI⁡\(rC\)=I⁡\(v\)I\(r\_\{C\}\)=I\(v\)\. The explicit quotient notation is still useful algorithmically because it records the deleted vertex ids for later materialization\.

The next characterization concerns blocks containing a vertex that appears nowhere else\. When incidence\-twin compression has been applied, degrees, block weights, and multiplicity counts are understood on the quotient family, with bars omitted for readability\. Let

ℬ1:=\{B∈ℬ:w⁡\(B\)=1\},\\mathcal\{B\}\_\{1\}:=\\\{B\\in\\mathcal\{B\}:w\(B\)=1\\\},\(16\)and for eachB∈ℬ1B\\in\\mathcal\{B\}\_\{1\}, choose one vertexzB∈Bz\_\{B\}\\in Bwithd⁡\(zB\)=1d\(z\_\{B\}\)=1\.

###### Theorem 2\(Canonical optimal form for weight\-1 blocks\)\.

There exists an optimal feasible setO⋆O^\{\\star\}such that

zB∈O⋆∀B∈ℬ1\.z\_\{B\}\\in O^\{\\star\}\\qquad\\forall B\\in\\mathcal\{B\}\_\{1\}\.\(17\)Equivalently, every weight\-1 block can be rooted by a weight\-1 vertex in an optimal solution\.

###### Proof\.

DefineZ:=\{zB:B∈ℬ1\}Z:=\\\{z\_\{B\}:B\\in\\mathcal\{B\}\_\{1\}\\\}\. Sinced⁡\(zB\)=1d\(z\_\{B\}\)=1, eachzBz\_\{B\}belongs only to its own blockBB\. Hence no two elements ofZZcan collide in any block, soZZis feasible\.

Among all optimal feasible sets, chooseOOmaximizing\|O∩Z\|\|O\\cap Z\|\. Suppose, for contradiction, that there existsB∈ℬ1B\\in\\mathcal\{B\}\_\{1\}withzB∉Oz\_\{B\}\\notin O\.

IfO∩B=∅O\\cap B=\\varnothing, thenO∪\{zB\}O\\cup\\\{z\_\{B\}\\\}is feasible \(becausezBz\_\{B\}appears only inBB\), which contradicts optimality ofOO\.

ThereforeO∩B=\{xB\}O\\cap B=\\\{x\_\{B\}\\\}for somexB≠zBx\_\{B\}\\neq z\_\{B\}\. Consider

O′:=\(O∖\{xB\}\)∪\{zB\}\.O^\{\\prime\}:=\(O\\setminus\\\{x\_\{B\}\\\}\)\\cup\\\{z\_\{B\}\\\}\.\(18\)This set is feasible: replacingxBx\_\{B\}byzBz\_\{B\}affects only blockBB, where the occupancy remains one, and in every other block feasibility can only improve becausexBx\_\{B\}is removed\. Also,\|O′\|=\|O\|\|O^\{\\prime\}\|=\|O\|, soO′O^\{\\prime\}is optimal\. But now\|O′∩Z\|=\|O∩Z\|\+1\|O^\{\\prime\}\\cap Z\|=\|O\\cap Z\|\+1, contradicting the choice ofOO\.

HencezB∈Oz\_\{B\}\\in Ofor everyB∈ℬ1B\\in\\mathcal\{B\}\_\{1\}\. TakingO⋆:=OO^\{\\star\}:=Oproves the claim\. ∎

In the running example,B1=\{a,u\}B\_\{1\}=\\\{a,u\\\}andd⁡\(a\)=1d\(a\)=1\. If an optimal solution useduuto cover the local conflict inB1B\_\{1\}, replacinguubyaacannot create any new conflict becauseaaappears nowhere else\. Thus one may canonically rootB1B\_\{1\}ataabefore considering the higher\-weight layers\.

The preceding results characterize vertex dominance/twin compression and canonical weight\-1 roots\. The next rule gives a pivot\-level canonicalization test built directly from Theorem[1](https://arxiv.org/html/2609.17951#Thmtheorem1): after deleting vertices dominated by a chosen pivot, a simple block condition guarantees an optimal solution containing that pivot\.

For a pivot vertexa∈Va\\in V, define the vertices dominated byaa, the incident\-block neighborhood ofaa, and the residual blockers ofaaby

D⁡\(a\):=\{v∈V∖\{a\}:I⁡\(a\)⊆I⁡\(v\)\},Γ⁡\(a\):=⋃i∈I⁡\(a\)Bi,R⁡\(a\):=Γ⁡\(a\)∖\(\{a\}∪D⁡\(a\)\)\.D\(a\):=\\\{v\\in V\\setminus\\\{a\\\}:I\(a\)\\subseteq I\(v\)\\\},\\qquad\\Gamma\(a\):=\\bigcup\_\{i\\in I\(a\)\}B\_\{i\},\\qquad R\(a\):=\\Gamma\(a\)\\setminus\(\\\{a\\\}\\cup D\(a\)\)\.\(19\)ThusD⁡\(a\)D\(a\)is exactly the set of vertices removable by Theorem[1](https://arxiv.org/html/2609.17951#Thmtheorem1)\(i\) usingaaas dominator, whileR⁡\(a\)R\(a\)is the set of remaining possible blockers ofaaafter that dominance removal\.

###### Theorem 3\(Pivot dominance closure and canonical inclusion\)\.

For any pivota∈Va\\in V, the following hold\.

1. \(i\)\(Closure under dominance removal\) α⁡\(ℬ\)=α⁡\(ℬ−D⁡\(a\)\)\.\\alpha\(\\mathcal\{B\}\)=\\alpha\\\!\\left\(\\mathcal\{B\}\-D\(a\)\\right\)\.\(20\)
2. \(ii\)\(Sufficient condition for an optimal set containingaa\)If there exists a blockB∗∈ℬB^\{\*\}\\in\\mathcal\{B\}such that R⁡\(a\)⊆B∗,R\(a\)\\subseteq B^\{\*\},\(21\)then there exists an optimal feasible setO⋆O^\{\\star\}witha∈O⋆a\\in O^\{\\star\}\.

###### Proof\.

For \(i\), remove vertices inD⁡\(a\)D\(a\)one\-by\-one\. For each removed vertexv∈D⁡\(a\)v\\in D\(a\), one hasI⁡\(a\)⊆I⁡\(v\),I\(a\)\\subseteq I\(v\),so Theorem[1](https://arxiv.org/html/2609.17951#Thmtheorem1)\(i\) applies with pivotaa, and the optimum value is preserved at each step\. SinceD⁡\(a\)D\(a\)is finite, the final reduced instance satisfiesα⁡\(ℬ\)=α⁡\(ℬ−D⁡\(a\)\)\.\\alpha\(\\mathcal\{B\}\)=\\alpha\(\\mathcal\{B\}\-D\(a\)\)\.

For \(ii\), letℬ′\\mathcal\{B\}^\{\\prime\}denote the reduced instance after removingD⁡\(a\)D\(a\)\. By \(i\),α⁡\(ℬ′\)=α⁡\(ℬ\)\\alpha\(\\mathcal\{B\}^\{\\prime\}\)=\\alpha\(\\mathcal\{B\}\)\. Take an optimal feasible setOOforℬ′\\mathcal\{B\}^\{\\prime\}\. Ifa∈Oa\\in O, we are done\.

Assumea∉Oa\\notin O\. SinceOOis feasible andB∗B^\{\*\}is a block,\|O∩B∗\|≤1\|O\\cap B^\{\*\}\|\\leq 1\.

IfO∩B∗=∅O\\cap B^\{\*\}=\\varnothing, thenO∩R⁡\(a\)=∅O\\cap R\(a\)=\\varnothingbecauseR⁡\(a\)⊆B∗R\(a\)\\subseteq B^\{\*\}\. Addingaakeeps feasibility: any potential conflict withaamust come from a block containingaa, hence fromΓ⁡\(a\)\\Gamma\(a\), butD⁡\(a\)D\(a\)was removed andOOhas no element inR⁡\(a\)R\(a\)\. ThusO∪\{a\}O\\cup\\\{a\\\}is feasible, contradicting optimality\.

SoO∩B∗=\{x\}O\\cap B^\{\*\}=\\\{x\\\}for somexx\. Ifx∈B∗∖Γ⁡\(a\)x\\in B^\{\*\}\\setminus\\Gamma\(a\), thenxxis in no block containingaa, so the same argument showsO∪\{a\}O\\cup\\\{a\\\}is feasible, again contradicting optimality\. Therefore necessarily

x∈R⁡\(a\)⊆B∗\.x\\in R\(a\)\\subseteq B^\{\*\}\.Define

O′:=\(O∖\{x\}\)∪\{a\}\.O^\{\\prime\}:=\(O\\setminus\\\{x\\\}\)\\cup\\\{a\\\}\.\(22\)Any block containingaacan intersectOOonly atxx: its members lie inΓ⁡\(a\)\\Gamma\(a\); elements ofD⁡\(a\)D\(a\)are absent inℬ′\\mathcal\{B\}^\{\\prime\}; and\|O∩R⁡\(a\)\|=1\|O\\cap R\(a\)\|=1becauseR⁡\(a\)⊆B∗R\(a\)\\subseteq B^\{\*\}andO∩B∗=\{x\}O\\cap B^\{\*\}=\\\{x\\\}\. HenceO′O^\{\\prime\}is feasible and\|O′\|=\|O\|=α⁡\(ℬ′\)\|O^\{\\prime\}\|=\|O\|=\\alpha\(\\mathcal\{B\}^\{\\prime\}\)\. Soℬ′\\mathcal\{B\}^\{\\prime\}has an optimal set containingaa, and by value equivalence this is also optimal for the original instance\. ∎

For the equality case below, write

ℬ′:=ℬ−D⁡\(a\)\\mathcal\{B\}^\{\\prime\}:=\\mathcal\{B\}\-D\(a\)for the pivot\-reduced instance\.

###### Corollary 1\(Equality case of pivot canonicalization\)\.

If Theorem[3](https://arxiv.org/html/2609.17951#Thmtheorem3)\(ii\) holds with

then every optimal feasible setOOforℬ′\\mathcal\{B\}^\{\\prime\}witha∉Oa\\notin Osatisfies

\|O∩R⁡\(a\)\|=1\.\|O\\cap R\(a\)\|=1\.In particular, swapping that unique element withaayields an optimal feasible set containingaa\.

###### Proof\.

By feasibility andB∗=R⁡\(a\)B^\{\*\}=R\(a\), one has\|O∩R⁡\(a\)\|≤1\|O\\cap R\(a\)\|\\leq 1\. If the intersection were empty, thenO∪\{a\}O\\cup\\\{a\\\}would be feasible inℬ′\\mathcal\{B\}^\{\\prime\}\(same argument as in the theorem proof\), contradicting optimality\. Hence the intersection size is exactly one, and the swap conclusion follows from Theorem[3](https://arxiv.org/html/2609.17951#Thmtheorem3)\(ii\)\. ∎

The equality case also has a useful downstream consequence for the closed\-form block\-weight bound introduced in the next section\. In the equality caseB∗=R⁡\(a\)B^\{\*\}=R\(a\), one may canonically keepaa, deleteD⁡\(a\)D\(a\), and then apply Theorem[5](https://arxiv.org/html/2609.17951#Thmtheorem5)to the reduced instanceℬ−D⁡\(a\)\\mathcal\{B\}\-D\(a\)\. This yields a weakly smaller computable upper bound than applying Theorem[5](https://arxiv.org/html/2609.17951#Thmtheorem5)directly to the original family, although the improvement is only local and typically marginal\.

###### Example 2\(Dominance closure and equality\-case swapping\)\.

Let

ℬ=\{\{a,d,u,v\},\{a,d\},\{u,v\},\{u,x\},\{v,y\},\{x,y\}\}\.\\mathcal\{B\}=\\bigl\\\{\\\{a,d,u,v\\\},\\\{a,d\\\},\\\{u,v\\\},\\\{u,x\\\},\\\{v,y\\\},\\\{x,y\\\}\\bigr\\\}\.All vertices have incidence degree at least two\. For pivotaa,

I⁡\(a\)=\{1,2\},I⁡\(d\)=\{1,2\},I\(a\)=\\\{1,2\\\},\\qquad I\(d\)=\\\{1,2\\\},sod∈D⁡\(a\)d\\in D\(a\)and dominance removal deletesddwithout changing the optimum\. In the reduced instance,R⁡\(a\)=\{u,v\}R\(a\)=\\\{u,v\\\}, and this set is exactly the blockB∗=\{u,v\}B^\{\*\}=\\\{u,v\\\}\. Theorem[3](https://arxiv.org/html/2609.17951#Thmtheorem3)\(ii\) therefore guarantees an optimal feasible set containingaa\.

The equality\-case corollary describes the only obstruction to already addingaa\. Any optimum excludingaamust contain exactly one vertex from\{u,v\}\\\{u,v\\\}\. For example,\{u,y\}\\\{u,y\\\}is feasible and optimal in the reduced instance; swapping the unique elementu∈R⁡\(a\)u\\in R\(a\)withaagives the equally large optimum\{a,y\}\\\{a,y\\\}\.

This dominance theorem also explains why we do not state separate private\-shadow certificates\. If a blockeruuof a pivotaahas a shadowzzoutsideΓ⁡\(a\)\\Gamma\(a\)with

I⁡\(z\)⊆I⁡\(u\)∖I⁡\(a\),I\(z\)\\subseteq I\(u\)\\setminus I\(a\),thenI⁡\(z\)⊆I⁡\(u\)I\(z\)\\subseteq I\(u\), souuis already removable by Theorem[1](https://arxiv.org/html/2609.17951#Thmtheorem1)\(i\)\. Thus such shadow arguments are best viewed as dominance preprocessing followed by the pivot canonicalization above, not as independent structural rules\.

The final characterization separates structural optimality from algorithmic attainability\. It identifies an incidence\-block pattern whose optimum is certified exactly, regardless of whether a particular greedy chronology finds the displayed optimal set\.

We first fix the reduced\-instance notation used in the certificate\. Perform vertex\-level dominance suppression by choosing a setD⊆VD\\subseteq Vsuch that everyv∈Dv\\in Dhas a surviving witnessr⁡\(v\)∈V∖Dr\(v\)\\in V\\setminus Dwith

I⁡\(r⁡\(v\)\)⊆I⁡\(v\)\.I\(r\(v\)\)\\subseteq I\(v\)\.Define the dominance\-reduced block family by

ℬ−:=\{B∖D:B∈ℬ,B∖D≠∅\},\\mathcal\{B\}^\{\-\}:=\\\{B\\setminus D:\\ B\\in\\mathcal\{B\},\\ B\\setminus D\\neq\\varnothing\\\},index it as

ℬ−=\{Bi−:i∈ℐ−\},\\mathcal\{B\}^\{\-\}=\\\{B\_\{i\}^\{\-\}:i\\in\\mathcal\{I\}^\{\-\}\\\},and letI−​\(v\)I\_\{\-\}\(v\),d−​\(v\)d\_\{\-\}\(v\), andw−​\(⋅\)w\_\{\-\}\(\\cdot\)denote incidence sets, degrees, and block weights computed insideℬ−\\mathcal\{B\}^\{\-\}\. Suppose the block\-index setℐ−\\mathcal\{I\}^\{\-\}is partitioned into nonempty blocks

𝒥1,…,𝒥m,\\mathcal\{J\}\_\{1\},\\dots,\\mathcal\{J\}\_\{m\},and for eacht∈\{1,…,m\}t\\in\\\{1,\\dots,m\\\}there exists a surviving vertexzt∈V∖Dz\_\{t\}\\in V\\setminus Dsuch that

I−​\(zt\)=𝒥t\.I\_\{\-\}\(z\_\{t\}\)=\\mathcal\{J\}\_\{t\}\.Set

Z:=\{z1,…,zm\}\.Z:=\\\{z\_\{1\},\\dots,z\_\{m\}\\\}\.The following certificate says that, after support\-superset suppression, these block representatives already form an optimum\.

###### Theorem 4\(Dominance\-reduced incidence\-block optimality certificate\)\.

Assume that every reduced block in the same block has block\-size weight:

w−​\(Bi−\)=\|𝒥t\|∀t∈\{1,…,m\},∀i∈𝒥t\.w\_\{\-\}\(B\_\{i\}^\{\-\}\)=\|\\mathcal\{J\}\_\{t\}\|\\qquad\\forall t\\in\\\{1,\\dots,m\\\},\\ \\forall i\\in\\mathcal\{J\}\_\{t\}\.ThenZZis a maximum feasible set for the reduced family and for the original family\. In particular,

α⁡\(ℬ\)=m\.\\alpha\(\\mathcal\{B\}\)=m\.\(23\)

###### Proof\.

For everyv∈Dv\\in D, the witnessr⁡\(v\)r\(v\)survives the suppression pass and satisfiesI⁡\(r⁡\(v\)\)⊆I⁡\(v\)I\(r\(v\)\)\\subseteq I\(v\)\. Deleting the vertices ofDDone by one is therefore value\-preserving by Theorem[1](https://arxiv.org/html/2609.17951#Thmtheorem1)\(i\), and empty blocks impose no feasibility constraint\. Hence

α⁡\(ℬ−\)=α⁡\(ℬ\)\.\\alpha\(\\mathcal\{B\}^\{\-\}\)=\\alpha\(\\mathcal\{B\}\)\.
Inℬ−\\mathcal\{B\}^\{\-\}, eachztz\_\{t\}has support𝒥t\\mathcal\{J\}\_\{t\}\. HenceZZis feasible: ifi∈𝒥ti\\in\\mathcal\{J\}\_\{t\}, thenzs∈Bi−z\_\{s\}\\in B\_\{i\}^\{\-\}iffi∈I−​\(zs\)=𝒥si\\in I\_\{\-\}\(z\_\{s\}\)=\\mathcal\{J\}\_\{s\}, which happens only fors=ts=tbecause the blocks form a partition\.

Now letOObe any feasible set forℬ−\\mathcal\{B\}^\{\-\}\. Assign one unit of charge to eachv∈Ov\\in Oand distribute it evenly over thed−​\(v\)d\_\{\-\}\(v\)reduced blocks containingvv\. Each block receives charge from at most one retained vertex\. Ifi∈𝒥ti\\in\\mathcal\{J\}\_\{t\}andO∩Bi−=\{v\}O\\cap B\_\{i\}^\{\-\}=\\\{v\\\}, then

d−​\(v\)≥w−​\(Bi−\)=\|𝒥t\|,d\_\{\-\}\(v\)\\geq w\_\{\-\}\(B\_\{i\}^\{\-\}\)=\|\\mathcal\{J\}\_\{t\}\|,so the reduced block receives at most1/\|𝒥t\|1/\|\\mathcal\{J\}\_\{t\}\|charge\. Therefore the total charge received by reduced blocks in block𝒥t\\mathcal\{J\}\_\{t\}is at most

∑i∈𝒥t1\|𝒥t\|=1\.\\sum\_\{i\\in\\mathcal\{J\}\_\{t\}\}\\frac\{1\}\{\|\\mathcal\{J\}\_\{t\}\|\}=1\.Summing over themmblocks gives\|O\|≤m\|O\|\\leq m\. SinceZZis feasible inℬ−\\mathcal\{B\}^\{\-\}and\|Z\|=m\|Z\|=m, it is maximum inℬ−\\mathcal\{B\}^\{\-\}\. The dominance deletion givesα⁡\(ℬ\)=α⁡\(ℬ−\)=m\\alpha\(\\mathcal\{B\}\)=\\alpha\(\\mathcal\{B\}^\{\-\}\)=m\. BecauseZ∩D=∅Z\\cap D=\\varnothing, the same setZZis feasible for the original familyℬ\\mathcal\{B\}as well\. ∎

Example 1\(c\) \(Running example: dominance\-reduced incidence blocks\)\.Return to the running example in Example[2](https://arxiv.org/html/2609.17951#S2)\. First perform the support\-superset suppression

because

I⁡\(a\)\\displaystyle I\(a\)=\{1\}⊊I⁡\(u\)=\{1,2\},\\displaystyle=\\\{1\\\}\\subsetneq I\(u\)=\\\{1,2\\\},I⁡\(b\)\\displaystyle I\(b\)=\{2,3\}⊊I⁡\(f\)=\{2,3,9\},\\displaystyle=\\\{2,3\\\}\\subsetneq I\(f\)=\\\{2,3,9\\\},I⁡\(e\)\\displaystyle I\(e\)=\{4,5\}⊊I⁡\(g\)=\{4,5,10\}\.\\displaystyle=\\\{4,5\\\}\\subsetneq I\(g\)=\\\{4,5,10\\\}\.The reduced familyℬ−\\mathcal\{B\}^\{\-\}keeps the same block labels\. Inℬ−\\mathcal\{B\}^\{\-\}, take the same block partition later used by the greedy trace:

𝒥1=\{1\},𝒥2=\{2,3\},𝒥3=\{4,5\},𝒥4=\{6,7,8\},𝒥5=\{9,10,11,12\},\\mathcal\{J\}\_\{1\}=\\\{1\\\},\\qquad\\mathcal\{J\}\_\{2\}=\\\{2,3\\\},\\qquad\\mathcal\{J\}\_\{3\}=\\\{4,5\\\},\\qquad\\mathcal\{J\}\_\{4\}=\\\{6,7,8\\\},\\qquad\\mathcal\{J\}\_\{5\}=\\\{9,10,11,12\\\},with representatives

z1=a,z2=b,z3=e,z4=c,z5=r\.z\_\{1\}=a,\\qquad z\_\{2\}=b,\\qquad z\_\{3\}=e,\\qquad z\_\{4\}=c,\\qquad z\_\{5\}=r\.The reduced family satisfies the block\-size weight condition:

w−​\(B1\)\\displaystyle w\_\{\-\}\(B\_\{1\}\)=1,w−\(B2\)=⋯=w−\(B5\)=2,\\displaystyle=1,\\qquad w\_\{\-\}\(B\_\{2\}\)=\\cdots=w\_\{\-\}\(B\_\{5\}\)=2,w−​\(B6\)\\displaystyle w\_\{\-\}\(B\_\{6\}\)=w−\(B7\)=w−\(B8\)=3,w−\(B9\)=⋯=w−\(B12\)=4\.\\displaystyle=w\_\{\-\}\(B\_\{7\}\)=w\_\{\-\}\(B\_\{8\}\)=3,\\qquad w\_\{\-\}\(B\_\{9\}\)=\\cdots=w\_\{\-\}\(B\_\{12\}\)=4\.Thus Theorem[4](https://arxiv.org/html/2609.17951#Thmtheorem4)certifies

Z=\{a,b,e,c,r\}Z=\\\{a,b,e,c,r\\\}as a maximum feasible set and gives

α⁡\(ℬ\)=5\.\\alpha\(\\mathcal\{B\}\)=5\.The unreduced closed\-form sum is larger,U⁡\(ℬ\)=31/6U\(\\mathcal\{B\}\)=31/6, becauseffandggartificially lower the weights ofB9B\_\{9\}andB10B\_\{10\}from44to33\. The dominance\-reduced certificate removes exactly this distortion\. Section 5 shows that the greedy layered clustering algorithm realizes the same suppression intrinsically: the low\-weight rootsa,b,ea,b,eabsorbu,f,gu,f,gbefore the higher\-weight layers are processed\.

Except for incidence\-twin compression and the weight\-1 canonical form, which are used below as preprocessing and first certificate steps, these exact characterization rules are optional tools: they can shrink or partially canonicalize an instance without changing the optimum, but the scalable certificates and algorithms below do not rely on the more expensive dominance\-closure preprocessing being applied\.

## 4Bounds and Certificates for Maximum Strong Independent Sets

### 4\.1Closed\-Form and Low\-Weight Certificates

Exact characterizations are useful when their hypotheses hold; at billion\-vertex scale we also need certificates that are cheap to compute on arbitrary block families\. With block weight already defined, the first certificate is the closed\-form block\-weight sum\.

###### Definition 5\(Closed\-form upper\-bound value\)\.

For any block familyℱ\\mathcal\{F\}with intrinsic degree functiondℱ​\(⋅\)d\_\{\\mathcal\{F\}\}\(\\cdot\)and induced block weights

wℱ​\(B\):=minv∈B⁡dℱ​\(v\),w\_\{\\mathcal\{F\}\}\(B\):=\\min\_\{v\\in B\}d\_\{\\mathcal\{F\}\}\(v\),\(24\)define

U⁡\(ℱ\):=∑B∈ℱ1wℱ​\(B\)\.U\(\\mathcal\{F\}\):=\\sum\_\{B\\in\\mathcal\{F\}\}\\frac\{1\}\{w\_\{\\mathcal\{F\}\}\(B\)\}\.\(25\)In particular, for the ambient familyℬ\\mathcal\{B\}this is exactly

U⁡\(ℬ\)=∑B∈ℬ1w⁡\(B\)\.U\(\\mathcal\{B\}\)=\\sum\_\{B\\in\\mathcal\{B\}\}\\frac\{1\}\{w\(B\)\}\.\(26\)

###### Theorem 5\(Closed\-form upper bound\)\.

For every feasible retained setR⊆VR\\subseteq V,

\|R\|≤U⁡\(ℬ\)\.\|R\|\\leq U\(\\mathcal\{B\}\)\.\(27\)

###### Proof\.

Assign one unit of charge to each retained vertexv∈Rv\\in R, and distribute it evenly among thed⁡\(v\)d\(v\)blocks containingvv\. Each incident block receives charge1/d⁡\(v\)1/d\(v\)\. SinceRRis feasible, each block receives charge from at most one retained vertex\. Ifv∈R∩Bv\\in R\\cap B, then by definitionw⁡\(B\)≤d⁡\(v\)w\(B\)\\leq d\(v\), hence1/d⁡\(v\)≤1/w⁡\(B\)1/d\(v\)\\leq 1/w\(B\)\. Summing over all blocks, the total received charge is at mostU⁡\(ℬ\)U\(\\mathcal\{B\}\)\. On the other hand, each retained vertex contributes total charge 1, so the total charge equals\|R\|\|R\|\. ∎

The intuitive interpretation is straightforward\. A vertex with larged⁡\(v\)d\(v\)is globally entangled: choosing it consumes capacity across many blocks\. A block containing a degree\-1 or degree\-2 vertex is therefore structurally sharp and should be resolved early\.

Example 1\(d\) \(Running example: closed\-form bound\)\.Applying Theorem[5](https://arxiv.org/html/2609.17951#Thmtheorem5)directly to the unreduced running example gives

U⁡\(ℬ\)=1\+4⋅12\+5⋅13\+2⋅14=316\.U\(\\mathcal\{B\}\)=1\+4\\cdot\\frac\{1\}\{2\}\+5\\cdot\\frac\{1\}\{3\}\+2\\cdot\\frac\{1\}\{4\}=\\frac\{31\}\{6\}\.The dominance\-reduced certificate is sharper\. The representatives

z1=a,z2=b,z3=e,z4=c,z5=rz\_\{1\}=a,\\quad z\_\{2\}=b,\\quad z\_\{3\}=e,\\quad z\_\{4\}=c,\\quad z\_\{5\}=rhave supports

\{1\},\{2,3\},\{4,5\},\{6,7,8\},\{9,10,11,12\},\\\{1\\\},\\quad\\\{2,3\\\},\\quad\\\{4,5\\\},\\quad\\\{6,7,8\\\},\\quad\\\{9,10,11,12\\\},and their dominated support\-superset vertices include

u,f,gwithI⁡\(a\)⊊I⁡\(u\),I⁡\(b\)⊊I⁡\(f\),I⁡\(e\)⊊I⁡\(g\)\.u,\\ f,\\ g\\quad\\text\{with\}\\quad I\(a\)\\subsetneq I\(u\),\\ I\(b\)\\subsetneq I\(f\),\\ I\(e\)\\subsetneq I\(g\)\.After deletingu,f,gu,f,g, Theorem[4](https://arxiv.org/html/2609.17951#Thmtheorem4)applies to the reduced family and gives

U⁡\(ℬ−\)=1\+4⋅12\+3⋅13\+4⋅14=5\.U\(\\mathcal\{B\}^\{\-\}\)=1\+4\\cdot\\frac\{1\}\{2\}\+3\\cdot\\frac\{1\}\{3\}\+4\\cdot\\frac\{1\}\{4\}=5\.Thus the optimal value is already certified as

α⁡\(ℬ\)=5\.\\alpha\(\\mathcal\{B\}\)=5\.Section 5 will return to this same instance and show that the greedy layered clustering algorithm performs the same first\-order superset suppression and attains this value exactly\.

The canonical optimal form for weight\-1 blocks \(Theorem[2](https://arxiv.org/html/2609.17951#Thmtheorem2)\) yields the following computable preclusion bound\. Let

ℬ1:=\{B∈ℬ:w⁡\(B\)=1\},ℬ\>1:=ℬ∖ℬ1,V1:=⋃B∈ℬ1B\.\\mathcal\{B\}\_\{1\}:=\\\{B\\in\\mathcal\{B\}:w\(B\)=1\\\},\\qquad\\mathcal\{B\}\_\{\>1\}:=\\mathcal\{B\}\\setminus\\mathcal\{B\}\_\{1\},\\qquad V\_\{1\}:=\\bigcup\_\{B\\in\\mathcal\{B\}\_\{1\}\}B\.\(28\)For eachB∈ℬ\>1B\\in\\mathcal\{B\}\_\{\>1\}define the residual block

B∘:=B∖V1,B^\{\\circ\}:=B\\setminus V\_\{1\},\(29\)and keep only nonempty residual blocks

ℬ∘:=\{B∘:B∈ℬ\>1,B∘≠∅\}\.\\mathcal\{B\}^\{\\circ\}:=\\\{B^\{\\circ\}:B\\in\\mathcal\{B\}\_\{\>1\},\\ B^\{\\circ\}\\neq\\varnothing\\\}\.\(30\)Onℬ∘\\mathcal\{B\}^\{\\circ\}, residual vertex degrees equal the original degrees of the surviving vertices, so the residual block weights are

w∘​\(B∘\):=minv∈B∘⁡d⁡\(v\),w^\{\\circ\}\(B^\{\\circ\}\):=\\min\_\{v\\in B^\{\\circ\}\}d\(v\),\(31\)and

U⁡\(ℬ∘\)=∑B∘∈ℬ∘1w∘​\(B∘\)\.U\(\\mathcal\{B\}^\{\\circ\}\)=\\sum\_\{B^\{\\circ\}\\in\\mathcal\{B\}^\{\\circ\}\}\\frac\{1\}\{w^\{\\circ\}\(B^\{\\circ\}\)\}\.\(32\)
###### Corollary 2\(Weight\-1 preclusion bound\)\.

Every feasible retained setRRsatisfies

\|R\|≤\|ℬ1\|\+U⁡\(ℬ∘\)\.\|R\|\\leq\|\\mathcal\{B\}\_\{1\}\|\\;\+\\;U\(\\mathcal\{B\}^\{\\circ\}\)\.\(33\)Moreover,

\|ℬ1\|\+U⁡\(ℬ∘\)≤U⁡\(ℬ\),\|\\mathcal\{B\}\_\{1\}\|\\;\+\\;U\(\\mathcal\{B\}^\{\\circ\}\)\\leq U\(\\mathcal\{B\}\),\(34\)so this is never weaker than Theorem[5](https://arxiv.org/html/2609.17951#Thmtheorem5)\.

###### Proof\.

SplitRRasR=\(R∩V1\)∪\(R∖V1\)R=\(R\\cap V\_\{1\}\)\\,\\cup\\,\(R\\setminus V\_\{1\}\)\. For the first part, eachx∈R∩V1x\\in R\\cap V\_\{1\}belongs to at least one block inℬ1\\mathcal\{B\}\_\{1\}, hence

\|R∩V1\|≤∑B∈ℬ1\|R∩B\|≤\|ℬ1\|\.\|R\\cap V\_\{1\}\|\\leq\\sum\_\{B\\in\\mathcal\{B\}\_\{1\}\}\|R\\cap B\|\\leq\|\\mathcal\{B\}\_\{1\}\|\.\(35\)
Now considerR0:=R∖V1⊆V∖V1R\_\{0\}:=R\\setminus V\_\{1\}\\subseteq V\\setminus V\_\{1\}\. For everyB∈ℬ\>1B\\in\\mathcal\{B\}\_\{\>1\},

\|R0∩B∘\|=\|R0∩B\|≤1,\|R\_\{0\}\\cap B^\{\\circ\}\|=\|R\_\{0\}\\cap B\|\\leq 1,\(36\)soR0R\_\{0\}is feasible for residual blocksℬ∘\\mathcal\{B\}^\{\\circ\}\. Ifv∈V∖V1v\\in V\\setminus V\_\{1\}, thenvvis in no block ofℬ1\\mathcal\{B\}\_\{1\}, hence its degree overℬ∘\\mathcal\{B\}^\{\\circ\}is exactlyd⁡\(v\)d\(v\), and the block\-weight theorem applies with weightsw∘w^\{\\circ\}:

\|R0\|≤U⁡\(ℬ∘\)\.\|R\_\{0\}\|\\leq U\(\\mathcal\{B\}^\{\\circ\}\)\.\(37\)Adding both parts gives the claimed refined bound\.

For the second inequality,∑B∈ℬ11/w⁡\(B\)=\|ℬ1\|\\sum\_\{B\\in\\mathcal\{B\}\_\{1\}\}1/w\(B\)=\|\\mathcal\{B\}\_\{1\}\|\. Also for eachB∘B^\{\\circ\}induced fromB∈ℬ\>1B\\in\\mathcal\{B\}\_\{\>1\}, one has

w∘​\(B∘\)=minv∈B∘⁡d⁡\(v\)≥minv∈B⁡d⁡\(v\)=w⁡\(B\),w^\{\\circ\}\(B^\{\\circ\}\)=\\min\_\{v\\in B^\{\\circ\}\}d\(v\)\\geq\\min\_\{v\\in B\}d\(v\)=w\(B\),\(38\)thus1/w∘​\(B∘\)≤1/w⁡\(B\)1/w^\{\\circ\}\(B^\{\\circ\}\)\\leq 1/w\(B\), and summing yields the result\. ∎

The next corollary gives a complementary achievability certificate for residual weight\-2 structure\. Unlike the weight\-1 case, weight 2 alone does not force a canonical root in each block\. However, the degree\-2 vertices define an ordinary graph\-matching problem over block incidences in the sense of Edmonds’ blossom algorithm\[[9](https://arxiv.org/html/2609.17951#bib.bib9)\]\. The size of such a matching is always a feasible retained count, and it certifies optimality exactly when it saturates the integer closed\-form bound\.

For this certificate, let𝒞\\mathcal\{C\}be a residual block family on active universe

V𝒞:=⋃B∈𝒞B,V\_\{\\mathcal\{C\}\}:=\\bigcup\_\{B\\in\\mathcal\{C\}\}B,with intrinsic degreesd𝒞​\(⋅\)d\_\{\\mathcal\{C\}\}\(\\cdot\)and intrinsic block weightsw𝒞​\(⋅\)w\_\{\\mathcal\{C\}\}\(\\cdot\)\. Construct a graphG2​\(𝒞\)G\_\{2\}\(\\mathcal\{C\}\)whose vertices are the blocks in𝒞\\mathcal\{C\}and whose edges are the degree\-2 vertices: for each vertexvvwithd𝒞​\(v\)=2d\_\{\\mathcal\{C\}\}\(v\)=2and incident blocksBi,Bj∈𝒞B\_\{i\},B\_\{j\}\\in\\mathcal\{C\}, add an edge\(Bi,Bj\)\(B\_\{i\},B\_\{j\}\)labeled byvv\. Assume

w𝒞​\(B\)=2∀B∈𝒞,w\_\{\\mathcal\{C\}\}\(B\)=2\\qquad\\forall B\\in\\mathcal\{C\},and letMMbe any matching inG2​\(𝒞\)G\_\{2\}\(\\mathcal\{C\}\)\.

###### Corollary 3\(Saturated weight\-2 matching certificate\)\.

The vertices labeling the matched edges form a feasible retained set for𝒞\\mathcal\{C\}, and

\|M\|≤α⁡\(𝒞\)≤⌊\|𝒞\|2⌋=⌊U⁡\(𝒞\)⌋\.\|M\|\\leq\\alpha\(\\mathcal\{C\}\)\\leq\\left\\lfloor\\frac\{\|\\mathcal\{C\}\|\}\{2\}\\right\\rfloor=\\left\\lfloor U\(\\mathcal\{C\}\)\\right\\rfloor\.\(39\)Consequently, if\|M\|=⌊\|𝒞\|/2⌋\|M\|=\\lfloor\|\\mathcal\{C\}\|/2\\rfloor, then the matched vertices form an optimal retained set for𝒞\\mathcal\{C\}\.

###### Proof\.

Since every block in𝒞\\mathcal\{C\}has intrinsic weight22, Theorem[5](https://arxiv.org/html/2609.17951#Thmtheorem5)applied to𝒞\\mathcal\{C\}gives

α⁡\(𝒞\)≤U⁡\(𝒞\)=∑B∈𝒞12=\|𝒞\|2\.\\alpha\(\\mathcal\{C\}\)\\leq U\(\\mathcal\{C\}\)=\\sum\_\{B\\in\\mathcal\{C\}\}\\frac\{1\}\{2\}=\\frac\{\|\\mathcal\{C\}\|\}\{2\}\.The left side is an integer, so

α⁡\(𝒞\)≤⌊\|𝒞\|2⌋\.\\alpha\(\\mathcal\{C\}\)\\leq\\left\\lfloor\\frac\{\|\\mathcal\{C\}\|\}\{2\}\\right\\rfloor\.Now retain the vertex labeling each matched edge ofMM\. BecauseMMis a matching, no two selected degree\-2 vertices share an incident block\. Hence every block in𝒞\\mathcal\{C\}contains at most one selected vertex, so the selected vertices are feasible\. This gives\|M\|≤α⁡\(𝒞\)\|M\|\\leq\\alpha\(\\mathcal\{C\}\)\. If\|M\|=⌊\|𝒞\|/2⌋\|M\|=\\lfloor\|\\mathcal\{C\}\|/2\\rfloor, the feasible matching construction attains the integer upper bound and is therefore optimal\. ∎

As a minimal saturated example, take four blocks arranged in a cycle by degree\-2 vertices:

C1=\{x12,x41\},C2=\{x12,x23\},C3=\{x23,x34\},C4=\{x34,x41\}\.C\_\{1\}=\\\{x\_\{12\},x\_\{41\}\\\},\\quad C\_\{2\}=\\\{x\_\{12\},x\_\{23\}\\\},\\quad C\_\{3\}=\\\{x\_\{23\},x\_\{34\}\\\},\\quad C\_\{4\}=\\\{x\_\{34\},x\_\{41\}\\\}\.Every block has intrinsic weight22, soU⁡\(𝒞\)=2U\(\\mathcal\{C\}\)=2\. The matching\{\(C1,C2\),\(C3,C4\)\}\\\{\(C\_\{1\},C\_\{2\}\),\(C\_\{3\},C\_\{4\}\)\\\}, labeled byx12x\_\{12\}andx34x\_\{34\}, saturates the bound and certifies that\{x12,x34\}\\\{x\_\{12\},x\_\{34\}\\\}is optimal\.

This certificate is deliberately only sufficient\. It can hold in the presence of higher\-degree vertices, but it certifies optimality only when the degree\-2 layer already saturates the integer block\-weight bound\. It is therefore not a weight\-2 analogue of Corollary[2](https://arxiv.org/html/2609.17951#Thmcorollary2): there is no unconditional weight\-2 preclusion pass, no automatic additive term to peel off, and no guaranteed bound improvement from the mere fact that a block has weight 2\. Rather, Corollary[3](https://arxiv.org/html/2609.17951#Thmcorollary3)is an achievability check showing that, in the special saturated\-matching case, the closed\-form block\-weight bound is tight\.

The closed\-form and weight\-1 certificates above are evaluated on a fixed active block family\. The next subsection treats them as reusable primitives inside a residual search: support\-superset sharpening and iterative puncturing repeatedly modify the active family, recompute intrinsic weights, and keep the smallest resulting valid upper boundUpunctU\_\{\\mathrm\{punct\}\}\.

### 4\.2Layered Superset Sharpening and Puncturing

The cost discussion after Theorem[1](https://arxiv.org/html/2609.17951#Thmtheorem1)explains why we do not run full exact superset suppression as a global preprocessing pass\. The next algorithm uses the same dominance principle more selectively: it looks only at supports revealed by current block\-weight vertices, deletes the higher\-degree support\-superset vertices certified by those witnesses, and uses the resulting weight increases to sharpen the closed\-form certificate\. We abbreviate this procedure as LSS in the empirical tables\.

###### Algorithm 1\(Layered Superset Sharpening\)\.

Given an active block familyℱ=\{F1,…,Fm\}\\mathcal\{F\}=\\\{F\_\{1\},\\dots,F\_\{m\}\\\}whose closed\-form certificate will be evaluated after the surrounding routine has exhausted its weight\-1 preclusion step, perform the following pass\.

1. 1\.First perform incidence\-twin compression on the remaining active family, then compute vertex degrees dℱ​\(v\)=\|\{i:v∈Fi\}\|d\_\{\\mathcal\{F\}\}\(v\)=\|\\\{i:v\\in F\_\{i\}\\\}\|and block weightswℱ​\(Fi\)=minv∈Fi⁡dℱ​\(v\)w\_\{\\mathcal\{F\}\}\(F\_\{i\}\)=\\min\_\{v\\in F\_\{i\}\}d\_\{\\mathcal\{F\}\}\(v\)\.
2. 2\.Process block\-weight layers from smallest to largest\. In layerww, build a fresh local incidence map Jw\(v\):=\{i:v∈Fi,wℱ\(Fi\)=w\}\.J\_\{w\}\(v\):=\\\{i:v\\in F\_\{i\},\\ w\_\{\\mathcal\{F\}\}\(F\_\{i\}\)=w\\\}\.Maintain the accumulated support P⁡\(v\):=⋃λ≤wJλ​\(v\)P\(v\):=\\bigcup\_\{\\lambda\\leq w\}J\_\{\\lambda\}\(v\)over layers already scanned\.
3. 3\.Whenever a vertexaasatisfies \|P⁡\(a\)\|=dℱ​\(a\)=w,\|P\(a\)\|=d\_\{\\mathcal\{F\}\}\(a\)=w,its full live supportIℱ​\(a\)=P​\(a\)I\_\{\\mathcal\{F\}\}\(a\)=P\(a\)has been revealed exactly at its own block\-weight layer\. Such a vertex is a block\-weight witness for that support\.
4. 4\.Intersect the blocks in this revealed support, C⁡\(a\):=⋂i∈P⁡\(a\)Fi,C\(a\):=\\bigcap\_\{i\\in P\(a\)\}F\_\{i\},and delete every activeb∈C⁡\(a\)b\\in C\(a\)withdℱ​\(b\)\>wd\_\{\\mathcal\{F\}\}\(b\)\>wfrom the residual certificate family\. Exact identity/equal\-support cases are handled by the incidence\-twin compression step at the start of the pass\.
5. 5\.After a supportP⁡\(a\)P\(a\)has been processed, removeaafrom the accumulated map to save memory\. After a nonempty deletion pass, rebuild incidence twins, recompute degrees and block weights, and repeat until no block\-weight witness deletes a vertex\.

For the next result and its cost discussion, let

Iℱ:=∑F∈ℱ\|F\|I\_\{\\mathcal\{F\}\}:=\\sum\_\{F\\in\\mathcal\{F\}\}\|F\|denote the active incidence size for one sharpening pass, and letT∩T\_\{\\cap\}denote the total cost of the block intersections performed for newly revealed supports\. Letℱ♯\\mathcal\{F\}^\{\\sharp\}denote the terminal active family after Algorithm[1](https://arxiv.org/html/2609.17951#Thmalgorithm1)stops\. For a single nonempty deletion pass, writeℱ′\\mathcal\{F\}^\{\\prime\}for the family obtained after deleting the certified support\-superset vertices and discarding any empty blocks\.

###### Proposition 1\(Correctness and fixed point of layered superset sharpening\)\.

Every support\-superset deletion made by Algorithm[1](https://arxiv.org/html/2609.17951#Thmalgorithm1)preservesα⁡\(ℱ\)\\alpha\(\\mathcal\{F\}\)\. Moreover, ifℱ′\\mathcal\{F\}^\{\\prime\}is obtained fromℱ\\mathcal\{F\}by one nonempty deletion pass, then

∑F′∈ℱ′1wℱ′​\(F′\)≤∑F∈ℱ1wℱ​\(F\)\.\\sum\_\{F^\{\\prime\}\\in\\mathcal\{F\}^\{\\prime\}\}\\frac\{1\}\{w\_\{\\mathcal\{F\}^\{\\prime\}\}\(F^\{\\prime\}\)\}\\leq\\sum\_\{F\\in\\mathcal\{F\}\}\\frac\{1\}\{w\_\{\\mathcal\{F\}\}\(F\)\}\.Inℱ♯\\mathcal\{F\}^\{\\sharp\}, no active blockFF, block\-weight witnessa∈Fa\\in F, and active vertexbbsatisfy

dℱ♯​\(a\)=wℱ♯​\(F\),Iℱ♯​\(a\)⊊Iℱ♯​\(b\)\.d\_\{\\mathcal\{F\}^\{\\sharp\}\}\(a\)=w\_\{\\mathcal\{F\}^\{\\sharp\}\}\(F\),\\qquad I\_\{\\mathcal\{F\}^\{\\sharp\}\}\(a\)\\subsetneq I\_\{\\mathcal\{F\}^\{\\sharp\}\}\(b\)\.

###### Proof\.

Consider a deletion made when the support of a block\-weight witnessaais revealed in layerww\. The algorithm has

dℱ​\(a\)=\|P⁡\(a\)\|=w,P⁡\(a\)=Iℱ​\(a\),d\_\{\\mathcal\{F\}\}\(a\)=\|P\(a\)\|=w,\\qquad P\(a\)=I\_\{\\mathcal\{F\}\}\(a\),and it deletes only verticesbbin

C⁡\(a\)=⋂i∈P⁡\(a\)Fi\.C\(a\)=\\bigcap\_\{i\\in P\(a\)\}F\_\{i\}\.Thereforebbbelongs to every block containingaa, soIℱ​\(a\)⊆Iℱ​\(b\)I\_\{\\mathcal\{F\}\}\(a\)\\subseteq I\_\{\\mathcal\{F\}\}\(b\)\. Since the algorithm deletes onlybbwithdℱ​\(b\)\>w=dℱ​\(a\)d\_\{\\mathcal\{F\}\}\(b\)\>w=d\_\{\\mathcal\{F\}\}\(a\), the containment is strict, and Theorem[1](https://arxiv.org/html/2609.17951#Thmtheorem1)\(i\) permits deletingbbwithout changingα⁡\(ℱ\)\\alpha\(\\mathcal\{F\}\)\. Repeating the argument over all deletions and rebuild passes proves preservation of the optimum by induction\. Equal\-support vertices are already handled by the incidence\-twin quotient before each pass\.

Removing vertices from blocks cannot decrease the degree of any surviving vertex and can only increase, or leave unchanged, the minimum surviving degree in each nonempty block\. Hence each surviving block term is weakly decreased when recomputed inℱ′\\mathcal\{F\}^\{\\prime\}; empty blocks contribute nothing\. Thus the displayed closed\-form sum weakly decreases\.

It remains to prove the stated fixed\-point property\. Letℱ♯\\mathcal\{F\}^\{\\sharp\}be the active family after the final rebuild, incidence\-twin compression, and sharpening pass\. Suppose for contradiction that an active blockFF, a block\-weight witnessa∈Fa\\in F, and an active vertexbbsatisfy

a∈F,dℱ♯​\(a\)=wℱ♯​\(F\),Iℱ♯​\(a\)⊊Iℱ♯​\(b\)\.a\\in F,\\qquad d\_\{\\mathcal\{F\}^\{\\sharp\}\}\(a\)=w\_\{\\mathcal\{F\}^\{\\sharp\}\}\(F\),\\qquad I\_\{\\mathcal\{F\}^\{\\sharp\}\}\(a\)\\subsetneq I\_\{\\mathcal\{F\}^\{\\sharp\}\}\(b\)\.When the final pass reaches layerwℱ♯​\(F\)=dℱ♯​\(a\)w\_\{\\mathcal\{F\}^\{\\sharp\}\}\(F\)=d\_\{\\mathcal\{F\}^\{\\sharp\}\}\(a\), the full support ofaais revealed, andbbbelongs to every block in that support\. Henceb∈C⁡\(a\)b\\in C\(a\)anddℱ♯​\(b\)\>dℱ♯​\(a\)d\_\{\\mathcal\{F\}^\{\\sharp\}\}\(b\)\>d\_\{\\mathcal\{F\}^\{\\sharp\}\}\(a\), so the pass would deletebb\. This contradicts termination\.

∎

Equivalently, no higher\-degree support superset remains for the block\-weight supports inspected by the pass\. This is a certificate\-sharpening property, not a full dominance closure over all vertices: support containments whose smaller support is not a current block\-weight witness may remain because they do not affect the first\-order closed\-form certificate in the same way\.

The implementation cost is also local\. A pass first scans all active incidences to compute degrees and block weights, then scans each block once in its layer to update the accumulated supportsP⁡\(⋅\)P\(\\cdot\); this contributesO⁡\(Iℱ\)O\(I\_\{\\mathcal\{F\}\}\)\. For every newly revealed support, the algorithm intersects its incident blocks, contributing total workT∩T\_\{\\cap\}across the pass\. Applying a nonempty deletion set requires one additional linear scan of the active block lists\. Thus one pass costsO⁡\(Iℱ\+T∩\)O\(I\_\{\\mathcal\{F\}\}\+T\_\{\\cap\}\), with peak auxiliary memory given by the accumulated not\-yet\-fully\-revealed support frontier plus temporary intersection sets\.

By contrast, a brute\-force dominance oracle would materialize full supports for all vertices and testI⁡\(a\)⊆I⁡\(b\)I\(a\)\\subseteq I\(b\)over many vertex pairs, costingΩ⁡\(\|V\|2\)\\Omega\(\|V\|^\{2\}\)support comparisons in the worst case, even before accounting for support lengths\. Algorithm[1](https://arxiv.org/html/2609.17951#Thmalgorithm1)avoids this global pair table: it only performs intersections for supports as they become fully revealed by the layer order\.

On the running example, the preliminary weight\-1 preclusion removes the blockB1B\_\{1\}and clusters awayuuwith the rootaa\. Algorithm[1](https://arxiv.org/html/2609.17951#Thmalgorithm1)then starts on the residual family\. In layer22, the full supports of the block\-weight witnessesbbandeeare revealed:

I⁡\(b\)=\{2,3\},I⁡\(e\)=\{4,5\}\.I\(b\)=\\\{2,3\\\},\\qquad I\(e\)=\\\{4,5\\\}\.The intersectionsB2∩B3B\_\{2\}\\cap B\_\{3\}andB4∩B5B\_\{4\}\\cap B\_\{5\}contain the higher\-degree verticesffandgg, respectively\. Hence the pass deletesffandgg, raising the residual weights ofB9B\_\{9\}andB10B\_\{10\}from their apparent weight33to their reduced weight44\. This is the intended role of the algorithm: it sharpens the certificate where block\-weight witnesses expose a support\-superset distractor, without attempting a global dominance closure\.

Beyond the canonical weight\-1 layer, the closed\-form bound can be further sharpened by puncturing the block family: delete selected blocks, recompute the incidence weights on the residual family, and keep the smallest valid certificate encountered\. Puncturing does not require every surviving block to keep its original weight\. The validity comes from monotonicity of the feasible region under deletion, while the tightening comes from searching for a residual family whose recomputed certificate is smaller\.

For the certificate below, consider a residual instance obtained fromℬ\\mathcal\{B\}by deleting blocks and by applying weight\-1 preclusion to fixqqroots and remove their clustered vertices from all remaining blocks\. Let𝒞\\mathcal\{C\}be the remaining nonempty block family, and assume every still\-active vertex is incident to at least one block of𝒞\\mathcal\{C\}\. Its intrinsic degrees, block weights, and closed\-form value are

d𝒞​\(v\):=\|\{B∈𝒞:v∈B\}\|,w𝒞​\(B\):=minv∈B⁡d𝒞​\(v\),d\_\{\\mathcal\{C\}\}\(v\):=\\bigl\|\\\{B\\in\\mathcal\{C\}:v\\in B\\\}\\bigr\|,\\qquad w\_\{\\mathcal\{C\}\}\(B\):=\\min\_\{v\\in B\}d\_\{\\mathcal\{C\}\}\(v\),\(40\)and

U⁡\(𝒞\):=∑B∈𝒞1w𝒞​\(B\)\.U\(\\mathcal\{C\}\):=\\sum\_\{B\\in\\mathcal\{C\}\}\\frac\{1\}\{w\_\{\\mathcal\{C\}\}\(B\)\}\.\(41\)If the residual instance is additionally processed by repeated weight\-1 preclusion, write𝒞∘\\mathcal\{C\}^\{\\circ\}for the final nonempty residual family\.

###### Proposition 2\(Punctured\-family upper\-bound certificate\)\.

α⁡\(ℬ\)≤q\+α⁡\(𝒞\)≤q\+U⁡\(𝒞\)\.\\alpha\(\\mathcal\{B\}\)\\leq q\+\\alpha\(\\mathcal\{C\}\)\\leq q\+U\(\\mathcal\{C\}\)\.\(42\)In particular,

α⁡\(ℬ\)≤q\+U⁡\(𝒞∘\)\.\\alpha\(\\mathcal\{B\}\)\\leq q\+U\(\\mathcal\{C\}^\{\\circ\}\)\.\(43\)

###### Proof\.

Each weight\-1 preclusion step charges at most one retained vertex to the precluded block, so all precluded parts contribute at mostqqretained vertices\. After these charged vertices are removed, deleting blocks only relaxes the remaining feasibility constraints\. Hence the uncharged part of any feasible retained set for the original family is feasible for the residual family𝒞\\mathcal\{C\}on its active universe, giving

α⁡\(ℬ\)≤q\+α⁡\(𝒞\)\.\\alpha\(\\mathcal\{B\}\)\\leq q\+\\alpha\(\\mathcal\{C\}\)\.Because every still\-active vertex is incident to at least one block of𝒞\\mathcal\{C\}, Theorem[5](https://arxiv.org/html/2609.17951#Thmtheorem5)applies to the residual instance with degrees and weights computed inside𝒞\\mathcal\{C\}, yieldingα⁡\(𝒞\)≤U⁡\(𝒞\)\\alpha\(\\mathcal\{C\}\)\\leq U\(\\mathcal\{C\}\)\. The final statement is the same argument applied after repeated weight\-1 preclusion\. ∎

Proposition[2](https://arxiv.org/html/2609.17951#Thmproposition2)turns bound sharpening into a certificate\-search problem\. The next algorithm is the practical iterative search used in our implementation\. It processes current block\-weight layers from high to low and, within each layer, dynamically chooses the block with the smallest current minimum\-degree count\. It accepts punctures that do not increase the current certificate, including zero\-gain punctures that expose new weight\-1 blocks; those blocks are precluded at the next rebuild and can unlock a strictly smaller certificate\. The returned value is the*iterative puncturing bound*, denotedUpunctU\_\{\\mathrm\{punct\}\}, namely the smallest valid certificate recorded over all outer rebuild\-and\-puncture rounds\.

###### Algorithm 2\(Iterative Greedy Layered Puncturing Algorithm\)\.

Initialize the live family𝒞←ℬ\\mathcal\{C\}\\leftarrow\\mathcal\{B\}, the fixed weight\-1 contributionq←0q\\leftarrow 0, and the best iterative certificateUpunct←U⁡\(ℬ\)U\_\{\\mathrm\{punct\}\}\\leftarrow U\(\\mathcal\{B\}\)\. For a current residual family𝒞\\mathcal\{C\}, write

nmin,𝒞​\(B\):=\|\{v∈B:d𝒞​\(v\)=w𝒞​\(B\)\}\|n\_\{\\min,\\mathcal\{C\}\}\(B\):=\\bigl\|\\\{v\\in B:d\_\{\\mathcal\{C\}\}\(v\)=w\_\{\\mathcal\{C\}\}\(B\)\\\}\\bigr\|for the number of minimum\-degree vertices in blockBB\.

Repeat the following outer rounds until no block is punctured in a full round\.

1. 1\.Rebuild, preclude weight\-1 blocks, and sharpen the certificate\.Recomputed𝒞​\(⋅\)d\_\{\\mathcal\{C\}\}\(\\cdot\)andw𝒞​\(⋅\)w\_\{\\mathcal\{C\}\}\(\\cdot\), compress incidence twins, and while there is a blockB∈𝒞B\\in\\mathcal\{C\}withw𝒞​\(B\)=1w\_\{\\mathcal\{C\}\}\(B\)=1, choose a degree\-1 root inBB, add one toqq, remove the vertices ofBBfrom all live blocks, delete empty blocks, and rebuild the affected degrees and weights\. After the current weight\-1 wave is exhausted, apply Algorithm[1](https://arxiv.org/html/2609.17951#Thmalgorithm1)to the residual certificate family\. If sharpening deletes vertices, rebuild incidence twins, degrees, and block weights before recording the certificate\. Weight\-1 blocks are not newly created by this vertex\-deletion pass; they are exposed by block punctures and handled at the next rebuild\.
2. 2\.Record the current certificate\.Update Upunct←min⁡\{Upunct,q\+∑B∈𝒞1w𝒞​\(B\)\}\.U\_\{\\mathrm\{punct\}\}\\leftarrow\\min\\left\\\{U\_\{\\mathrm\{punct\}\},\\ q\+\\sum\_\{B\\in\\mathcal\{C\}\}\\frac\{1\}\{w\_\{\\mathcal\{C\}\}\(B\)\}\\right\\\}\.\(44\)If𝒞=∅\\mathcal\{C\}=\\varnothing, stop\.
3. 3\.Process layers from high to low\.Maintain a global vertex\-to\-live\-block index and current block weights for the residual family\. For current weightswwin decreasing order, initialize the active layer ℒw:=\{B∈𝒞:w𝒞​\(B\)=w\}\\mathcal\{L\}\_\{w\}:=\\\{B\\in\\mathcal\{C\}:w\_\{\\mathcal\{C\}\}\(B\)=w\\\}with scoresnmin,𝒞​\(B\)n\_\{\\min,\\mathcal\{C\}\}\(B\)\. Repeatedly choose a blockB∈ℒwB\\in\\mathcal\{L\}\_\{w\}with minimum currentnmin,𝒞​\(B\)n\_\{\\min,\\mathcal\{C\}\}\(B\), breaking ties arbitrarily\. Use the global index to identify every same\- or higher\-weight block whose weight may change after puncturingBB, and compute the exact local certificate change Δ⁡\(B\):=\(q\+∑C∈𝒞1w𝒞​\(C\)\)−\(q\+∑C∈𝒞∖\{B\}1w𝒞∖\{B\}​\(C\)\),\\Delta\(B\):=\\left\(q\+\\sum\_\{C\\in\\mathcal\{C\}\}\\frac\{1\}\{w\_\{\\mathcal\{C\}\}\(C\)\}\\right\)\-\\left\(q\+\\sum\_\{C\\in\\mathcal\{C\}\\setminus\\\{B\\\}\}\\frac\{1\}\{w\_\{\\mathcal\{C\}\\setminus\\\{B\\\}\}\(C\)\}\\right\),\(45\)updating only blocks incident to vertices ofBB\.
4. 4\.Puncture non\-worsening or weight\-1\-enabling blocks\.DeleteBBifΔ⁡\(B\)≥0\\Delta\(B\)\\geq 0, or if deletingBBcreates a new weight\-1 block that will be precluded in the next rebuild\. After a deletion, update the affected vertex degrees, block weights, and active\-layer scores through the global index; if a block’s weight decreases belowww, move it to the corresponding later layer\. At the end of each layer, discard index entries for vertices that cannot affect any future processed layer\.

Output the iterative puncturing boundUpunctU\_\{\\mathrm\{punct\}\}\.

###### Corollary 4\(Validity and termination of the iterative puncturing bound\)\.

The iterative puncturing boundUpunctU\_\{\\mathrm\{punct\}\}returned by Algorithm[2](https://arxiv.org/html/2609.17951#Thmalgorithm2)is a valid upper bound:

α⁡\(ℬ\)≤Upunct\.\\alpha\(\\mathcal\{B\}\)\\leq U\_\{\\mathrm\{punct\}\}\.\(46\)Moreover, the algorithm terminates after finitely many punctures and preclusion steps\.

###### Proof\.

Every certificate recorded by the algorithm has the formq\+U⁡\(𝒞∘\)q\+U\(\\mathcal\{C\}^\{\\circ\}\)after puncturing, repeated incidence\-twin compression, weight\-1 preclusion, and layered superset sharpening on a residual family\. Proposition[2](https://arxiv.org/html/2609.17951#Thmproposition2), together with Theorem[1](https://arxiv.org/html/2609.17951#Thmtheorem1)and Proposition[1](https://arxiv.org/html/2609.17951#Thmproposition1), shows that each such quantity upper\-boundsα⁡\(ℬ\)\\alpha\(\\mathcal\{B\}\)\. The output is the minimum over recorded valid certificates and is therefore valid\. Termination follows because every accepted puncture deletes at least one live block, every weight\-1 preclusion removes at least one nonempty block and its clustered vertices from the residual family, every nontrivial incidence\-twin or superset\-sharpening pass deletes at least one live vertex from the residual certificate family, and the initial incidence family is finite\. ∎

###### Example 3\(Two\-round puncturing cascade\)\.

Let the vertices bex1,x2,x3,x4,y1,y2,y3,y4x\_\{1\},x\_\{2\},x\_\{3\},x\_\{4\},y\_\{1\},y\_\{2\},y\_\{3\},y\_\{4\}, and define

A1\\displaystyle A\_\{1\}=\{x1,x2\},\\displaystyle=\\\{x\_\{1\},x\_\{2\}\\\},A2\\displaystyle A\_\{2\}=\{x3,x4\},\\displaystyle=\\\{x\_\{3\},x\_\{4\}\\\},A3\\displaystyle A\_\{3\}=\{x1,x3\},\\displaystyle=\\\{x\_\{1\},x\_\{3\}\\\},A4\\displaystyle A\_\{4\}=\{x2,x4\},\\displaystyle=\\\{x\_\{2\},x\_\{4\}\\\},L1\\displaystyle L\_\{1\}=\{x1,y1,y2\},\\displaystyle=\\\{x\_\{1\},y\_\{1\},y\_\{2\}\\\},L2\\displaystyle L\_\{2\}=\{x3,y3,y4\},\\displaystyle=\\\{x\_\{3\},y\_\{3\},y\_\{4\}\\\},L3\\displaystyle L\_\{3\}=\{x1,x3,y1,y3\},\\displaystyle=\\\{x\_\{1\},x\_\{3\},y\_\{1\},y\_\{3\}\\\},L4\\displaystyle L\_\{4\}=\{x2,x4,y2,y4\}\.\\displaystyle=\\\{x\_\{2\},x\_\{4\},y\_\{2\},y\_\{4\}\\\}\.The degrees are

d\(x1\)=d\(x3\)=4,d\(x2\)=d\(x4\)=3,d\(yi\)=2\(i=1,…,4\),d\(x\_\{1\}\)=d\(x\_\{3\}\)=4,\\qquad d\(x\_\{2\}\)=d\(x\_\{4\}\)=3,\\qquad d\(y\_\{i\}\)=2\\quad\(i=1,\\dots,4\),so

w\(A3\)=4,w\(A1\)=w\(A2\)=w\(A4\)=3,w\(Li\)=2\(i=1,…,4\),w\(A\_\{3\}\)=4,\\qquad w\(A\_\{1\}\)=w\(A\_\{2\}\)=w\(A\_\{4\}\)=3,\\qquad w\(L\_\{i\}\)=2\\quad\(i=1,\\dots,4\),and the initial closed\-form certificate is

U⁡\(ℬ\)=14\+33\+42=134\.U\(\\mathcal\{B\}\)=\\frac\{1\}\{4\}\+\\frac\{3\}\{3\}\+\\frac\{4\}\{2\}=\\frac\{13\}\{4\}\.
One admissible high\-to\-low puncturing trace first removesA3A\_\{3\}, thenA1A\_\{1\}andA2A\_\{2\}, each of which decreases the current recomputed certificate\. The dynamic increasing\-nminn\_\{\\min\}order is visible along the way:A3A\_\{3\}is the only block in layerw=4w=4; after puncturingA3A\_\{3\}, the layerw=3w=3containsA1,A2,A4A\_\{1\},A\_\{2\},A\_\{4\}with tied or updated minimum\-degree counts, and after one ofA1,A2A\_\{1\},A\_\{2\}is punctured the other becomes the only remaining block in that highest layer\.

The residual family is then

A4,L1,L2,L3,L4,A\_\{4\},\\ L\_\{1\},\\ L\_\{2\},\\ L\_\{3\},\\ L\_\{4\},with current certificate5/25/2\. At this point all live blocks have weight22, but their current minimum\-degree counts are

nmin​\(A4\)=2,nmin​\(L1\)=nmin​\(L2\)=3,nmin​\(L3\)=nmin​\(L4\)=4\.n\_\{\\min\}\(A\_\{4\}\)=2,\\qquad n\_\{\\min\}\(L\_\{1\}\)=n\_\{\\min\}\(L\_\{2\}\)=3,\\qquad n\_\{\\min\}\(L\_\{3\}\)=n\_\{\\min\}\(L\_\{4\}\)=4\.Thus the increasing\-nminn\_\{\\min\}rule selectsA4A\_\{4\}before the largerLL\-blocks\. PuncturingA4A\_\{4\}is a zero\-gain move, but it creates weight\-1 structure in the latentLL\-blocks\. Algorithm[2](https://arxiv.org/html/2609.17951#Thmalgorithm2)handles such newly exposed weight\-1 blocks at the next outer rebuild, so the current layer can still continue its puncturing pass\.

Continuing the same dynamically updated order,L1L\_\{1\}andL2L\_\{2\}are the smallest remaining weight\-2 blocks by currentnminn\_\{\\min\}, so they are punctured before the larger blocksL3,L4L\_\{3\},L\_\{4\}\. This leaves only

L3=\{x1,x3,y1,y3\},L4=\{x2,x4,y2,y4\},L\_\{3\}=\\\{x\_\{1\},x\_\{3\},y\_\{1\},y\_\{3\}\\\},\\qquad L\_\{4\}=\\\{x\_\{2\},x\_\{4\},y\_\{2\},y\_\{4\}\\\},both of residual weight11\. The next rebuild therefore precludesL3L\_\{3\}andL4L\_\{4\}, fixes two canonical units, leaves the residual family empty, and records

Upunct=2\.U\_\{\\mathrm\{punct\}\}=2\.The example isolates why Algorithm[2](https://arxiv.org/html/2609.17951#Thmalgorithm2)is an outer\-iteration procedure rather than a one\-shot deletion rule: some useful punctures do not improve the certificate at the moment they are made, but the dynamic increasing\-nminn\_\{\\min\}order finds small exposure blocks first, these punctures expose the next wave of weight\-1 blocks, and the certificate tightens only after the subsequent rebuild\.

### 4\.3Covering Certificates

The block\-weight bound, its weight\-1 preclusion form, and the puncturing certificate provide instance\-level upper bounds\. They also identify low\-w⁡\(B\)w\(B\)blocks as the most constraining parts of the instance, motivating both the covering certificate below and the greedy clustering schedule in the next section\.

###### Example 4\(A loose weight\-2 block\-weight bound\)\.

Letx1,…,x2​nx\_\{1\},\\dots,x\_\{2n\}be vertices withn≥3n\\geq 3, and define pair blocks

Pt:=\{x2​t−1,x2​t\}\(t=1,…,n\),P\_\{t\}:=\\\{x\_\{2t\-1\},x\_\{2t\}\\\}\\quad\(t=1,\\dots,n\),together with the two parity blocks

O:=\{x1,x3,…,x2​n−1\},E:=\{x2,x4,…,x2​n\}\.O:=\\\{x\_\{1\},x\_\{3\},\\dots,x\_\{2n\-1\}\\\},\\qquad E:=\\\{x\_\{2\},x\_\{4\},\\dots,x\_\{2n\}\\\}\.Then every vertex has degree22, and every block has minimum weightw=2w=2\. Hence Theorem[5](https://arxiv.org/html/2609.17951#Thmtheorem5)gives

α⁡\(ℬ\)≤n\+22\.\\alpha\(\\mathcal\{B\}\)\\leq\\frac\{n\+2\}\{2\}\.However,α⁡\(ℬ\)=2\\alpha\(\\mathcal\{B\}\)=2\. Indeed, one may retain two vertices, for example\{x1,x4\}\\\{x\_\{1\},x\_\{4\}\\\}\. On the other hand, the parity blocks force any feasible set to contain at most one odd\-indexed vertex and at most one even\-indexed vertex\. This family shows that the closed\-form bound can remain loose even when all blocks have uniform weight 2 and no larger “all\-xx” block is present\. Example[5](https://arxiv.org/html/2609.17951#Thmexample5)later traces this same family through puncturing, covering, and greedy clustering\.

Theorem[5](https://arxiv.org/html/2609.17951#Thmtheorem5)provides the foundational ordering principle for the two greedy procedures that follow\. It shows that a block’s contribution toward the maximum strong independent set size is governed primarily by the inverse of its minimum weight, so lower\-weight blocks are the most constraining part of the instance and should be handled first\.

The Greedy Layered Covering Algorithm below and the Greedy Layered Clustering Algorithm in Section 5 are complementary realizations of this same principle: both prioritize increasing block weight, and both refine ties by favoring blocks containing more vertices of that current minimum weight\. The weight\-2 example above then explains why a second, covering\-based viewpoint is useful in addition to the closed\-form charging bound of Theorem[5](https://arxiv.org/html/2609.17951#Thmtheorem5): concentrated overlap can force many nominal low\-weight candidates into a small number of incompatibility blocks\.

###### Algorithm 3\(Greedy Layered Covering Algorithm and iteration\)\.

Initialize a cumulative covered set𝒵0:=∅\\mathcal\{Z\}\_\{0\}:=\\varnothing, a residual block family

ℱ\(0\):=\{B∈ℬ:B≠∅\},\\mathcal\{F\}^\{\(0\)\}:=\\\{B\\in\\mathcal\{B\}:B\\neq\\varnothing\\\},where residual blocks retain their original block indices, and a counterNcov:=0N\_\{\\mathrm\{cov\}\}:=0\. Degrees are recomputed intrinsically on the current residual family:

dt​\(v\):=\|\{B∈ℱ\(t\):v∈B\}\|\.d\_\{t\}\(v\):=\\bigl\|\\\{B\\in\\mathcal\{F\}^\{\(t\)\}:v\\in B\\\}\\bigr\|\.The*Greedy Layered Covering Algorithm*repeatedly performs the following:

1. 1\.Ifℱ\(t\)=∅\\mathcal\{F\}^\{\(t\)\}=\\varnothing, stop and return the selected covering family ℬ⋆:=\{B0⋆,…,BNcov−1⋆\}\\mathcal\{B\}^\{\\star\}:=\\\{B\_\{0\}^\{\\star\},\\dots,B\_\{N\_\{\\mathrm\{cov\}\}\-1\}^\{\\star\}\\\}and the final counterNcov=\|ℬ⋆\|N\_\{\\mathrm\{cov\}\}=\|\\mathcal\{B\}^\{\\star\}\|\.
2. 2\.Compute current block weights wt​\(B\):=minv∈B⁡dt​\(v\),w\_\{t\}\(B\):=\\min\_\{v\\in B\}d\_\{t\}\(v\),the current minimum layer λt:=minB∈ℱ\(t\)⁡wt​\(B\),ℳt:=\{B∈ℱ\(t\):wt​\(B\)=λt\},\\lambda\_\{t\}:=\\min\_\{B\\in\\mathcal\{F\}^\{\(t\)\}\}w\_\{t\}\(B\),\\qquad\\mathcal\{M\}\_\{t\}:=\\\{B\\in\\mathcal\{F\}^\{\(t\)\}:w\_\{t\}\(B\)=\\lambda\_\{t\}\\\},and, for each current degree\-λt\\lambda\_\{t\}vertex, the layer\-local vertex\-to\-block index ℐλt\(v\):=\{i:Bi∈ℳt,v∈Bi,dt\(v\)=λt\},\\mathcal\{I\}\_\{\\lambda\_\{t\}\}\(v\):=\\\{\\,i:\\ B\_\{i\}\\in\\mathcal\{M\}\_\{t\},\\ v\\in B\_\{i\},\\ d\_\{t\}\(v\)=\\lambda\_\{t\}\\,\\\},together with, for eachB∈ℳtB\\in\\mathcal\{M\}\_\{t\}, the number of current minimum\-weight vertices nt​\(B\):=\|\{v∈B:dt​\(v\)=λt\}\|\.n\_\{t\}\(B\):=\\bigl\|\\\{v\\in B:d\_\{t\}\(v\)=\\lambda\_\{t\}\\\}\\bigr\|\.
3. 3\.Select a covering block Bt⋆∈arg⁡maxB∈ℳt​nt​\(B\),B\_\{t\}^\{\\star\}\\in\\arg\\max\_\{B\\in\\mathcal\{M\}\_\{t\}\}n\_\{t\}\(B\),breaking ties arbitrarily\.
4. 4\.Update 𝒵t\+1:=𝒵t∪Bt⋆,Ncov←Ncov\+1,\\mathcal\{Z\}\_\{t\+1\}:=\\mathcal\{Z\}\_\{t\}\\cup B\_\{t\}^\{\\star\},\\qquad N\_\{\\mathrm\{cov\}\}\\leftarrow N\_\{\\mathrm\{cov\}\}\+1,and update the residual family by removing the cumulative covered set from every original block: ℱ\(t\+1\):=\{B∖𝒵t\+1:B∈ℬ,B∖𝒵t\+1≠∅\}\.\\mathcal\{F\}^\{\(t\+1\)\}:=\\\{\\,B\\setminus\\mathcal\{Z\}\_\{t\+1\}:B\\in\\mathcal\{B\},\\ B\\setminus\\mathcal\{Z\}\_\{t\+1\}\\neq\\varnothing\\,\\\}\.\(47\)

The iterated covering version used in the numerical tables setsℬ\(0\):=ℬ\\mathcal\{B\}^\{\(0\)\}:=\\mathcal\{B\}and repeats this covering pass on the current family\. At iterations\+1s\+1, it runs the pass onℬ\(s\)\\mathcal\{B\}^\{\(s\)\}, records the returned family asℬ\(s\+1\)\\mathcal\{B\}^\{\(s\+1\)\}, records

Ncov\(s\+1\):=\|ℬ\(s\+1\)\|,Ucover\(s\+1\):=U⁡\(ℬ\(s\+1\)\),N\_\{\\mathrm\{cov\}\}^\{\(s\+1\)\}:=\|\\mathcal\{B\}^\{\(s\+1\)\}\|,\\qquad U\_\{\\mathrm\{cover\}\}^\{\(s\+1\)\}:=U\(\\mathcal\{B\}^\{\(s\+1\)\}\),and stops whenℬ\(s\+1\)=ℬ\(s\)\\mathcal\{B\}^\{\(s\+1\)\}=\\mathcal\{B\}^\{\(s\)\}\. Thus each reportedUcoverU\_\{\\mathrm\{cover\}\}is the final restricted block\-weight certificate at convergence, while the associated iteration count is the firsts\+1s\+1for which the covering family is unchanged\.

Algorithm[3](https://arxiv.org/html/2609.17951#Thmalgorithm3)deliberately uses the opposite layer priority from Algorithm[2](https://arxiv.org/html/2609.17951#Thmalgorithm2)\. Puncturing starts from the highest residual block weights and, inside a layer, chooses the smallest currentnmin,𝒞​\(B\)n\_\{\\min,\\mathcal\{C\}\}\(B\)because such blocks are the safest candidates to remove without worsening the certificate\. Covering starts from the lowest residual block weight and chooses the largest currentnt​\(B\)n\_\{t\}\(B\)because such blocks cover the most active minimum\-degree vertices in the bottleneck layer\.

###### Theorem 6\(Greedy covering upper bound\)\.

Algorithm[3](https://arxiv.org/html/2609.17951#Thmalgorithm3)returns an upper bound on the maximum feasible retention value:

α⁡\(ℬ\)≤Ncov\.\\alpha\(\\mathcal\{B\}\)\\leq N\_\{\\mathrm\{cov\}\}\.\(48\)

###### Proof\.

Let the algorithm select blocks

B0⋆,B1⋆,…,BNcov−1⋆\.B\_\{0\}^\{\\star\},B\_\{1\}^\{\\star\},\\dots,B\_\{N\_\{\\mathrm\{cov\}\}\-1\}^\{\\star\}\.At termination, the residual family is empty\. Following the residual updates shows that every original blockB∈ℬB\\in\\mathcal\{B\}satisfies

B∖𝒵Ncov=∅,B\\setminus\\mathcal\{Z\}\_\{N\_\{\\mathrm\{cov\}\}\}=\\varnothing,hence

B⊆𝒵Ncov=⋃t=0Ncov−1Bt⋆\.B\\subseteq\\mathcal\{Z\}\_\{N\_\{\\mathrm\{cov\}\}\}=\\bigcup\_\{t=0\}^\{N\_\{\\mathrm\{cov\}\}\-1\}B\_\{t\}^\{\\star\}\.Therefore every retained root belongs to at least one selected covering block\. Assign each retained root to the earliest selected block containing it\. This assignment is injective, because each selected block may contain at most one retained root by feasibility\. Hence the number of retained roots is at most the number of selected covering blocks:

α⁡\(ℬ\)≤Ncov\.\\alpha\(\\mathcal\{B\}\)\\leq N\_\{\\mathrm\{cov\}\}\.∎

The next lemma separates two roles of a restricted block family that preserves the active vertex universe: dropping blocks relaxes feasibility, while under a stronger pairwise\-cover condition the optimum is preserved exactly\. Throughout the lemma, letℬ⋆⊆ℬ\\mathcal\{B\}^\{\\star\}\\subseteq\\mathcal\{B\}satisfy

⋃B∈ℬ⋆B=⋃B∈ℬB\.\\bigcup\_\{B\\in\\mathcal\{B\}^\{\\star\}\}B=\\bigcup\_\{B\\in\\mathcal\{B\}\}B\.
###### Lemma 1\(Subfamily monotonicity and equality under pairwise covering\)\.

Under this shared\-universe assumption:

1. \(i\)One always has α⁡\(ℬ\)≤α⁡\(ℬ⋆\)\.\\alpha\(\\mathcal\{B\}\)\\leq\\alpha\(\\mathcal\{B\}^\{\\star\}\)\.
2. \(ii\)If, in addition, for every omitted blockB∈ℬ∖ℬ⋆B\\in\\mathcal\{B\}\\setminus\\mathcal\{B\}^\{\\star\}and every distinctx,y∈Bx,y\\in B, there existsC∈ℬ⋆C\\in\\mathcal\{B\}^\{\\star\}such that \{x,y\}⊆C,\\\{x,y\\\}\\subseteq C,then α⁡\(ℬ\)=α⁡\(ℬ⋆\)\.\\alpha\(\\mathcal\{B\}\)=\\alpha\(\\mathcal\{B\}^\{\\star\}\)\.

###### Proof\.

For part \(i\), the two families have the same active universe, and everyℬ\\mathcal\{B\}\-feasible set is automaticallyℬ⋆\\mathcal\{B\}^\{\\star\}\-feasible becauseℬ⋆\\mathcal\{B\}^\{\\star\}is a subfamily\. Henceα⁡\(ℬ\)≤α⁡\(ℬ⋆\)\\alpha\(\\mathcal\{B\}\)\\leq\\alpha\(\\mathcal\{B\}^\{\\star\}\)\.

For part \(ii\), letRRbe anyℬ⋆\\mathcal\{B\}^\{\\star\}\-feasible set\. If some omitted blockB∈ℬ∖ℬ⋆B\\in\\mathcal\{B\}\\setminus\\mathcal\{B\}^\{\\star\}contained two retained verticesx,y∈Rx,y\\in R, then by assumption there would existC∈ℬ⋆C\\in\\mathcal\{B\}^\{\\star\}with\{x,y\}⊆C\\\{x,y\\\}\\subseteq C, contradicting feasibility ofRRforℬ⋆\\mathcal\{B\}^\{\\star\}\. Hence everyℬ⋆\\mathcal\{B\}^\{\\star\}\-feasible set is alsoℬ\\mathcal\{B\}\-feasible, soα⁡\(ℬ⋆\)≤α⁡\(ℬ\)\\alpha\(\\mathcal\{B\}^\{\\star\}\)\\leq\\alpha\(\\mathcal\{B\}\)\. Together with part \(i\), this gives equality\. ∎

The restricted covering theorem below uses the monotonicity part of Lemma[1](https://arxiv.org/html/2609.17951#Thmlemma1), together with the fact that a covering family preserves the active vertex universe: once such a familyℬ⋆\\mathcal\{B\}^\{\\star\}has been identified, Theorem[5](https://arxiv.org/html/2609.17951#Thmtheorem5)can be reapplied on that restricted family to obtain a sharper upper bound\. Hereℬ⋆⊆ℬ\\mathcal\{B\}^\{\\star\}\\subseteq\\mathcal\{B\}is a covering subfamily, meaning that every blockB∈ℬB\\in\\mathcal\{B\}satisfies

B⊆⋃C∈ℬ⋆C\.B\\subseteq\\bigcup\_\{C\\in\\mathcal\{B\}^\{\\star\}\}C\.Equivalently, on the active block universe, every vertex that appears in the original block family still appears in the restricted family\.

###### Theorem 7\(Restricted block\-weight refinement over any covering family\)\.

Ifℬ⋆⊆ℬ\\mathcal\{B\}^\{\\star\}\\subseteq\\mathcal\{B\}is a covering subfamily, then

α⁡\(ℬ\)≤U⁡\(ℬ⋆\)≤\|ℬ⋆\|\.\\alpha\(\\mathcal\{B\}\)\\leq U\(\\mathcal\{B\}^\{\\star\}\)\\leq\|\\mathcal\{B\}^\{\\star\}\|\.\(49\)In particular, takingℬ⋆=\{B0⋆,…,BNcov−1⋆\}\\mathcal\{B\}^\{\\star\}=\\\{B\_\{0\}^\{\\star\},\\dots,B\_\{N\_\{\\mathrm\{cov\}\}\-1\}^\{\\star\}\\\}from Theorem[6](https://arxiv.org/html/2609.17951#Thmtheorem6)gives

α⁡\(ℬ\)≤U⁡\(ℬ⋆\)≤Ncov\.\\alpha\(\\mathcal\{B\}\)\\leq U\(\\mathcal\{B\}^\{\\star\}\)\\leq N\_\{\\mathrm\{cov\}\}\.

###### Proof\.

By part \(i\) of Lemma[1](https://arxiv.org/html/2609.17951#Thmlemma1),

α⁡\(ℬ\)≤α⁡\(ℬ⋆\)\.\\alpha\(\\mathcal\{B\}\)\\leq\\alpha\(\\mathcal\{B\}^\{\\star\}\)\.Applying Theorem[5](https://arxiv.org/html/2609.17951#Thmtheorem5)to the restricted familyℬ⋆\\mathcal\{B\}^\{\\star\}gives

α⁡\(ℬ⋆\)≤U⁡\(ℬ⋆\)\.\\alpha\(\\mathcal\{B\}^\{\\star\}\)\\leq U\(\\mathcal\{B\}^\{\\star\}\)\.Here the covering condition is what makes the restricted\-family certificate legitimate for the same active vertex universe: no originally active vertex has disappeared from all retained blocks\. Combining the two inequalities yields

α⁡\(ℬ\)≤U⁡\(ℬ⋆\)\.\\alpha\(\\mathcal\{B\}\)\\leq U\(\\mathcal\{B\}^\{\\star\}\)\.Finally, every block weight contributing toU⁡\(ℬ⋆\)U\(\\mathcal\{B\}^\{\\star\}\)is at least11,

U⁡\(ℬ⋆\)≤\|ℬ⋆\|\.U\(\\mathcal\{B\}^\{\\star\}\)\\leq\|\\mathcal\{B\}^\{\\star\}\|\.∎

The outer iteration in Algorithm[3](https://arxiv.org/html/2609.17951#Thmalgorithm3)is justified by the same covering\-and\-reweighting principle: once one covering family has been extracted, the pass may be applied again to that restricted family, yielding a nested sequence of valid upper bounds whose limit family has a simple fixed\-point structure\. Initialize

ℬ\(0\):=ℬ,\\mathcal\{B\}^\{\(0\)\}:=\\mathcal\{B\},and for eacht≥0t\\geq 0, letℬ\(t\+1\)⊆ℬ\(t\)\\mathcal\{B\}^\{\(t\+1\)\}\\subseteq\\mathcal\{B\}^\{\(t\)\}be the covering family produced by running the Greedy Layered Covering Algorithm onℬ\(t\)\\mathcal\{B\}^\{\(t\)\}\. Ifℬ\(t\+1\)=ℬ\(t\)\\mathcal\{B\}^\{\(t\+1\)\}=\\mathcal\{B\}^\{\(t\)\}, the iteration has converged and stops; otherwiseℬ\(t\+1\)⊂ℬ\(t\)\\mathcal\{B\}^\{\(t\+1\)\}\\subset\\mathcal\{B\}^\{\(t\)\}\. Letwt⋆​\(B\)w\_\{t\}^\{\\star\}\(B\)denote the restricted block weight computed insideℬ\(t\)\\mathcal\{B\}^\{\(t\)\}\.

###### Theorem 8\(Iterated covering refinement and fixed\-point structure\)\.

For the covering sequence above, every constructedt≥1t\\geq 1satisfies

α⁡\(ℬ\)≤U⁡\(ℬ\(t\)\)≤\|ℬ\(t\)\|,\\alpha\(\\mathcal\{B\}\)\\leq U\(\\mathcal\{B\}^\{\(t\)\}\)\\leq\|\\mathcal\{B\}^\{\(t\)\}\|,\(50\)and the sequence\|ℬ\(t\)\|\|\\mathcal\{B\}^\{\(t\)\}\|is nonincreasing and stabilizes after finitely many steps\. Therefore there exists sometcov≥0t\_\{\\mathrm\{cov\}\}\\geq 0such that

ℬ\(tcov\+1\)=ℬ\(tcov\),\\mathcal\{B\}^\{\(t\_\{\\mathrm\{cov\}\}\+1\)\}=\\mathcal\{B\}^\{\(t\_\{\\mathrm\{cov\}\}\)\},and every block in the converged family has restricted weight11:

wtcov⋆​\(B\)=1∀B∈ℬ\(tcov\),w\_\{t\_\{\\mathrm\{cov\}\}\}^\{\\star\}\(B\)=1\\qquad\\forall B\\in\\mathcal\{B\}^\{\(t\_\{\\mathrm\{cov\}\}\)\},and consequently

U⁡\(ℬ\(tcov\)\)=\|ℬ\(tcov\)\|\.U\(\\mathcal\{B\}^\{\(t\_\{\\mathrm\{cov\}\}\)\}\)=\|\\mathcal\{B\}^\{\(t\_\{\\mathrm\{cov\}\}\)\}\|\.

###### Proof\.

We first prove the validity and termination claims\. By construction, eachℬ\(t\+1\)\\mathcal\{B\}^\{\(t\+1\)\}is a covering subfamily ofℬ\(t\)\\mathcal\{B\}^\{\(t\)\}\. Applying Theorem[7](https://arxiv.org/html/2609.17951#Thmtheorem7)withℬ=ℬ\(t−1\)\\mathcal\{B\}=\\mathcal\{B\}^\{\(t\-1\)\}andℬ⋆=ℬ\(t\)\\mathcal\{B\}^\{\\star\}=\\mathcal\{B\}^\{\(t\)\}yields

α⁡\(ℬ\(t−1\)\)≤U⁡\(ℬ\(t\)\)≤\|ℬ\(t\)\|\.\\alpha\(\\mathcal\{B\}^\{\(t\-1\)\}\)\\leq U\(\\mathcal\{B\}^\{\(t\)\}\)\\leq\|\\mathcal\{B\}^\{\(t\)\}\|\.Sinceℬ\(t\)⊆ℬ\(t−1\)\\mathcal\{B\}^\{\(t\)\}\\subseteq\\mathcal\{B\}^\{\(t\-1\)\}for everytt, Lemma[1](https://arxiv.org/html/2609.17951#Thmlemma1)\(i\) gives

α⁡\(ℬ\)=α⁡\(ℬ\(0\)\)≤α⁡\(ℬ\(t−1\)\),\\alpha\(\\mathcal\{B\}\)=\\alpha\(\\mathcal\{B\}^\{\(0\)\}\)\\leq\\alpha\(\\mathcal\{B\}^\{\(t\-1\)\}\),and therefore

α⁡\(ℬ\)≤U⁡\(ℬ\(t\)\)≤\|ℬ\(t\)\|\.\\alpha\(\\mathcal\{B\}\)\\leq U\(\\mathcal\{B\}^\{\(t\)\}\)\\leq\|\\mathcal\{B\}^\{\(t\)\}\|\.Finally, becauseℬ\(t\+1\)⊆ℬ\(t\)\\mathcal\{B\}^\{\(t\+1\)\}\\subseteq\\mathcal\{B\}^\{\(t\)\}and the family sizes are nonnegative integers, the sequence\|ℬ\(t\)\|\|\\mathcal\{B\}^\{\(t\)\}\|is nonincreasing and must stabilize after finitely many iterations\.

It remains to identify the structure of a converged family\. Now lettcovt\_\{\\mathrm\{cov\}\}be a converged index\. Run the Greedy Layered Covering Algorithm on the fixed familyℬ\(tcov\)\\mathcal\{B\}^\{\(t\_\{\\mathrm\{cov\}\}\)\}\. Since the covering family returned by that run is againℬ\(tcov\)\\mathcal\{B\}^\{\(t\_\{\\mathrm\{cov\}\}\)\}, every block ofℬ\(tcov\)\\mathcal\{B\}^\{\(t\_\{\\mathrm\{cov\}\}\)\}is eventually selected during the run\.

Assume for contradiction that some block ofℬ\(tcov\)\\mathcal\{B\}^\{\(t\_\{\\mathrm\{cov\}\}\)\}has restricted weight greater than11, and let

ℬ^\>1:=\{B∈ℬ\(tcov\):wtcov⋆​\(B\)\>1\}\.\\widehat\{\\mathcal\{B\}\}\_\{\>1\}:=\\\{\\,B\\in\\mathcal\{B\}^\{\(t\_\{\\mathrm\{cov\}\}\)\}:w\_\{t\_\{\\mathrm\{cov\}\}\}^\{\\star\}\(B\)\>1\\,\\\}\.ChooseBi∈ℬ^\>1B\_\{i\}\\in\\widehat\{\\mathcal\{B\}\}\_\{\>1\}to be the*last block actually selected*among all blocks ofℬ^\>1\\widehat\{\\mathcal\{B\}\}\_\{\>1\}during this fixed\-point rerun\.

Take any vertexv∈Biv\\in B\_\{i\}\. Sincewtcov⋆​\(Bi\)\>1w\_\{t\_\{\\mathrm\{cov\}\}\}^\{\\star\}\(B\_\{i\}\)\>1, every vertex ofBiB\_\{i\}has restricted degree at least22insideℬ\(tcov\)\\mathcal\{B\}^\{\(t\_\{\\mathrm\{cov\}\}\)\}, so there exists another blockCv≠BiC\_\{v\}\\neq B\_\{i\}inℬ\(tcov\)\\mathcal\{B\}^\{\(t\_\{\\mathrm\{cov\}\}\)\}containingvv\.

Ifwtcov⋆​\(Cv\)=1w\_\{t\_\{\\mathrm\{cov\}\}\}^\{\\star\}\(C\_\{v\}\)=1, thenCvC\_\{v\}is selected earlier thanBiB\_\{i\}because all weight\-11blocks are processed before any block of intrinsic weight greater than11\. Ifwtcov⋆​\(Cv\)\>1w\_\{t\_\{\\mathrm\{cov\}\}\}^\{\\star\}\(C\_\{v\}\)\>1, thenCv∈ℬ^\>1C\_\{v\}\\in\\widehat\{\\mathcal\{B\}\}\_\{\>1\}, and by the choice ofBiB\_\{i\}as the last selected block inℬ^\>1\\widehat\{\\mathcal\{B\}\}\_\{\>1\}, the blockCvC\_\{v\}is again selected earlier thanBiB\_\{i\}\.

In either case, the earlier selection ofCvC\_\{v\}covers the vertexvvbeforeBiB\_\{i\}would be selected\. Since this argument applies to every vertexv∈Biv\\in B\_\{i\}, all elements ofBiB\_\{i\}are already covered before its supposed selection time\. Therefore the residual version ofBiB\_\{i\}is empty at that moment, soBiB\_\{i\}must be discarded rather than selected\. This contradicts the fact that every block of the fixed\-point familyℬ\(tcov\)\\mathcal\{B\}^\{\(t\_\{\\mathrm\{cov\}\}\)\}is selected again in the rerun\.

Therefore no converged block can have restricted weight greater than11, proving thatwtcov⋆​\(B\)=1w\_\{t\_\{\\mathrm\{cov\}\}\}^\{\\star\}\(B\)=1for everyB∈ℬ\(tcov\)B\\in\\mathcal\{B\}^\{\(t\_\{\\mathrm\{cov\}\}\)\}\. The displayed identity follows immediately\. ∎

Apply the iterated covering procedure until convergence, and denote its terminal covering family by

ℬ^:=ℬ\(tcov\)\.\\widehat\{\\mathcal\{B\}\}:=\\mathcal\{B\}^\{\(t\_\{\\mathrm\{cov\}\}\)\}\.Since Theorem[8](https://arxiv.org/html/2609.17951#Thmtheorem8)gives unit block weight inℬ^\\widehat\{\\mathcal\{B\}\}, choose for each terminal blockB∈ℬ^B\\in\\widehat\{\\mathcal\{B\}\}one vertexzB∈Bz\_\{B\}\\in Bwith

dℬ^​\(zB\)=1\.d\_\{\\widehat\{\\mathcal\{B\}\}\}\(z\_\{B\}\)=1\.Set

Z:=\{zB:B∈ℬ^\}\.Z:=\\\{z\_\{B\}:B\\in\\widehat\{\\mathcal\{B\}\}\\\}\.The next corollary records the canonical structure of this terminal restricted family\.

###### Corollary 5\(Unit\-weight covering family and canonical optimum\)\.

For every finite block familyℬ\\mathcal\{B\}, the terminal familyℬ^\\widehat\{\\mathcal\{B\}\}is a covering subfamily ofℬ\\mathcal\{B\}satisfying

wℬ^​\(B\)=1∀B∈ℬ^\.w\_\{\\widehat\{\\mathcal\{B\}\}\}\(B\)=1\\qquad\\forall B\\in\\widehat\{\\mathcal\{B\}\}\.Moreover,ZZis an optimal retained set forℬ^\\widehat\{\\mathcal\{B\}\}satisfying

\|Z\|=\|ℬ^\|=α⁡\(ℬ^\)=U⁡\(ℬ^\)\.\|Z\|=\|\\widehat\{\\mathcal\{B\}\}\|=\\alpha\(\\widehat\{\\mathcal\{B\}\}\)=U\(\\widehat\{\\mathcal\{B\}\}\)\.

###### Proof\.

Theorem[8](https://arxiv.org/html/2609.17951#Thmtheorem8)shows thatℬ^\\widehat\{\\mathcal\{B\}\}is a covering subfamily ofℬ\\mathcal\{B\}and that every block inℬ^\\widehat\{\\mathcal\{B\}\}has intrinsic weight11\. Therefore Theorem[2](https://arxiv.org/html/2609.17951#Thmtheorem2), applied to the restricted familyℬ^\\widehat\{\\mathcal\{B\}\}, gives an optimal feasible set containing one restricted\-degree\-11vertexzBz\_\{B\}from every blockB∈ℬ^B\\in\\widehat\{\\mathcal\{B\}\}\. Since each such vertex belongs to exactly one block ofℬ^\\widehat\{\\mathcal\{B\}\}, the selected setZZis feasible and satisfies\|Z\|=\|ℬ^\|\|Z\|=\|\\widehat\{\\mathcal\{B\}\}\|\. The same fixed\-point theorem also givesU⁡\(ℬ^\)=\|ℬ^\|U\(\\widehat\{\\mathcal\{B\}\}\)=\|\\widehat\{\\mathcal\{B\}\}\|, and Theorem[5](https://arxiv.org/html/2609.17951#Thmtheorem5)applied toℬ^\\widehat\{\\mathcal\{B\}\}yieldsα⁡\(ℬ^\)≤U⁡\(ℬ^\)\\alpha\(\\widehat\{\\mathcal\{B\}\}\)\\leq U\(\\widehat\{\\mathcal\{B\}\}\)\. Hence

\|Z\|=\|ℬ^\|=U⁡\(ℬ^\)≥α⁡\(ℬ^\)\.\|Z\|=\|\\widehat\{\\mathcal\{B\}\}\|=U\(\\widehat\{\\mathcal\{B\}\}\)\\geq\\alpha\(\\widehat\{\\mathcal\{B\}\}\)\.SinceZZis itself feasible forℬ^\\widehat\{\\mathcal\{B\}\}, one also has\|Z\|≤α⁡\(ℬ^\)\|Z\|\\leq\\alpha\(\\widehat\{\\mathcal\{B\}\}\), proving the claimed equalities\. ∎

For later comparison, it is convenient to name the main structural bounds introduced in this section:

Ucf:=U⁡\(ℬ\),Uw1:=\|ℬ1\|\+U⁡\(ℬ∘\),Upunct:=Punct⁡\(ℬ\),U\_\{\\mathrm\{cf\}\}:=U\(\\mathcal\{B\}\),\\qquad U\_\{\\mathrm\{w1\}\}:=\|\\mathcal\{B\}\_\{1\}\|\+U\(\\mathcal\{B\}^\{\\circ\}\),\\qquad U\_\{\\mathrm\{punct\}\}:=\\operatorname\{Punct\}\(\\mathcal\{B\}\),\(51\)for the closed\-form, weight\-1 preclusion, and iterative puncturing bounds, respectively, wherePunct⁡\(ℬ\)\\operatorname\{Punct\}\(\\mathcal\{B\}\)denotes the certificate returned by Algorithm[2](https://arxiv.org/html/2609.17951#Thmalgorithm2)\. For an iterated covering sequenceℬ\(t\)\\mathcal\{B\}^\{\(t\)\}, we also write

Ncov\(t\):=\|ℬ\(t\)\|,Ucover\(t\):=U⁡\(ℬ\(t\)\)\.N\_\{\\mathrm\{cov\}\}^\{\(t\)\}:=\|\\mathcal\{B\}^\{\(t\)\}\|,\\qquad U\_\{\\mathrm\{cover\}\}^\{\(t\)\}:=U\(\\mathcal\{B\}^\{\(t\)\}\)\.\(52\)In particular, the first covering round satisfiesNcov\(1\)=\|ℬ⋆\|N\_\{\\mathrm\{cov\}\}^\{\(1\)\}=\|\\mathcal\{B\}^\{\\star\}\|andUcover\(1\)=U⁡\(ℬ⋆\)U\_\{\\mathrm\{cover\}\}^\{\(1\)\}=U\(\\mathcal\{B\}^\{\\star\}\)\. When the iterated sequence is run to convergence in the empirical tables,UcoverU\_\{\\mathrm\{cover\}\}denotes the final value ofUcover\(t\)U\_\{\\mathrm\{cover\}\}^\{\(t\)\}\.

The puncturing and iterated\-covering refinements are complementary rather than inclusive\. The iterative puncturing boundUpunctU\_\{\\mathrm\{punct\}\}is obtained by searching over residual block subfamilies across outer rounds, recomputing intrinsic weights after punctures, and repeatedly precluding newly exposed weight\-1 blocks; the iterated covering boundsUcover\(t\)U\_\{\\mathrm\{cover\}\}^\{\(t\)\}instead come from repeatedly selecting covering families and recomputing intrinsic weights on those restricted families\. Because these mechanisms are different, neither quantity dominates the other in general\. In practice, one should therefore compute both and use

min⁡\{Upunct,Ucover\(1\),Ucover\(2\),…\}\\min\\bigl\\\{U\_\{\\mathrm\{punct\}\},\\,U\_\{\\mathrm\{cover\}\}^\{\(1\)\},\\,U\_\{\\mathrm\{cover\}\}^\{\(2\)\},\\,\\dots\\bigr\\\}as the strongest available structural comparison target\.

Example 1\(e\) \(Running example under the Greedy Layered Covering Algorithm\)\.The running example from Examples[2](https://arxiv.org/html/2609.17951#S2)–[4\.1](https://arxiv.org/html/2609.17951#S4.SS1)also behaves cleanly under the Greedy Layered Covering Algorithm\. One valid covering run selects

ℬ⋆=\{B1,B2,B4,B8,B11\},\\mathcal\{B\}^\{\\star\}=\\\{B\_\{1\},B\_\{2\},B\_\{4\},B\_\{8\},B\_\{11\}\\\},so Theorem[6](https://arxiv.org/html/2609.17951#Thmtheorem6)gives

α⁡\(ℬ\)≤Ncov=5\.\\alpha\(\\mathcal\{B\}\)\\leq N\_\{\\mathrm\{cov\}\}=5\.Moreover, in the restricted familyℬ⋆\\mathcal\{B\}^\{\\star\}, each selected block has restricted weight11: for example,B1B\_\{1\}contains the restricted\-degree\-1 vertexaa,B2B\_\{2\}containsbb, andB4,B8,B11B\_\{4\},B\_\{8\},B\_\{11\}containe,c,re,c,r, respectively\. Hence

U⁡\(ℬ⋆\)=1\+1\+1\+1\+1=5,U\(\\mathcal\{B\}^\{\\star\}\)=1\+1\+1\+1\+1=5,so Theorem[7](https://arxiv.org/html/2609.17951#Thmtheorem7)reaches the same exact value\. In this instance the dominance\-reduced closed\-form bound, the covering\-family restricted bound, and the closed\-form bound for the selected covering set all coincide with the true optimum\.

This algorithm is complementary to Theorem[5](https://arxiv.org/html/2609.17951#Thmtheorem5): Theorem[5](https://arxiv.org/html/2609.17951#Thmtheorem5)gives a closed\-form charging bound, while the Greedy Layered Covering Algorithm searches directly for a small covering family of incompatibility blocks in the active minimum\-weight layer\. Theorem[7](https://arxiv.org/html/2609.17951#Thmtheorem7)then shows that any such covering family, regardless of how it is obtained, yields a restricted block\-weight upper bound\.

The practical purpose of the greedy construction is to capture concentration effects like the weight\-2 example above, where many nominal low\-weight candidates collapse into a single forced block\. The secondary keynt​\(B\)n\_\{t\}\(B\)is not needed for validity, but it is the natural greedy choice because it attempts to cover as many current degree\-λt\\lambda\_\{t\}candidates as possible per unit increase of the bound\. The tradeoff is that, unlike Theorem[5](https://arxiv.org/html/2609.17951#Thmtheorem5), this procedure has no closed form and requires repeated residual updates, so its direct computation is typically quadratic\-scale in the residual incidences\.

## 5Greedy Layered block\-Weight Clustering

The previous section develops structural bounds for the maximum strong independent set objective on a hyperedge family\. We now turn those bounds into an explicit block\-native solver\. In particular, Theorems[5](https://arxiv.org/html/2609.17951#Thmtheorem5)and[6](https://arxiv.org/html/2609.17951#Thmtheorem6)provide the first\-order and second\-order scheduling principles that drive the block\-weight\-layered greedy clustering routine below\.

Generic bounded\-degree hypergraph algorithms typically treat a hypergraph as a graph\-style combinatorial object in a more general setting\[[10](https://arxiv.org/html/2609.17951#bib.bib10)\]\. In contrast, the approach here is explicitly incidence\-native: it assumes the block family itself is materialized and uses block weights, minimum\-degree witnesses, and block\-side residual updates as the primary state\.

Theorem[5](https://arxiv.org/html/2609.17951#Thmtheorem5)provides the first\-order principle: blocks of smaller minimum weight are more constraining and therefore should be processed first\. Theorem[6](https://arxiv.org/html/2609.17951#Thmtheorem6)provides a second\-order principle: within a fixed block\-weight layer, blocks containing more minimum\-weight vertices exert stronger covering pressure and should be prioritized next\. This suggests a block\-native greedy algorithm organized by block\-weight layers with a lexicographic within\-layer priority, rather than by an auxiliary hypergraph optimization routine\.

Letℬ=\{B1,…,BM\}\\mathcal\{B\}=\\\{B\_\{1\},\\dots,B\_\{M\}\\\}denote the incidence\-twin\-compressed block family\. The algorithm below is stated on an abstract indexed family, but its operations are deliberately block\-local: residual deletion and layer updates are expressed as scans of block records and vertex\-to\-block incidence lists\.

Incidence\-twin compression quotients vertices with identical block\-index support and stores their original vertex lists for final materialization if needed\. All initial degrees, block weights, andnminn\_\{\\min\}values are computed on this quotient family; this avoids treating mutually exclusive identical\-support vertices as separate minimum\-weight candidates\.

Following Corollary[2](https://arxiv.org/html/2609.17951#Thmcorollary2), the clustering routine first performs a weight\-1 preclusion pass\. For eachB∈ℬ1:=\{B∈ℬ:w⁡\(B\)=1\}B\\in\\mathcal\{B\}\_\{1\}:=\\\{B\\in\\mathcal\{B\}:w\(B\)=1\\\}, it selects a degree\-1 vertex classzBz\_\{B\}as canonical root, attaches currently unassigned members ofBBto that root, and marks attached classes as removed from subsequent processing\. It then removes attached classes from all remaining blocks and keeps the resulting nonempty residual familyℬres\\mathcal\{B\}^\{\\mathrm\{res\}\}\. Degrees are recomputed onℬres\\mathcal\{B\}^\{\\mathrm\{res\}\}and kept fixed during the later layered pass; once a class is attached, it is removed from subsequent layer processing rather than assigned a new residual degree\.

In implementation, we materializeℬres\\mathcal\{B\}^\{\\mathrm\{res\}\}as a mutable list\-of\-lists representation

𝐁=\[B1,…,BMres\],\\mathbf\{B\}=\[B\_\{1\},\\dots,B\_\{M\_\{\\mathrm\{res\}\}\}\],where eachBiB\_\{i\}is updated in place during processing\. Layer priorities use

w^​\(B\):=minv∈B⁡d⁡\(v\),nmin​\(B\):=\|\{v∈B:d⁡\(v\)=w^​\(B\)\}\|,\\widehat\{w\}\(B\):=\\min\_\{v\\in B\}d\(v\),\\qquad n\_\{\\min\}\(B\):=\\bigl\|\\\{v\\in B:d\(v\)=\\widehat\{w\}\(B\)\\\}\\bigr\|,and for each integer weightwwwe maintain a block\-index set

𝒮w:=\{i:w^​\(Bi\)=w\}\.\\mathcal\{S\}\_\{w\}:=\\\{i:\\widehat\{w\}\(B\_\{i\}\)=w\\\}\.Within a fixed block\-weight layerw^​\(B\)=w\\widehat\{w\}\(B\)=w, Theorem[6](https://arxiv.org/html/2609.17951#Thmtheorem6)suggests prioritizing largernmin​\(B\)n\_\{\\min\}\(B\): such blocks cover more current degree\-wwcandidates and therefore exert stronger covering pressure\. Representative state is maintained by a root setRRand a vertex\-to\-root mapϕ:V→V\\phi:V\\to V\(vertex↦\\mapstocurrent root\), initialized from the weight\-1 preclusion pass and then updated by the layered greedy stage\. The blocks are released progressively \(Bi←∅B\_\{i\}\\leftarrow\\varnothing\) until all residual blocks are consumed\.

###### Definition 6\(Active root\)\.

A vertexuuis an active root if it is currently chosen as the representative of its cluster\.

###### Definition 7\(vertex\-to\-root map\)\.

A vertex\-to\-root map is a functionϕ:V→V\\phi:V\\to Vsuch thatϕ⁡\(v\)\\phi\(v\)is the current representative of the cluster containingvv, andϕ⁡\(v\)=v\\phi\(v\)=viffvvis a root\.

###### Definition 8\(Cluster\)\.

For a rootuu, define

𝒞u:=\{v∈V:ϕ⁡\(v\)=u\}\.\\mathcal\{C\}\_\{u\}:=\\\{v\\in V:\\phi\(v\)=u\\\}\.\(53\)

###### Definition 9\(Root selection key\)\.

After a blockBBhas been chosen by the block\-level priority, let

w⁡\(B\):=minv∈B⁡d⁡\(v\),M⁡\(B\):=\{v∈B:d⁡\(v\)=w⁡\(B\)\}\.w\(B\):=\\min\_\{v\\in B\}d\(v\),\\qquad M\(B\):=\\\{v\\in B:d\(v\)=w\(B\)\\\}\.\(54\)Thus

nmin​\(B\)=\|M⁡\(B\)\|\.n\_\{\\min\}\(B\)=\|M\(B\)\|\.For a candidatev∈M⁡\(B\)v\\in M\(B\), define its equal\-weight collision neighborhood

𝒩w⁡\(B\)​\(v\):=\{u∈⋃B′∋vB′:d⁡\(u\)=w⁡\(B\)\},\\mathcal\{N\}\_\{w\(B\)\}\(v\):=\\left\\\{u\\in\\bigcup\_\{B^\{\\prime\}\\ni v\}B^\{\\prime\}:d\(u\)=w\(B\)\\right\\\},\(55\)and its equal\-weight collision score

cw⁡\(B\)​\(v\):=\|𝒩w⁡\(B\)​\(v\)\|\.c\_\{w\(B\)\}\(v\):=\\left\|\\mathcal\{N\}\_\{w\(B\)\}\(v\)\\right\|\.\(56\)Since eachv∈M⁡\(B\)v\\in M\(B\)lies in exactlyw⁡\(B\)w\(B\)blocks,cw⁡\(B\)​\(v\)c\_\{w\(B\)\}\(v\)counts the number of distinct degree\-w⁡\(B\)w\(B\)vertices coupled tovvthrough those blocks\. Thus, after the blockBBhas been selected, the root is chosen fromM⁡\(B\)M\(B\)by

v⋆=arg⁡minv∈M⁡\(B\)⁡\(cw⁡\(B\)​\(v\),id⁡\(v\)\)\.v^\{\\star\}=\\arg\\min\_\{v\\in M\(B\)\}\\bigl\(c\_\{w\(B\)\}\(v\),\\mathrm\{id\}\(v\)\\bigr\)\.\(57\)This can also be extended to include source\-priority terms without changing feasibility\.

Fix a blockBBand two candidate rootsu,v∈M⁡\(B\)u,v\\in M\(B\), so that

d⁡\(u\)=d⁡\(v\)=w⁡\(B\)\.d\(u\)=d\(v\)=w\(B\)\.
###### Proposition 3\(Equal\-weight collision minimization\)\.

The number of current degree\-w⁡\(B\)w\(B\)candidates consumed immediately by the root choice is monotone in the collision score:

cw⁡\(B\)​\(u\)≤cw⁡\(B\)​\(v\)⟹\|𝒩w⁡\(B\)​\(u\)\|≤\|𝒩w⁡\(B\)​\(v\)\|\.c\_\{w\(B\)\}\(u\)\\leq c\_\{w\(B\)\}\(v\)\\quad\\Longrightarrow\\quad\|\\mathcal\{N\}\_\{w\(B\)\}\(u\)\|\\leq\|\\mathcal\{N\}\_\{w\(B\)\}\(v\)\|\.Consequently, after a block has been selected, choosing fromM⁡\(B\)M\(B\)the candidate with the smallestcw⁡\(B\)​\(⋅\)c\_\{w\(B\)\}\(\\cdot\)minimizes the number of degree\-w⁡\(B\)w\(B\)candidates clustered away at that step, and therefore preserves the largest remaining pool of degree\-w⁡\(B\)w\(B\)candidates for future roots in the same layer\.

###### Proof\.

By definition,𝒩w⁡\(B\)​\(v\)\\mathcal\{N\}\_\{w\(B\)\}\(v\)is exactly the set of current degree\-w⁡\(B\)w\(B\)vertices coupled tovvthrough the blocks incident tovv\. Oncevvis chosen as root, these coupled degree\-w⁡\(B\)w\(B\)vertices are clustered away from future root consideration in the current layer\. Hence the number of degree\-w⁡\(B\)w\(B\)candidates consumed immediately by choosingvvis exactly

cw⁡\(B\)​\(v\)=\|𝒩w⁡\(B\)​\(v\)\|\.c\_\{w\(B\)\}\(v\)=\|\\mathcal\{N\}\_\{w\(B\)\}\(v\)\|\.Therefore minimizing the collision score minimizes the number of current degree\-w⁡\(B\)w\(B\)candidates removed at that step, leaving the largest remaining pool available for subsequent root creation in the same layer\. ∎

Note thatcw⁡\(B\)​\(v\)c\_\{w\(B\)\}\(v\)counts distinct degree\-w⁡\(B\)w\(B\)competitors, so in general

cw⁡\(B\)​\(v\)≤∑B′∋vnmin​\(B′\),c\_\{w\(B\)\}\(v\)\\leq\\sum\_\{B^\{\\prime\}\\ni v\}n\_\{\\min\}\(B^\{\\prime\}\),with equality only when those minimum\-weight candidate sets are disjoint outside ofvvitself\.

###### Algorithm 4\(Greedy Layered Clustering Algorithm\)\.

The clustering stage proceeds as follows\.

1. 1\.Load the indexed blocks, compress incidence\-twin vertex classes, and denote the resulting quotient family byℬ=\{B1,…,BM\}\\mathcal\{B\}=\\\{B\_\{1\},\\dots,B\_\{M\}\\\}\. Count quotient\-vertex frequenciesd⁡\(v\)d\(v\)\.
2. 2\.Weight\-1 preclusion: identifyℬ1:=\{B∈ℬ:w⁡\(B\)=1\}\\mathcal\{B\}\_\{1\}:=\\\{B\\in\\mathcal\{B\}:w\(B\)=1\\\}\. For eachB∈ℬ1B\\in\\mathcal\{B\}\_\{1\}, pick a degree\-1 rootzBz\_\{B\}, attach currently unassigned members ofBBtozBz\_\{B\}, and updateR,ϕR,\\phi\.
3. 3\.Remove already clustered vertices from remaining blocks, setℬres\\mathcal\{B\}^\{\\mathrm\{res\}\}to the resulting nonempty residual block family, materialize it as𝐁=\[B1,…,BMres\]\\mathbf\{B\}=\[B\_\{1\},\\dots,B\_\{M\_\{\\mathrm\{res\}\}\}\], recompute residual frequenciesd⁡\(v\)d\(v\)onℬres\\mathcal\{B\}^\{\\mathrm\{res\}\}, and for each residual block indexiicomputew^​\(Bi\)=minv∈Bi⁡d⁡\(v\)\\widehat\{w\}\(B\_\{i\}\)=\\min\_\{v\\in B\_\{i\}\}d\(v\)and insertiiinto the corresponding block\-index set𝒮w^​\(Bi\)\\mathcal\{S\}\_\{\\widehat\{w\}\(B\_\{i\}\)\}\.
4. 4\.For each block\-weight layerwwfrom the current minimum upward: 1. \(a\)First pass over𝒮w\\mathcal\{S\}\_\{w\}: for eachi∈𝒮wi\\in\\mathcal\{S\}\_\{w\}, remove already clustered vertices fromBiB\_\{i\}\. IfBi=∅B\_\{i\}=\\varnothing, discard it\. IfBiB\_\{i\}contains no degree\-wwvertex, recomputew^​\(Bi\)\>w\\widehat\{w\}\(B\_\{i\}\)\>wand moveiito the corresponding larger\-weight set𝒮w^​\(Bi\)\\mathcal\{S\}\_\{\\widehat\{w\}\(B\_\{i\}\)\}\. Otherwise computenmin​\(Bi\)=\|\{v∈Bi:d⁡\(v\)=w\}\|n\_\{\\min\}\(B\_\{i\}\)=\|\\\{v\\in B\_\{i\}:d\(v\)=w\\\}\|and keepiiin the active layer\. 2. \(b\)From the surviving current\-layer blocks, build the degree\-wwvertex\-to\-block index ℐw\(v\):=\{i∈𝒮w:v∈Bi,d\(v\)=w\},\\mathcal\{I\}\_\{w\}\(v\):=\\\{i\\in\\mathcal\{S\}\_\{w\}:v\\in B\_\{i\},\\ d\(v\)=w\\\},for each active degree\-wwvertex\. 3. \(c\)While active blocks remain in the current layer and the indexℐw​\(⋅\)\\mathcal\{I\}\_\{w\}\(\\cdot\)is nonempty, choose an active blockBiB\_\{i\}with maximum currentnmin​\(Bi\)n\_\{\\min\}\(B\_\{i\}\), breaking ties arbitrarily\. 4. \(d\)For the chosen block, defineM⁡\(Bi\):=\{v∈Bi:d⁡\(v\)=w\}M\(B\_\{i\}\):=\\\{v\\in B\_\{i\}:d\(v\)=w\\\}\. IfM⁡\(Bi\)=∅M\(B\_\{i\}\)=\\varnothing, recomputew^​\(Bi\)\>w\\widehat\{w\}\(B\_\{i\}\)\>w, moveiito the corresponding larger\-weight set𝒮w^​\(Bi\)\\mathcal\{S\}\_\{\\widehat\{w\}\(B\_\{i\}\)\}, and continue\. Otherwise compute the current collision scorescw​\(v\)c\_\{w\}\(v\)forv∈M⁡\(Bi\)v\\in M\(B\_\{i\}\)and choose u⋆=arg⁡minv∈M⁡\(Bi\)⁡\(cw​\(v\),id⁡\(v\)\)\.u^\{\\star\}=\\arg\\min\_\{v\\in M\(B\_\{i\}\)\}\\bigl\(c\_\{w\}\(v\),\\mathrm\{id\}\(v\)\\bigr\)\. 5. \(e\)Letℐw​\(u⋆\)\\mathcal\{I\}\_\{w\}\(u^\{\\star\}\)be the associated degree\-wwblock indices of the new root\. Cluster all currently unassigned vertices in ⋃j∈ℐw​\(u⋆\)Bj\\bigcup\_\{j\\in\\mathcal\{I\}\_\{w\}\(u^\{\\star\}\)\}B\_\{j\}tou⋆u^\{\\star\}and set those blocks to∅\\varnothing\. For each degree\-wwvertexvvin that union, use the already\-built indexℐw​\(v\)\\mathcal\{I\}\_\{w\}\(v\)to decrement by one the current countsnmin​\(⋅\)n\_\{\\min\}\(\\cdot\)of all still\-active associated blocks, then deletevvfromℐw​\(⋅\)\\mathcal\{I\}\_\{w\}\(\\cdot\)\. If the count of an active block drops to00, then no degree\-wwvertex remains in it; recomputew^​\(Bi\)\>w\\widehat\{w\}\(B\_\{i\}\)\>wand move it to the corresponding larger\-weight set𝒮w^​\(Bi\)\\mathcal\{S\}\_\{\\widehat\{w\}\(B\_\{i\}\)\}\. 6. \(f\)Delete the completed layer set𝒮w\\mathcal\{S\}\_\{w\}and continue with the next nonempty weight layer\.
5. 5\.Output root setRRand vertex\-to\-root mapϕ\\phi\(including both weight\-1 preclusion and layered greedy assignments\)\.

For one update step of Algorithm[3](https://arxiv.org/html/2609.17951#Thmalgorithm3)or Algorithm[4](https://arxiv.org/html/2609.17951#Thmalgorithm4)on a current residual familyℱ\\mathcal\{F\}and block\-weight layerww, let𝒬\\mathcal\{Q\}be the block collection absorbed by that step:

𝒬=\{Bt⋆\}\\mathcal\{Q\}=\\\{B\_\{t\}^\{\\star\}\\\}for the covering algorithm, and

𝒬=\{Bj:j∈ℐw​\(u⋆\)\}\\mathcal\{Q\}=\\\{B\_\{j\}:j\\in\\mathcal\{I\}\_\{w\}\(u^\{\\star\}\)\\\}for the clustering algorithm\. Let

A⁡\(𝒬\):=⋃B∈𝒬BA\(\\mathcal\{Q\}\):=\\bigcup\_\{B\\in\\mathcal\{Q\}\}Bbe the vertices covered or clustered by the step\.

###### Proposition 4\(Implicit suppression for block\-weight witnesses\)\.

Ifa∈A⁡\(𝒬\)a\\in A\(\\mathcal\{Q\}\)is a current block\-weight witness,

dℱ​\(a\)=w,d\_\{\\mathcal\{F\}\}\(a\)=w,and an active vertexbbsatisfies

Iℱ​\(a\)⊆Iℱ​\(b\),I\_\{\\mathcal\{F\}\}\(a\)\\subseteq I\_\{\\mathcal\{F\}\}\(b\),thenb∈A⁡\(𝒬\)b\\in A\(\\mathcal\{Q\}\)as well\. Consequently, a vertex whose current support is a superset of an absorbed block\-weight witness cannot survive beyond that absorbing step\. Thus the low\-to\-high flow of Algorithms[3](https://arxiv.org/html/2609.17951#Thmalgorithm3)and[4](https://arxiv.org/html/2609.17951#Thmalgorithm4)performs a local, implicit form of superset suppression for current minimum\-degree witnesses, without running a global support\-containment pass\.

###### Proof\.

Sincea∈A⁡\(𝒬\)a\\in A\(\\mathcal\{Q\}\), there exists some absorbed blockB∈𝒬B\\in\\mathcal\{Q\}witha∈Ba\\in B\. Hence the index ofBBbelongs toIℱ​\(a\)I\_\{\\mathcal\{F\}\}\(a\)\. The containmentIℱ​\(a\)⊆Iℱ​\(b\)I\_\{\\mathcal\{F\}\}\(a\)\\subseteq I\_\{\\mathcal\{F\}\}\(b\)impliesb∈Bb\\in B\. Thereforeb∈A⁡\(𝒬\)b\\in A\(\\mathcal\{Q\}\)\.

In Algorithm[3](https://arxiv.org/html/2609.17951#Thmalgorithm3), all vertices inA⁡\(𝒬\)=Bt⋆A\(\\mathcal\{Q\}\)=B\_\{t\}^\{\\star\}are added to the covered set and removed from subsequent residual blocks\. In Algorithm[4](https://arxiv.org/html/2609.17951#Thmalgorithm4), all currently unassigned vertices inA⁡\(𝒬\)A\(\\mathcal\{Q\}\)are assigned to the chosen root and removed from later layer processing\. Thus any active support\-supersetbbis suppressed no later than the step that absorbs the current block\-weight witnessaa\. ∎

This proposition is deliberately weaker than the fixed\-point statement of Algorithm[1](https://arxiv.org/html/2609.17951#Thmalgorithm1)\. It does not claim that covering or clustering computes a full dominance closure, nor does it claim a suppression property for arbitrary nonminimum vertices incidentally absorbed by a selected block\. Rather, it explains why explicit superset reduction is unnecessary inside their low\-to\-high inner loops for the vertices that actually drive the layer order: once a selected block absorbs a current block\-weight witness, every active vertex whose support contains that witness support is absorbed automatically\.

This restriction to block\-weight witnesses is also the right structural focus\. The closed\-form bound charges each block by the inverse of its minimum incident degree, so the vertices attaining, or nearly attaining, block weights determine the bottleneck terms in the certificate and drive both the covering scorent​\(B\)n\_\{t\}\(B\)and the clustering scorenmin​\(B\)n\_\{\\min\}\(B\)\. Superset effects involving only higher\-degree nonminimum vertices may exist, but they do not control the first\-order block\-weight certificate\. The low\-to\-high algorithms therefore spend their local update budget on the near\-minimum witnesses that dominate the bound, rather than on a global dominance closure over all vertices\.

This algorithm is genuinely layered: each weight level is cleaned first, then resolved by repeated maximum\-nmin​\(B\)n\_\{\\min\}\(B\)choices driven by the current degree\-wwvertex\-to\-block index\. It therefore keeps the two structural priorities suggested by Theorem[5](https://arxiv.org/html/2609.17951#Thmtheorem5)and Theorem[6](https://arxiv.org/html/2609.17951#Thmtheorem6)while localizing all updates to the blocks touched by the newly attached degree\-wwvertices\.

The following worked example continues the running example from Examples[2](https://arxiv.org/html/2609.17951#S2)–[4\.1](https://arxiv.org/html/2609.17951#S4.SS1)\. Here the focus is no longer on the incidence data or the closed\-form sum, but on how the layered greedy procedure realizes that bound and why it naturally leads to the exactness theorem\.

Example 1\(f\) \(Worked example for the greedy layered clustering algorithm\)\.For the running example, now partition the block indices into

𝒥1=\{1\},𝒥2=\{2,3\},𝒥3=\{4,5\},𝒥4=\{6,7,8\},𝒥5=\{9,10,11,12\},\\mathcal\{J\}\_\{1\}=\\\{1\\\},\\qquad\\mathcal\{J\}\_\{2\}=\\\{2,3\\\},\\qquad\\mathcal\{J\}\_\{3\}=\\\{4,5\\\},\\qquad\\mathcal\{J\}\_\{4\}=\\\{6,7,8\\\},\\qquad\\mathcal\{J\}\_\{5\}=\\\{9,10,11,12\\\},with canonical quotient representatives

z1=a,z2=b,z3=e,z4=c,z5=r\.z\_\{1\}=a,\\qquad z\_\{2\}=b,\\qquad z\_\{3\}=e,\\qquad z\_\{4\}=c,\\qquad z\_\{5\}=r\.Component contraction would still select only one vertex on this connected family, while the dominance\-reduced block certificate gives the optimal value55\. The remaining question is whether the greedy layered clustering algorithm can realize that value without an explicit global dominance pass\. The key mechanism is support\-superset suppression\. The vertexuusatisfies

I⁡\(u\)=\{1,2\},I\(u\)=\\\{1,2\\\},so it strictly containsI⁡\(a\)=\{1\}I\(a\)=\\\{1\\\}\. The smaller\-weight branch applies because its extra block is attached to the lower\-weight blockB1B\_\{1\}:

The gate verticesffandggsimilarly satisfy

I⁡\(f\)=\{2,3,9\},I⁡\(g\)=\{4,5,10\},I\(f\)=\\\{2,3,9\\\},\\qquad I\(g\)=\\\{4,5,10\\\},with

I⁡\(b\)=\{2,3\}⊊I⁡\(f\),I⁡\(e\)=\{4,5\}⊊I⁡\(g\)\.I\(b\)=\\\{2,3\\\}\\subsetneq I\(f\),\\qquad I\(e\)=\\\{4,5\\\}\\subsetneq I\(g\)\.Thusffandggare suppressed by the weight\-22representativesbbandee, respectively\. Before they are suppressed, they gate the blocksB9B\_\{9\}andB10B\_\{10\}down to apparent weight33; after suppression, those blocks recover their true reduced weight44\.

The greedy layered clustering algorithm now proceeds as follows\.

1. \(i\)Weight\-1 preclusion choosesaafromB1B\_\{1\}, clustering away the support\-superset distractoruu\. This is the algorithmic version of the first dominance deletion used by Theorem[4](https://arxiv.org/html/2609.17951#Thmtheorem4):B2B\_\{2\}losesuubefore the weight\-22layer is processed\.
2. \(ii\)In the weight\-2 layer, blocksB2,B3B\_\{2\},B\_\{3\}havebbas their degree\-2 representative, whileB4,B5B\_\{4\},B\_\{5\}haveeeas their degree\-2 representative\. The algorithm choosesbband clusters the unionB2∪B3B\_\{2\}\\cup B\_\{3\}, thereby removingffand the helpersp,qp,qfrom those two blocks; it then chooseseefromB4,B5B\_\{4\},B\_\{5\}, removingggfrom the remaining active family\. This exposesB9B\_\{9\}andB10B\_\{10\}as true weight\-44blocks in the dominance\-reduced view\.
3. \(iii\)In the weight\-3 layer, the residual blocks are B6=\{c,x\},B7=\{c,y\},B8=\{c,x,y\},\\displaystyle B\_\{6\}=\\\{c,x\\\},\\qquad B\_\{7\}=\\\{c,y\\\},\\qquad B\_\{8\}=\\\{c,x,y\\\},B9=\{r,x\},B10=\{r,y\},B11=\{r,x\},B12=\{r,y\}\.\\displaystyle B\_\{9\}=\\\{r,x\\\},\\qquad B\_\{10\}=\\\{r,y\\\},\\qquad B\_\{11\}=\\\{r,x\\\},\\qquad B\_\{12\}=\\\{r,y\\\}\.The only degree\-33representative in this layer iscc, so the algorithm choosesccand nullifiesB6,B7,B8B\_\{6\},B\_\{7\},B\_\{8\}, thereby removingxxandyy\. The remaining weight\-44block then reduces to blocks containing onlyrr, so the algorithm choosesrr\.

The final root set is

RG=\{a,b,e,c,r\},R\_\{G\}=\\\{a,b,e,c,r\\\},so

Thus the greedy layered clustering algorithm exactly attains the dominance\-reduced closed\-form bound, while connected\-component contraction would retain only one vertex\.

###### Example 5\(Unified trace for puncturing, covering, and greedy clustering\)\.

Consider the pair/parity family from Example[4](https://arxiv.org/html/2609.17951#Thmexample4):

Pt=\{x2​t−1,x2​t\}\(t=1,…,n\),O=\{x1,x3,…,x2​n−1\},E=\{x2,x4,…,x2​n\},P\_\{t\}=\\\{x\_\{2t\-1\},x\_\{2t\}\\\}\\quad\(t=1,\\dots,n\),\\qquad O=\\\{x\_\{1\},x\_\{3\},\\dots,x\_\{2n\-1\}\\\},\\qquad E=\\\{x\_\{2\},x\_\{4\},\\dots,x\_\{2n\}\\\},withn≥3n\\geq 3\. Every vertex has degree22, so every block has weight22and the closed\-form certificate is

U⁡\(ℬ\)=n\+22\.U\(\\mathcal\{B\}\)=\\frac\{n\+2\}\{2\}\.This is loose becauseα⁡\(ℬ\)=2\\alpha\(\\mathcal\{B\}\)=2: one can retain, for example,\{x1,x4\}\\\{x\_\{1\},x\_\{4\}\\\}, whileOOandEEallow at most one odd and one even retained vertex\.

The puncturing algorithm sharpens the certificate by deleting the pair blocks\. Initially

nmin​\(Pt\)=2,nmin​\(O\)=nmin​\(E\)=n,n\_\{\\min\}\(P\_\{t\}\)=2,\\qquad n\_\{\\min\}\(O\)=n\_\{\\min\}\(E\)=n,so the high\-to\-low puncturing schedule, with minimum\-nminn\_\{\\min\}priority inside the layer, selects the pair blocks before the parity blocks\. Puncturing the pair blocks leaves the residual family\{O,E\}\\\{O,E\\\}\. After the next weight\-1 preclusion rebuild,OOandEEeach contribute one canonical unit and the residual family is empty\. Thus

Upunct=2\.U\_\{\\mathrm\{punct\}\}=2\.
The covering algorithm reaches the same certificate from the opposite direction\. It starts in the minimum layerw=2w=2and chooses maximum\-ntn\_\{t\}blocks\. Initially

nt\(O\)=nt\(E\)=n,nt\(Ps\)=2\(s=1,…,n\),n\_\{t\}\(O\)=n\_\{t\}\(E\)=n,\\qquad n\_\{t\}\(P\_\{s\}\)=2\\quad\(s=1,\\dots,n\),so it selects one parity block, sayOO, before any pair block\. After this dynamic update, all odd vertices are covered, the residual counts satisfynt​\(E\)=nn\_\{t\}\(E\)=nandnt​\(Ps\)=1n\_\{t\}\(P\_\{s\}\)=1, and the decreasing\-ntn\_\{t\}rule selectsEEnext\. Thus the selected covering family isℬ⋆=\{O,E\}\\mathcal\{B\}^\{\\star\}=\\\{O,E\\\}, whose intrinsic block weights are both one\. Therefore

Ucover=U⁡\(ℬ⋆\)=2\.U\_\{\\mathrm\{cover\}\}=U\(\\mathcal\{B\}^\{\\star\}\)=2\.
Finally, the greedy layered clustering algorithm also follows the parity structure\. In the weight\-22layer it first selects one ofOOandEE; suppose it selectsOOand chooses rootx1x\_\{1\}\. The associated blocks ofx1x\_\{1\}areOOandP1P\_\{1\}, so the step clusters away all odd\-indexed vertices andx2x\_\{2\}\. The remaining parity blockEEstill contains the even verticesx4,x6,…,x2​nx\_\{4\},x\_\{6\},\\dots,x\_\{2n\}and has the largest currentnminn\_\{\\min\}among surviving blocks\. The algorithm then chooses one even root, sayx4x\_\{4\}, and clusters the remaining even side\. The final retained set has two roots, for instance

RG=\{x1,x4\},R\_\{G\}=\\\{x\_\{1\},x\_\{4\}\\\},so

\|RG\|=Upunct=Ucover=α⁡\(ℬ\)=2\.\|R\_\{G\}\|=U\_\{\\mathrm\{punct\}\}=U\_\{\\mathrm\{cover\}\}=\\alpha\(\\mathcal\{B\}\)=2\.This example is complementary to the previous running example: the closed\-form bound is loose, but puncturing, covering, and greedy clustering all identify the same sharper two\-representative structure\.

The worked example separates the mechanisms behind greedy attainment of the structural optimum from Theorem[4](https://arxiv.org/html/2609.17951#Thmtheorem4): support\-superset distractors are first absorbed by their dominators, and this can reveal higher\-weight blocks that were hidden by low\-degree gate vertices\. The theorem below isolates the algorithmic add\-on\. The structural optimality is already certified by Theorem[4](https://arxiv.org/html/2609.17951#Thmtheorem4); the additional conditions ensure that the greedy layered clustering algorithm selects the corresponding representatives\.

For this algorithmic statement, assume the block family has been incidence\-twin compressed\. LetD⊆VD\\subseteq Vbe a set of support\-superset vertices that the greedy run suppresses before any vertex inDDcan be selected as a root\. Define

ℬ−:=\{B∖D:B∈ℬ,B∖D≠∅\}=\{Bi−:i∈ℐ−\},\\mathcal\{B\}^\{\-\}:=\\\{B\\setminus D:\\ B\\in\\mathcal\{B\},\\ B\\setminus D\\neq\\varnothing\\\}=\\\{B\_\{i\}^\{\-\}:i\\in\\mathcal\{I\}^\{\-\}\\\},and letI−​\(⋅\)I\_\{\-\}\(\\cdot\),d−​\(⋅\)d\_\{\-\}\(\\cdot\), andw−​\(⋅\)w\_\{\-\}\(\\cdot\)denote supports, degrees, and block weights inℬ−\\mathcal\{B\}^\{\-\}\. Suppose the block\-index setℐ−\\mathcal\{I\}^\{\-\}is partitioned into nonempty blocks

𝒥1,…,𝒥m,\\mathcal\{J\}\_\{1\},\\dots,\\mathcal\{J\}\_\{m\},with quotient verticesz1,…,zmz\_\{1\},\\dots,z\_\{m\}satisfying

I−​\(zt\)=𝒥t\.I\_\{\-\}\(z\_\{t\}\)=\\mathcal\{J\}\_\{t\}\.Writewt:=\|𝒥t\|w\_\{t\}:=\|\\mathcal\{J\}\_\{t\}\|and

Z:=\{z1,…,zm\}\.Z:=\\\{z\_\{1\},\\dots,z\_\{m\}\\\}\.For each block, write

ct:=cwt​\(zt\)c\_\{t\}:=c\_\{w\_\{t\}\}\(z\_\{t\}\)for the current collision score used when the first surviving block from block𝒥t\\mathcal\{J\}\_\{t\}is processed\. With this notation, the sufficient conditions for greedy attainment have three roles: suppress the support\-superset distractors before they become roots, align each block’s block weights with its representative support size, and ensure that every same\-layer competitor is either removed earlier or loses the root\-selection tie\-break\.

###### Theorem 9\(Greedy attainment after support\-superset suppression\)\.

Assume:

1. \(i\)everyv∈Dv\\in Dis clustered to some representativeztz\_\{t\}withI⁡\(zt\)⊊I⁡\(v\)I\(z\_\{t\}\)\\subsetneq I\(v\)beforevvcan be selected as a root;
2. \(ii\)for everyttand everyi∈𝒥ti\\in\\mathcal\{J\}\_\{t\}, w−​\(Bi−\)=wt;w\_\{\-\}\(B\_\{i\}^\{\-\}\)=w\_\{t\};
3. \(iii\)for everytt, everyi∈𝒥ti\\in\\mathcal\{J\}\_\{t\}, and every vertexu∈Bi−u\\in B\_\{i\}^\{\-\}with d−​\(u\)=wtandu≠zt,d\_\{\-\}\(u\)=w\_\{t\}\\qquad\\text\{and\}\\qquad u\\neq z\_\{t\},at least one of the following holds: 1. \(a\)there exists j∈I−​\(u\)∖𝒥tj\\in I\_\{\-\}\(u\)\\setminus\\mathcal\{J\}\_\{t\}such that w−​\(Bj−\)<wt;w\_\{\-\}\(B\_\{j\}^\{\-\}\)<w\_\{t\}; 2. \(b\)ifuuis still active when the first surviving block from𝒥t\\mathcal\{J\}\_\{t\}is processed, then it loses toztz\_\{t\}under the current root\-selection key: \(ct,id⁡\(zt\)\)<\(cwt​\(u\),id⁡\(u\)\)\.\\bigl\(c\_\{t\},\\mathrm\{id\}\(z\_\{t\}\)\\bigr\)<\\bigl\(c\_\{w\_\{t\}\}\(u\),\\mathrm\{id\}\(u\)\\bigr\)\.

Then the Greedy Layered Clustering Algorithm creates exactly the root set

RG=\{z1,…,zm\},R\_\{G\}=\\\{z\_\{1\},\\dots,z\_\{m\}\\\},and therefore

\|RG\|=U⁡\(ℬ−\)=α⁡\(ℬ\)\.\|R\_\{G\}\|=U\(\\mathcal\{B\}^\{\-\}\)=\\alpha\(\\mathcal\{B\}\)\.\(58\)

###### Proof\.

By Theorem[4](https://arxiv.org/html/2609.17951#Thmtheorem4), the set\{z1,…,zm\}\\\{z\_\{1\},\\dots,z\_\{m\}\\\}is maximum andα⁡\(ℬ\)=m\\alpha\(\\mathcal\{B\}\)=m\. Also, by assumption \(ii\),

U⁡\(ℬ−\)=∑t=1m∑i∈𝒥t1wt=m\.U\(\\mathcal\{B\}^\{\-\}\)=\\sum\_\{t=1\}^\{m\}\\sum\_\{i\\in\\mathcal\{J\}\_\{t\}\}\\frac\{1\}\{w\_\{t\}\}=m\.It remains only to prove that the greedy algorithm selects these representatives\.

By assumption \(i\), the vertices inDDare already clustered to representatives before they can become roots\. We may therefore analyze the subsequent block choices on the active reduced familyℬ−\\mathcal\{B\}^\{\-\}\.

Proceed in the actual order in which the algorithm reaches unresolved blocks\. Fix such a block𝒥t\\mathcal\{J\}\_\{t\}\. SinceI−​\(zt\)=𝒥tI\_\{\-\}\(z\_\{t\}\)=\\mathcal\{J\}\_\{t\}in the reduced family and every reduced block in𝒥t\\mathcal\{J\}\_\{t\}has layerwtw\_\{t\}, the representativeztz\_\{t\}cannot be removed by a smaller\-weight outside block\. Previously resolved block representatives have supports equal to their own disjoint blocks, so they do not nullify blocks in𝒥t\\mathcal\{J\}\_\{t\}\. Henceztz\_\{t\}is active when the first surviving blockBi−B\_\{i\}^\{\-\}withi∈𝒥ti\\in\\mathcal\{J\}\_\{t\}is processed in layerwtw\_\{t\}\.

Letu∈M⁡\(Bi−\)u\\in M\(B\_\{i\}^\{\-\}\)withu≠ztu\\neq z\_\{t\}\. If condition \(iii\.a\) holds foruu, then there existsj∈I−​\(u\)∖𝒥tj\\in I\_\{\-\}\(u\)\\setminus\\mathcal\{J\}\_\{t\}withw−​\(Bj−\)<wtw\_\{\-\}\(B\_\{j\}^\{\-\}\)<w\_\{t\}\. That lower\-weight block is processed before layerwtw\_\{t\}\. Sinceu∈Bj−u\\in B\_\{j\}^\{\-\}butd−​\(u\)=wt\>w−​\(Bj−\)d\_\{\-\}\(u\)=w\_\{t\}\>w\_\{\-\}\(B\_\{j\}^\{\-\}\), vertexuucannot be chosen as the root ofBj−B\_\{j\}^\{\-\}; whenBj−B\_\{j\}^\{\-\}is processed, all currently unassigned vertices in the absorbed block collection containingBj−B\_\{j\}^\{\-\}are clustered to the root chosen there, souuis removed before layerwtw\_\{t\}begins\. Thus any degree\-wtw\_\{t\}competitor still present inM⁡\(Bi−\)M\(B\_\{i\}^\{\-\}\)must satisfy condition \(iii\.b\), and hence loses toztz\_\{t\}under the current root\-selection key\.

Therefore the algorithmic choice

u⋆∈arg⁡minv∈M⁡\(Bi−\)⁡\(cwt​\(v\),id⁡\(v\)\)u^\{\\star\}\\in\\arg\\min\_\{v\\in M\(B\_\{i\}^\{\-\}\)\}\\bigl\(c\_\{w\_\{t\}\}\(v\),\\mathrm\{id\}\(v\)\\bigr\)must selectu⋆=ztu^\{\\star\}=z\_\{t\}\. The associated\-block update forztz\_\{t\}nullifies exactly the blocks indexed by𝒥t\\mathcal\{J\}\_\{t\}, and no second root can later be chosen from that block\.

Repeating this argument until all blocks have been resolved shows that the only roots created arez1,…,zmz\_\{1\},\\dots,z\_\{m\}\. ThusRG=\{z1,…,zm\}R\_\{G\}=\\\{z\_\{1\},\\dots,z\_\{m\}\\\}, and the displayed equality follows from the first paragraph\. ∎

The governing invariant is the following\.

###### Lemma 2\(block\-root uniqueness invariant\)\.

At every step of the algorithm, no block contains more than one active root\.

###### Proof\.

Initially there are no roots, so the invariant holds\. During the weight\-1 pass, exactly one root is assigned in each processed block\. During a later layer\-wwstep, once a rootu⋆u^\{\\star\}is chosen, every block inℐw​\(u⋆\)\\mathcal\{I\}\_\{w\}\(u^\{\\star\}\)is immediately clustered tou⋆u^\{\\star\}and nullified\. Hence no later step can create a second active root in any block already containingu⋆u^\{\\star\}\. No other operation increases the number of active roots in a surviving block beyond one\. ∎

By construction of the weight\-1 preclusion pass, everyB∈ℬ1B\\in\\mathcal\{B\}\_\{1\}is assigned a degree\-1 root before layered greedy processing starts\.

###### Theorem 10\(Feasibility of greedy output\)\.

The set of active roots returned by the Greedy Layered Clustering Algorithm is feasible\.

###### Proof\.

By the block\-root uniqueness invariant, each block contains at most one active root at termination\. Since the retained set is exactly the set of active roots, it satisfies the feasibility condition\. ∎

LetRGR\_\{G\}denote the final active\-root set returned by the Greedy Layered Clustering Algorithm\.

###### Proposition 5\(Maximality of greedy output\)\.

RGR\_\{G\}is a maximal feasible set: for everyx∈V∖RGx\\in V\\setminus R\_\{G\}, the setRG∪\{x\}R\_\{G\}\\cup\\\{x\\\}is infeasible\.

###### Proof\.

Every non\-root vertex is attached during processing to a block that already contains an active root, or is attached to a newly created root in that block\. Hence for eachx∉RGx\\notin R\_\{G\}, there exists a blockBx∈ℬB\_\{x\}\\in\\mathcal\{B\}withx∈Bxx\\in B\_\{x\}andBx∩RG≠∅B\_\{x\}\\cap R\_\{G\}\\neq\\varnothing\. Addingxxwould create at least two retained elements inBxB\_\{x\}, violating feasibility\. ∎

The next result records a generic component\-baseline consequence of maximality\.

For anyR⊆VR\\subseteq V, write

ℬ\|R:=\{B∩R:B∈ℬ,B∩R≠∅\}\\mathcal\{B\}\|\_\{R\}:=\\\{B\\cap R:\\ B\\in\\mathcal\{B\},\\ B\\cap R\\neq\\varnothing\\\}for the induced block family\. Letmmbe the number of connected components of the block\-overlap graphGℬG\_\{\\mathcal\{B\}\}\.

###### Proposition 6\(Maximal feasible sets meet every component\)\.

For any feasible setR⊆VR\\subseteq V, every induced block inℬ\|R\\mathcal\{B\}\|\_\{R\}has size at most one\. If, in addition,RRis maximal feasible, thenRRcontains at least one vertex in every connected component𝒦i\\mathcal\{K\}\_\{i\}ofGℬG\_\{\\mathcal\{B\}\}\. Consequently,

In particular, the greedy layered clustering outputRGR\_\{G\}has size at least the number of block\-overlap components\.

###### Proof\.

IfRRis feasible, then by definition\|R∩B\|≤1\|R\\cap B\|\\leq 1for everyB∈ℬB\\in\\mathcal\{B\}, so every induced blockB∩RB\\cap Rhas size at most one\.

Now assume thatRRis maximal feasible\. Let𝒦1,…,𝒦m\\mathcal\{K\}\_\{1\},\\dots,\\mathcal\{K\}\_\{m\}be the connected components ofGℬG\_\{\\mathcal\{B\}\}, with corresponding vertex domainsVi=⋃B∈𝒦iBV\_\{i\}=\\bigcup\_\{B\\in\\mathcal\{K\}\_\{i\}\}B\. These domains are pairwise disjoint: otherwise a vertex shared by two domains would belong to blocks in two different components, creating an overlap edge between them\. If some component domainViV\_\{i\}contained no retained vertex, then for anyx∈Vix\\in V\_\{i\}the setR∪\{x\}R\\cup\\\{x\\\}would remain feasible: blocks outside𝒦i\\mathcal\{K\}\_\{i\}are disjoint fromViV\_\{i\}, and blocks inside𝒦i\\mathcal\{K\}\_\{i\}contain no element ofRR\. This contradicts maximality\. Hence every component contributes at least one retained vertex, so\|R\|≥m\|R\|\\geq m\. Applying this withR=RGR=R\_\{G\}gives the final claim, sinceRGR\_\{G\}is feasible and maximal by the previous two results\. ∎

The result explains why component contraction is a weak baseline for the strong\-independence objective\. In the minimal chain

B1=\{a,b\},B2=\{b,c\},B\_\{1\}=\\\{a,b\\\},\\qquad B\_\{2\}=\\\{b,c\\\},the feasible setR=\{a,c\}R=\\\{a,c\\\}induces only singleton blocks,

B1∩R=\{a\},B2∩R=\{c\}\.B\_\{1\}\\cap R=\\\{a\\\},\\qquad B\_\{2\}\\cap R=\\\{c\\\}\.The overlap path throughbbis a property of the constraint representation, not a reason to forbid selecting bothaaandcc\.

The next proposition records the first\-order reason for the layer schedule: lower block weight means larger contribution to the closed\-form obstruction\.

###### Proposition 7\(Upper\-bound alignment\)\.

Ifw⁡\(B1\)≤w⁡\(B2\)w\(B\_\{1\}\)\\leq w\(B\_\{2\}\), then blockB1B\_\{1\}contributes at least as much to the block\-weight upper bound asB2B\_\{2\}:

1w⁡\(B1\)≥1w⁡\(B2\)\.\\frac\{1\}\{w\(B\_\{1\}\)\}\\geq\\frac\{1\}\{w\(B\_\{2\}\)\}\.\(59\)

###### Proof\.

The reciprocal function is decreasing on positive block weights\. ∎

Within a fixed current layer, Theorem[6](https://arxiv.org/html/2609.17951#Thmtheorem6)further motivates prioritizing blocks with largernmin​\(B\)n\_\{\\min\}\(B\)\. Thus the layered schedule first resolves the most constraining weight level and then, inside that level, the blocks with stronger minimum\-weight covering pressure\.

This block\-first viewpoint is the decisive difference from generic hypergraph MIS methods\. The latter are typically vertex\-centric, whereas the certificates and greedy schedule here operate directly on the materialized incidence relation: block lists, vertex\-to\-block support lists, and root assignments\.

## 6Algorithmic Interpretation and Complexity

The previous section specified the greedy clustering routine and its feasibility, maximality, and conditional optimality guarantees\. We now record three complementary facts: an exactness regime, an algorithm\-aware upper bound induced by the greedy chronology itself, and coarse implementation costs in incidence\-list units\.

### 6\.1Exactness and Algorithm\-Aware Bounds

A first sanity check is the decomposable case\.

###### Proposition 8\(Exactness on disjoint block families\)\.

If the blocks are pairwise disjoint, the Greedy Layered Clustering Algorithm is optimal\.

###### Proof\.

When the blocks are pairwise disjoint, the feasibility constraint decomposes block by block, and retaining one representative per nonempty block is optimal\. The greedy routine processes each nonempty block once: choosing a root in one block cannot remove or constrain any vertex in another block because there is no block overlap\. Thus the algorithm creates exactly one root per nonempty block, attaining the decomposed optimum\. ∎

It is also useful to treat the closed\-form valueU⁡\(ℬ\)U\(\\mathcal\{B\}\)as an instance\-level certificate target\. Since Theorem[5](https://arxiv.org/html/2609.17951#Thmtheorem5)givesα⁡\(ℬ\)≤U⁡\(ℬ\)\\alpha\(\\mathcal\{B\}\)\\leq U\(\\mathcal\{B\}\), ifRGR\_\{G\}denotes the retained set returned by the greedy algorithm, then

ηG:=\|RG\|U⁡\(ℬ\)\\eta\_\{G\}:=\\frac\{\|R\_\{G\}\|\}\{U\(\\mathcal\{B\}\)\}\(60\)measures how closely the constructed feasible set approaches the explicit structural upper bound\. This ratio is meaningful even when exact optimum computation is unavailable, because both\|RG\|\|R\_\{G\}\|andU⁡\(ℬ\)U\(\\mathcal\{B\}\)are computed directly from the materialized incidence data\.

The next theorem gives a finer, algorithm\-aware upper bound\. WhereasU⁡\(ℬ\)U\(\\mathcal\{B\}\)depends only on static block weights, this bound uses the actual layer\-by\-layer assignments made by Algorithm[4](https://arxiv.org/html/2609.17951#Thmalgorithm4)\. For the comparison, assumed⁡\(v\)≥1d\(v\)\\geq 1for allv∈Vv\\in V\. Let

ℬ1:=\{B∈ℬ:w⁡\(B\)=1\},ℬ\>1:=ℬ∖ℬ1\.\\mathcal\{B\}\_\{1\}:=\\\{B\\in\\mathcal\{B\}:w\(B\)=1\\\},\\qquad\\mathcal\{B\}\_\{\>1\}:=\\mathcal\{B\}\\setminus\\mathcal\{B\}\_\{1\}\.\(61\)LetO⋆O^\{\\star\}be an optimal feasible set satisfying the canonical weight\-1 conclusion of Theorem[2](https://arxiv.org/html/2609.17951#Thmtheorem2), and write

Z:=\{zB:B∈ℬ1\}⊆O⋆\.Z:=\\\{z\_\{B\}:B\\in\\mathcal\{B\}\_\{1\}\\\}\\subseteq O^\{\\star\}\.\(62\)For each layerww, letRw⊆RGR\_\{w\}\\subseteq R\_\{G\}be the set of roots created in layerww\. For eachr∈Rwr\\in R\_\{w\}, define the associated block family consumed by that root as

𝒜w​\(r\):=\{Bj:j∈ℐw​\(r\)\}\.\\mathcal\{A\}\_\{w\}\(r\):=\\\{B\_\{j\}:\\ j\\in\\mathcal\{I\}\_\{w\}\(r\)\\\}\.\(63\)For each vertexx∈V∖Zx\\in V\\setminus Z, letτ⁡\(x\)=w\\tau\(x\)=wbe the layer in whichxxis first removed from further processing by the greedy algorithm, including the case wherexxitself is chosen as a root in layerww\. Define the layer\-wwwitness graph

Gw:=\(Xw,Γw,Ew\)G\_\{w\}:=\\bigl\(X\_\{w\},\\Gamma\_\{w\},E\_\{w\}\\bigr\)\(64\)with left side

Xw:=\{x∈V∖Z:τ⁡\(x\)=w\},X\_\{w\}:=\\\{x\\in V\\setminus Z:\\tau\(x\)=w\\\},\(65\)right side

Γw:=\{\(r,B\):r∈Rw,B∈𝒜w\(r\)\},\\Gamma\_\{w\}:=\\\{\(r,B\):r\\in R\_\{w\},\\ B\\in\\mathcal\{A\}\_\{w\}\(r\)\\\},\(66\)and edge relation

x∼\(r,B\)⟺x∈B\.x\\sim\(r,B\)\\quad\\Longleftrightarrow\\quad x\\in B\.\(67\)Writeν⁡\(Gw\)\\nu\(G\_\{w\}\)for the maximum matching size inGwG\_\{w\}\.

###### Theorem 11\(Layered witness\-matching upper bound\)\.

α⁡\(ℬ\)≤\|ℬ1\|\+∑wν⁡\(Gw\)\.\\alpha\(\\mathcal\{B\}\)\\leq\|\\mathcal\{B\}\_\{1\}\|\+\\sum\_\{w\}\\nu\(G\_\{w\}\)\.\(68\)

###### Proof\.

By Theorem[2](https://arxiv.org/html/2609.17951#Thmtheorem2), chooseO⋆O^\{\\star\}so thatZ⊆O⋆Z\\subseteq O^\{\\star\}and\|Z\|=\|ℬ1\|\|Z\|=\|\\mathcal\{B\}\_\{1\}\|\. Let

O\+:=O⋆∖Z\.O^\{\+\}:=O^\{\\star\}\\setminus Z\.Then

\|O⋆\|=\|ℬ1\|\+\|O\+\|\.\|O^\{\\star\}\|=\|\\mathcal\{B\}\_\{1\}\|\+\|O^\{\+\}\|\.
For each layerww, let

Ow\+:=\{x∈O\+:τ⁡\(x\)=w\}\.O\_\{w\}^\{\+\}:=\\\{x\\in O^\{\+\}:\\tau\(x\)=w\\\}\.We claim that\|Ow\+\|≤ν⁡\(Gw\)\|O\_\{w\}^\{\+\}\|\\leq\\nu\(G\_\{w\}\)for everyww\. Fixwwandx∈Ow\+x\\in O\_\{w\}^\{\+\}\. By definition ofτ⁡\(x\)\\tau\(x\), the vertexxxis first removed in layerwwwhen some rootrx∈Rwr\_\{x\}\\in R\_\{w\}is chosen and one of its associated blocksBx∈𝒜w​\(rx\)B\_\{x\}\\in\\mathcal\{A\}\_\{w\}\(r\_\{x\}\)containsxx\. Hence\(rx,Bx\)∈Γw\(r\_\{x\},B\_\{x\}\)\\in\\Gamma\_\{w\}andx∼\(rx,Bx\)x\\sim\(r\_\{x\},B\_\{x\}\)\.

MoreoverBx∈ℬ\>1B\_\{x\}\\in\\mathcal\{B\}\_\{\>1\}\. IfBx∈ℬ1B\_\{x\}\\in\\mathcal\{B\}\_\{1\}, thenzBx∈Z⊆O⋆z\_\{B\_\{x\}\}\\in Z\\subseteq O^\{\\star\}and alsox∈Bx∩O⋆x\\in B\_\{x\}\\cap O^\{\\star\}withx≠zBxx\\neq z\_\{B\_\{x\}\}, contradicting feasibility ofO⋆O^\{\\star\}\.

The edges\{\(x,\(rx,Bx\)\):x∈Ow\+\}\\\{\(x,\(r\_\{x\},B\_\{x\}\)\):x\\in O\_\{w\}^\{\+\}\\\}form a matching inGwG\_\{w\}\. Distinct vertices ofOw\+O\_\{w\}^\{\+\}are distinct on the left\. They are also distinct on the right: if two distinct verticesx,y∈Ow\+x,y\\in O\_\{w\}^\{\+\}were assigned to the same right vertex\(r,B\)\(r,B\), thenx,y∈O⋆∩Bx,y\\in O^\{\\star\}\\cap B, contradicting feasibility ofO⋆O^\{\\star\}\. Therefore\|Ow\+\|≤ν⁡\(Gw\)\|O\_\{w\}^\{\+\}\|\\leq\\nu\(G\_\{w\}\)\.

Summing over all layers,

\|O\+\|=∑w\|Ow\+\|≤∑wν⁡\(Gw\)\.\|O^\{\+\}\|=\\sum\_\{w\}\|O\_\{w\}^\{\+\}\|\\leq\\sum\_\{w\}\\nu\(G\_\{w\}\)\.Thus

α⁡\(ℬ\)=\|O⋆\|≤\|ℬ1\|\+∑wν⁡\(Gw\)\.\\alpha\(\\mathcal\{B\}\)=\|O^\{\\star\}\|\\leq\|\\mathcal\{B\}\_\{1\}\|\+\\sum\_\{w\}\\nu\(G\_\{w\}\)\.∎

Example[5](https://arxiv.org/html/2609.17951#Thmexample5)gives a concrete witness picture\. There are no weight\-1 blocks, soZ=∅Z=\\varnothing\. If the greedy roots arex1x\_\{1\}andx4x\_\{4\}, then the right side ofG2G\_\{2\}consists of block\-root pairs consumed by those two choices, such as\(x1,O\)\(x\_\{1\},O\),\(x1,P1\)\(x\_\{1\},P\_\{1\}\),\(x4,E\)\(x\_\{4\},E\), and\(x4,P2\)\(x\_\{4\},P\_\{2\}\)\. Any feasible optimum can be injected into these consumed pairs by assigning each optimal vertex to a block that first removes it\. The matching condition is exactly feasibility: two optimal vertices cannot be assigned to the same consumed block\.

### 6\.2Complexity

The algorithms above are intended for instances where the incidence relation is materialized\. Let

I:=∑v∈Vd⁡\(v\)=∑B∈ℬ\|B\|I:=\\sum\_\{v\\in V\}d\(v\)=\\sum\_\{B\\in\\mathcal\{B\}\}\|B\|\(69\)be the total vertex\-block incidence\. LetMres:=\|ℬres\|M\_\{\\mathrm\{res\}\}:=\|\\mathcal\{B\}^\{\\mathrm\{res\}\}\|be the number of residual blocks after incidence\-twin compression and weight\-1 preclusion\.

###### Proposition 9\(Preprocessing cost\)\.

Computing vertex degrees, performing weight\-1 preclusion, removing clustered vertices, and initializing residual block weights requireO⁡\(I\)O\(I\)time\.

###### Proof\.

Using vertex\-to\-block incidence lists, the initial degree computation scans each incidence once\. During weight\-1 preclusion, each clustered vertex class is removed from later consideration once, and affected block records are updated through their incident lists\. Residual block weights are initialized by scanning the surviving residual block records\. Each operation is charged to an original or surviving incidence a constant number of times, giving total workO⁡\(I\)O\(I\)\. ∎

###### Proposition 10\(Layer\-set initialization cost\)\.

Placing each residual block index into its initial weight set𝒮w^​\(B\)\\mathcal\{S\}\_\{\\widehat\{w\}\(B\)\}requiresO⁡\(Mres\)O\(M\_\{\\mathrm\{res\}\}\)time\.

###### Proof\.

After residual weights have been computed, each residual block contributes exactly one index insertion into the set corresponding to its initial weight\. ∎

Let

Jres:=∑B∈ℬres∑t=1kB\|B\(t\)\|J\_\{\\mathrm\{res\}\}:=\\sum\_\{B\\in\\mathcal\{B\}^\{\\mathrm\{res\}\}\}\\sum\_\{t=1\}^\{k\_\{B\}\}\|B^\{\(t\)\}\|\(70\)be the total incidence scanned across all residual block states, wherekBk\_\{B\}is the number of times residual blockBBis visited andB\(t\)B^\{\(t\)\}is its live vertex set during thett\-th layer\-cleaning or layer\-clustering pass\. LetTindexT\_\{\\mathrm\{index\}\}denote the total work needed to build and update the layer\-local vertex\-to\-block indicesℐw​\(⋅\)\\mathcal\{I\}\_\{w\}\(\\cdot\), and letTscoreT\_\{\\mathrm\{score\}\}denote the total work needed to evaluate the collision scorescw​\(⋅\)c\_\{w\}\(\\cdot\)at the selected blocks\.

###### Proposition 11\(Coarse clustering complexity\)\.

If the currentnmin​\(B\)n\_\{\\min\}\(B\)values are maintained in an integer\-keyed bucketed queue, or any equivalent priority structure supportingO⁡\(1\)O\(1\)amortized decrement/update inside a fixed layer, then the layered greedy stage runs in

O⁡\(Jres\+Tindex\+Tscore\)O\\\!\\left\(J\_\{\\mathrm\{res\}\}\+T\_\{\\mathrm\{index\}\}\+T\_\{\\mathrm\{score\}\}\\right\)\(71\)time\.

###### Proof\.

Residual block scans contributeJresJ\_\{\\mathrm\{res\}\}\. Building and updating the layer\-local degree\-wwincidence tables contributesTindexT\_\{\\mathrm\{index\}\}\. On\-demand collision\-score evaluations at selected blocks contributeTscoreT\_\{\\mathrm\{score\}\}\. A global within\-layer sort is unnecessary: onceℐw​\(⋅\)\\mathcal\{I\}\_\{w\}\(\\cdot\)and the initialnmin​\(B\)n\_\{\\min\}\(B\)values are built, each decrement of a current\-layer counter is triggered by deleting some degree\-wwvertex from the index, so every current\-layer incidence is touched only when its degree\-wwendpoint is clustered away\. Since each residual block has at least one member, the initialization termO⁡\(Mres\)O\(M\_\{\\mathrm\{res\}\}\)is absorbed byO⁡\(Jres\)O\(J\_\{\\mathrm\{res\}\}\)\. ∎

Equivalently, with residual scan amplification

σres:=JresI,\\sigma\_\{\\mathrm\{res\}\}:=\\frac\{J\_\{\\mathrm\{res\}\}\}\{I\},the coarse bound is

O⁡\(σres​I\+Tindex\+Tscore\)\.O\\\!\\left\(\\sigma\_\{\\mathrm\{res\}\}I\+T\_\{\\mathrm\{index\}\}\+T\_\{\\mathrm\{score\}\}\\right\)\.Thus the implemented loop is incidence\-local: it does not construct induced subhypergraphs, dual graphs, or neighborhood\-exchange structures, and its dominant cost is the number of live incidences actually scanned during residual layer processing\.

## 7Conclusion

We formulated a structural theory for maximum strong independent set in finite hypergraphs, focused on the incidence patterns that arise when hyperedges are local incompatibility blocks rather than transitive equivalence classes\. The main contributions are exact reductions, block\-weight upper bounds, puncturing and covering certificates, and a layered greedy clustering algorithm with feasibility, maximality, witness\-matching, complexity, and optimality guarantees under explicit incidence conditions\.

The framework emphasizes that local hyperedge constraints should be handled through their incidence structure rather than collapsed into a coarser graph\-level surrogate\. Future work should sharpen worst\-case approximation guarantees for the layered greedy algorithm, characterize when puncturing and covering certificates are tight, and develop graph\-native versions of the certificate framework\. Since ordinary graph MIS is the 2\-uniform special case, the more substantial question is how to recover useful block\-like incidence decompositions and certificate\-guided greedy schedules for general graph instances whose constraints are not already presented as explicit local blocks\.

## References

- \[1\]Andrei Z\. Broder\.On the resemblance and containment of documents\.In*Proceedings of the Compression and Complexity of Sequences 1997*, pages 21–29\. IEEE, 1997\.DOI:[10\.1109/SEQUEN\.1997\.666900](https://doi.org/10.1109/SEQUEN.1997.666900)\.
- \[2\]Andrei Z\. Broder\.Identifying and filtering near\-duplicate documents\.In*Combinatorial Pattern Matching \(CPM 2000\)*, volume 1848 of LNCS, pages 1–10\. Springer, 2000\.DOI:[10\.1007/3\-540\-45123\-4\_1](https://doi.org/10.1007/3-540-45123-4_1)\.
- \[3\]Gurmeet Singh Manku, Arvind Jain, and Anish Das Sarma\.Detecting near\-duplicates for web crawling\.In*Proceedings of the 16th International Conference on World Wide Web*, pages 141–150\. ACM, 2007\.DOI:[10\.1145/1242572\.1242592](https://doi.org/10.1145/1242572.1242592)\.
- \[4\]Moses S\. Charikar\.Similarity estimation techniques from rounding algorithms\.In*Proceedings of the Thirty\-Fourth Annual ACM Symposium on Theory of Computing*, pages 380–388\. ACM, 2002\.DOI:[10\.1145/509907\.509965](https://doi.org/10.1145/509907.509965)\.
- \[5\]Noga Alon, Uri Arad, and Yossi Azar\.Independent sets in hypergraphs with applications to routing via fixed paths\.In Dorit S\. Hochbaum, Klaus Jansen, José D\. P\. Rolim, and Alistair Sinclair, editors,*Randomization, Approximation, and Combinatorial Optimization\. Algorithms and Techniques \(RANDOM\-APPROX 1999\)*, volume 1671 of LNCS, pages 16–27\. Springer, 1999\.DOI:[10\.1007/978\-3\-540\-48413\-4\_3](https://doi.org/10.1007/978-3-540-48413-4_3)\.
- \[6\]Georg Gottlob and Gianluigi Greco\.Decomposing combinatorial auctions and set packing problems\.*Journal of the ACM*, 60\(4\):24:1–24:39, 2013\.DOI:[10\.1145/2508028\.2505987](https://doi.org/10.1145/2508028.2505987)\.
- \[7\]Yingquan \(Cody\) Wu and Jason Cong\.Bucket\-feasible LSH\-MinHash for deduplication and query\.Companion manuscript prepared for submission to the*Journal of Machine Learning Research*, 2026\.
- \[8\]Richard M\. Karp\.Reducibility among combinatorial problems\.In Raymond E\. Miller and James W\. Thatcher, editors,*Complexity of Computer Computations*, pages 85–103\. Plenum Press, 1972\.
- \[9\]Jack Edmonds\.Paths, trees, and flowers\.*Canadian Journal of Mathematics*, 17:449–467, 1965\.DOI:[10\.4153/CJM\-1965\-045\-4](https://doi.org/10.4153/CJM-1965-045-4)\.
- \[10\]Magnus M\. Halldorsson and Elena Losievskaja\.Independent sets in bounded\-degree hypergraphs\.*Discrete Applied Mathematics*, 157\(8\):1773–1786, 2009\.DOI:[10\.1016/j\.dam\.2008\.11\.013](https://doi.org/10.1016/j.dam.2008.11.013)\.
- \[11\]Thomas Hofmeister and Hanno Lefmann\.Approximating maximum independent sets in uniform hypergraphs\.In*Automata, Languages and Programming \(ICALP 1998\)*, volume 1443 of LNCS, pages 562–570\. Springer, 1998\.DOI:[10\.1007/BFb0055806](https://doi.org/10.1007/BFb0055806)\.
- \[12\]Geir Agnarsson, Magnus M\. Halldorsson, and Elena Losievskaja\.SDP\-based algorithms for maximum independent set problems on hypergraphs\.*Theoretical Computer Science*, 470:1–9, 2013\.DOI:[10\.1016/j\.tcs\.2012\.11\.025](https://doi.org/10.1016/j.tcs.2012.11.025)\.
- \[13\]Ernestine Großmann, Christian Schulz, Darren Strash, and Antonie Wagner\.Data reductions for the strong maximum independent set problem in hypergraphs\.*arXiv preprint arXiv:2602\.10781*, 2026\.DOI:[10\.48550/arXiv\.2602\.10781](https://doi.org/10.48550/arXiv.2602.10781)\.
- \[14\]C\. A\. J\. Hurkens and A\. Schrijver\.On the size of systems of sets everyttof which have an SDR, with an application to the worst\-case ratio of heuristics for packing problems\.*SIAM Journal on Discrete Mathematics*, 2\(1\):68–72, 1989\.DOI:[10\.1137/0402008](https://doi.org/10.1137/0402008)\.
- \[15\]Elad Hazan, Shmuel Safra, and Oded Schwartz\.On the complexity of approximatingkk\-set packing\.*Computational Complexity*, 15\(1\):20–39, 2006\.DOI:[10\.1007/s00037\-006\-0205\-6](https://doi.org/10.1007/s00037-006-0205-6)\.
- \[16\]Maxim Sviridenko and Justin Ward\.Large neighborhood local search for the maximum set packing problem\.In*Proceedings of the 40th International Colloquium on Automata, Languages, and Programming \(ICALP 2013, Part I\)*, volume 7965 of LNCS, pages 792–803\. Springer, 2013\.DOI:[10\.1007/978\-3\-642\-39206\-1\_67](https://doi.org/10.1007/978-3-642-39206-1_67)\.
- \[17\]Marek Cygan\.Improved approximation for 3\-dimensional matching via bounded pathwidth local search\.In*Proceedings of the 54th IEEE Annual Symposium on Foundations of Computer Science \(FOCS\)*, pages 509–518, 2013\.DOI:[10\.1109/FOCS\.2013\.61](https://doi.org/10.1109/FOCS.2013.61)\.
- \[18\]Davi Castro\-Silva, Fernando Mário de Oliveira Filho, Lucas Slot, and Frank Vallentin\.A recursive theta body for hypergraphs\.*Combinatorica*, 43:909–938, 2023\.DOI:[10\.1007/s00493\-023\-00040\-9](https://doi.org/10.1007/s00493-023-00040-9)\.