Maximum Strong Independent Sets in Hypergraphs: Reductions, Bounds, and Greedy Certificates
Yingquan (Cody), Wu, Jason Cong
cs.LG
Quick verdict
Sound, fully proved toolkit of reductions, charging/puncturing/covering bounds, and greedy certificates for hypergraph strong independent sets — but the paper itself contains no experiments.
Summary
The paper studies the maximum strong independent set (MSIS) problem in finite hypergraphs: finding the largest vertex set that meets every hyperedge in at most one vertex, motivated by multi-band LSH-MinHash deduplication where collision buckets are local, non-transitive incompatibility blocks. It contributes a structural toolkit: exact reductions via incidence dominance, twin compression, and weight-1 canonical rooting (Theorems 1-3); a closed-form charging upper bound U(B)=sum 1/w(B) (Theorem 5) refined by weight-1 preclusion (Corollary 2), a saturated weight-2 matching certificate (Corollary 3), and iterative puncturing and greedy covering certificates with fixed-point analysis (Theorems 6-8, Propositions 1-2); and a layered greedy clustering algorithm (Algorithm 4) proven feasible, maximal, and exactly optimal under explicit incidence conditions (Theorems 4, 9), plus a witness-matching bound tied to the greedy chronology (Theorem 11) and incidence-local complexity bounds (Propositions 9-11). All results carry complete in-text proofs and are illustrated on a persistent 12-block running example. Main limitations: the manuscript contains no experiments - all empirical support (greedy within 0.57% of the puncturing bound on ClueWeb22/HPLT) is deferred to an unpublished companion manuscript; no worst-case approximation guarantee is proven for the greedy solver; and several core tools (charging bound, dominance reduction) are elementary relative to the stated Journal of the ACM target.
Review complete
Assessment at a glance
3
risk flags identified
● high 0
● medium 2
● low 1
5 strengths · 5 weaknesses · 5 author questions
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Dominance removal (I(a) subset of I(b) implies b deletable), incidence-twin compression, and weight-1 canonical rooting are exact reductions that preserve the optimum alpha(B) (Theorems 1-3).
- The closed-form block-weight sum U(B) = sum over B of 1/w(B) upper-bounds alpha(B), and weight-1 preclusion, iterative puncturing, and greedy covering produce valid, often sharper certificates with a provable covering fixed point (Theorems 5-8, Corollaries 2-3, Propositions 1-2).
- The layered greedy clustering algorithm always terminates with a feasible maximal set, and under explicit support-superset suppression, weight-alignment, and tie-break conditions it attains the exact optimum (Theorems 9-10, Propositions 4-5).
- The greedy chronology itself induces a valid upper bound alpha(B) <= |B_1| + sum over layers of the maximum matching sizes in per-layer witness graphs (Theorem 11).
- All reductions, certificates, and the clustering algorithm run in time local to the materialized incidence lists, without LP/SDP relaxations or pairwise conflict-graph construction (Propositions 9-11).
Strengths
Complete, verifiable proofs for every claim
All eleven theorems, eleven propositions, and five corollaries carry full in-text proofs. The charging argument of Theorem 5 and the fixed-point analysis of iterated covering (Theorem 8, proving every converged block has restricted weight 1) are clean and, on careful reading, correct.
Certificate hierarchy with genuine separation examples
Example 4/5 (pair+parity family) and Remark 6 show the closed-form bound U=(n+2)/2, the puncturing bound Upunct=2, the covering count Ncov, and restricted reweighting U(B*) can all differ, so computing the min over certificates is justified rather than redundant.
Honest cost accounting
Coherent running example tying theory to algorithm behavior
Clear positioning against prior machinery
Weaknesses
No empirical evidence inside the paper
No worst-case guarantee for the headline algorithm
Elementary core relative to the stated venue
Certificates are never benchmarked against relaxations
Theorem 9's exactness regime is narrow
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 3 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is a strong independent set in a hypergraph?
It is a set of vertices that contains at most one vertex from each hyperedge. Whereas ordinary graph independence only forbids pairs joined by an edge, strong hypergraph independence forbids any two selected vertices from co-occurring in any hyperedge. Finding the largest such set generalizes maximum independent set (the 2-uniform case) and maximum set packing, and is NP-hard.
Why does this problem matter for LSH-MinHash deduplication?
In multi-band LSH pipelines, each collision bucket is a hyperedge of candidates that are locally suspicious of being duplicates. Merging all overlapping buckets into connected components can chain unrelated items into one false equivalence group. Requiring instead a selection with at most one vertex per bucket respects only the local evidence and avoids spurious over-merging; this paper provides bounds and a greedy algorithm for that selection problem.
Does the paper include experiments or code?
No. This manuscript is purely theoretical. Large-scale results (ClueWeb22 with 1.62B and HPLT with 3.98B documents, where the greedy solver reportedly stays within about 0.6% of the puncturing upper bound) are deferred to a separate companion manuscript that is itself still being prepared for submission, and no code is released with this paper.
Does the greedy clustering algorithm have an approximation guarantee?
No worst-case ratio is proven. The paper proves the output is always feasible and maximal, gives an upper bound derived from the greedy's own layer-by-layer removal chronology via matchings, and identifies explicit structural conditions under which the greedy output is exactly optimal; proving approximation guarantees is explicitly listed as future work.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Review is based on extracted text; math notation and Table 1 are partially garbled by extraction, but all sections, theorems, proofs, and references appear present, so coverage is near-complete.
- Companion manuscript [7] containing all empirical results was not available; its claims are taken at face value from the abstract and introduction.
- No figures were analyzable from the extracted text; any figures in the published version were not reviewed.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.