Pith. sign in

REVIEW 5 minor 38 references

The Complexity of Weak Saturation for Complete Graphs and Balanced Complete Bipartite Graphs

T0 review · 0 major / 5 minor · reviewed 2026-07-13 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Deciding whether the weak saturation number of a graph for Kr or Kr,r is at most k is NP-complete for every fixed r ≥ 3.

desk verdict Solid NP-completeness lift from triangles to all Kr and Kr,r via clean new combinatorial gadgets and standard topology; the proofs hold. read the letter →

arxiv 2607.04185 v2 pith:GZAQHS4Y submitted 2026-07-05 math.CO

Yihan Chen , Tianying Xie This is my paper
classification math.CO MSC 05C8505C3568Q17
keywords weaksaturationNP-completecompletegraphsbalancedbipartiteflag-no-square3-cleancollapsibilitygraphalgorithms
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves that, for every fixed integer r at least 3, the problem of deciding whether the weak saturation number of an input graph F with respect to the complete graph Kr, or with respect to the balanced complete bipartite graph Kr,r, is at most a given integer k, is NP-complete. Weak saturation asks for the fewest edges in a spanning subgraph of F from which the remaining edges of F can be added one by one so that each new edge completes a fresh copy of the target. Hardness is obtained by polynomial reductions that start from the already-hard triangle case, lift it to larger cliques by successive joins with universal vertices, and lift it to balanced bipartite targets by an auxiliary bipartite graph whose K3,3 copies are forced to come from triangles. The forcing step relies on a topological subdivision that produces flag-no-square complexes, whose 1-skeletons satisfy a new combinatorial property called 3-clean. A reader who cares about extremal graph theory learns that even for the most classical targets the exact weak-saturation threshold is computationally intractable, and that a classical topological property can control combinatorial saturation numbers.

What carries the argument

The 3-clean property (every pair of triples whose complete bipartite product appears in the closed neighborhood graph must be identical and induce a triangle) together with special subdivisions that produce flag-no-square 2-complexes. These guarantee that every K3,3 in the auxiliary bipartite graph B(G) arises from a unique triangle of G, yielding the exact identity wsat(B(G), K3,3) = n + m + wsat(G, K3). Iterated cone joins and balanced liftings then raise the target from K3 to Kr and from K3,3 to Kr,r.

What would settle it

Produce either a flag-no-square 2-complex whose 1-skeleton is not 3-clean, or a concrete 3-clean graph G for which wsat(B(G), K3,3) differs from |V(G)| + |E(G)| + wsat(G, K3). Either counter-example collapses the K3,3 reduction and therefore the hardness claims for all larger Kr,r.

Watch

Extended reading notes

Core claim

For every fixed integer r ≥ 3 and every target H belonging to {Kr, Kr,r}, the decision problem that takes a finite graph F and an integer k and asks whether wsat(F, H) ≤ k is NP-complete. Membership in NP follows by guessing a small initial edge set together with an addition order and verifying each step in polynomial time; NP-hardness is proved by explicit polynomial-time reductions from the known hard problem of deciding whether wsat(F, K3) equals the number of vertices minus one.

Load-bearing premise

The special subdivision of the input complex must stay free of induced 4-cycles and force every complete triple product of neighborhoods to come from a single triangle; if that fails, the exact link between bipartite and triangle weak-saturation numbers breaks.

Editorial extensions

If this is right

  • No polynomial-time algorithm exists for computing wsat(F, Kr) or wsat(F, Kr,r) unless P = NP, for every fixed r ≥ 3.
  • Hardness already holds on the explicit infinite family of host graphs produced by the reductions from 3-SAT.
  • Flag-no-square 2-complexes force their 1-skeletons to be 3-clean, giving a topological certificate that controls bipartite weak-saturation numbers.
  • The same technique does not decide the complexity of weak saturation for C4 or for unbalanced complete bipartite graphs Ks,t with s ≠ t.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Analogous “clean” combinatorial properties may allow hardness lifts to other highly symmetric targets such as complete multipartite graphs once a matching topological subdivision is available.
  • Collapsibility and shellability of flag complexes may continue to classify the complexity of weak saturation for further patterns beyond cliques and balanced bipartite graphs.
  • Any future polynomial algorithm for unbalanced Ks,t would have to exploit the asymmetry of part sizes that the present balanced lifting deliberately avoids.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper proves that for every fixed r≥3 and H∈{K_r,K_{r,r}}, the decision problem of whether wsat(F,H)≤k (given F and k) is NP-complete. Starting from the Tancer–Tyomkyn NP-hardness of deciding wsat(F,K_3)=n-1, the authors give polynomial reductions: iterative cone joins for cliques (Lemma 3.1), and for balanced bipartite graphs an auxiliary bipartite graph B(G) together with a 3-clean property that forces every K_{3,3} to arise from a unique triangle (Lemma 4.3). The 3-clean property is obtained by applying the special subdivision of Przytycki–Świątkowski to the Tancer–Tyomkyn complex, which yields a flag-no-square complex whose 1-skeleton is 3-clean (Lemmas 4.8–4.9). Collapsibility is preserved under subdivision (Lemmas 4.10–4.11), and a balanced lifting lemma (Lemma 4.12) extends the K_{3,3} case to all K_{r,r}. Membership in NP is elementary (Observation 2.8).

Significance. The result cleanly extends the only previously known hardness result for weak saturation (the triangle case of Tancer–Tyomkyn) to all complete graphs and all balanced complete bipartite graphs. The technical contribution is substantial: the introduction of the 3-clean property, the mixed-peeling formalism, and especially the importation of the flag-no-square property from geometric topology into extremal graph theory supply new tools that are likely to be reusable. All reductions are fully explicit, parameter-free, and polynomial-time; the key identities are proved in detail rather than sketched. The concluding discussion of the obstacles for C_4 and unbalanced K_{s,t} is honest and useful.

minor comments (5)
  1. Throughout: several typographical slips ("promblem" in §2.2, "This constructiongivesavalidmixed" in the proof of Lemma 4.3, missing spaces after periods). A careful copy-edit would remove them.
  2. Lemma 4.5 (mixed peeling): the induction is correct but the base case when F is H-free is only mentioned in one sentence; a one-line expansion would improve readability.
  3. Lemma 4.11: the Euler-characteristic bookkeeping (χ(T)=1+s-r) is sound, yet the argument that r≤s is slightly terse; an explicit sentence that every face of R contributes at least one face of S would help.
  4. Figure 1 (Z_10) is helpful; a short caption sentence identifying the three true vertices A,B,C would make the special-subdivision construction self-contained for readers unfamiliar with Dranishnikov’s complex.
  5. References: the arXiv numbers of the most recent related papers (e.g., Terekhov–Zhukovskii, Ascoli–He) could be updated to journal versions if they have appeared by the time of final revision.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: hardness reductions are parameter-free polynomial maps from an external NP-hard problem, with all equalities proved by direct combinatorial arguments.

full rationale

The central claim (Theorem 1.2) is obtained by polynomial-time reductions from the already-published external result of Tancer–Tyomkyn that deciding wsat(F,K3)=n-1 is NP-hard. The new constructions (iterated joins for cliques; the auxiliary bipartite graph B(G) together with special subdivision for balanced complete bipartite graphs) are explicit and parameter-free. All load-bearing identities—Lemma 3.1 (clique lifting), Lemma 4.3 (wsat(B(G),K3,3)=n+m+wsat(G,K3) for 3-clean G), Lemma 4.12 (balanced lifting), and the collapsibility-preservation lemmas—are proved by direct case analysis, mixed-peeling arguments and elementary topological facts; none is obtained by redefining the target quantity in terms of itself or by fitting parameters. The flag-no-square property is imported from the independent external source Przytycki–Świątkowski and then verified to imply the 3-clean property by a short combinatorial argument (Lemma 4.9). No self-citation is load-bearing, no uniqueness theorem of the present authors is invoked, and no empirical fit is renamed as a prediction. The derivation chain is therefore self-contained against the external hardness benchmark.

Assumptions & free parameters 0 free parameters · 4 assumptions · 2 invented entities

The paper is pure discrete mathematics. It inherits standard graph-theoretic and topological notions, the NP-hardness of 3-SAT, and the Tancer–Tyomkyn complex; it introduces two new combinatorial predicates (3-clean, mixed peeling) whose only purpose is to make the reductions work. No free parameters or physical entities appear.

assumptions (4)
  • standard math 3-SAT is NP-complete
    Used as the source problem for every polynomial reduction (Sections 3 and 4).
  • domain assumption Tancer–Tyomkyn construction yields a flag 2-complex Lφ whose collapsibility after triangle deletion is equivalent to satisfiability of φ
    Theorem 2.7 / Theorem 1.1 of [36]; the entire hardness chain begins from this object.
  • domain assumption Special subdivision of any 2-complex is flag-no-square (Przytycki–Świątkowski)
    Lemma 4.8, cited from [32]; guarantees that the 1-skeleton is 3-clean.
  • standard math In dimension 2 every triangulated disk is endo-collapsible
    Fact 2.5, used to preserve collapsibility under subdivision (Lemma 4.11).
invented entities (2)
  • 3-clean graph
    purpose: Forces every K3,3 in the auxiliary bipartite graph B(G) to arise from a unique triangle of G, enabling the equality of weak-saturation numbers.
    Definition 4.2; purely combinatorial predicate introduced for the reduction; no independent external evidence required.
  • mixed H-peeling
    purpose: Allows vertex deletions as well as edge deletions while preserving the length of an optimal peeling sequence, used to bound λ K3,3(B(G)).
    Definition 4.4 and Observation 4.5; technical device internal to the proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Complexity of Weak Saturation for Complete Graphs and Balanced Complete Bipartite Graphs." pith.science (2026). https://pith.science/paper/GZAQHS4Y

@misc{pith2026260704185,
  author       = {Pith},
  title        = {Pith review of: The Complexity of Weak Saturation for Complete Graphs and Balanced Complete Bipartite Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GZAQHS4Y}},
  note         = {Machine review of arXiv:2607.04185}
}
abstract

For graphs $F$ and $H$, a spanning subgraph $G$ of $F$ is weakly $H$-saturated in $F$ if the edges in $E(F)\setminus E(G)$ can be added one at a time, each addition creating a new copy of $H$. Recently, Tancer and Tyomkyn proved that, given an $n$-vertex graph $F$, deciding whether $\mathrm{wsat}(F,K_3)=n-1$ is NP-hard. In this paper, we study the decision version of the weak saturation problem and show that, for every fixed integer $r\ge 3$, given a graph $F$ and an integer $k$, deciding whether $\mathrm{wsat}(F,H)\le k$ is NP-complete when $H\in\{K_r,K_{r,r}\}$. Our approach uses novel graph-theoretic and topological ideas and techniques, yielding new constructions that build on the construction of Tancer and Tyomkyn. In particular, our proofs bring the flag-no-square property, a fundamental property in topology that is of independent interest, into the study of weak saturation problem.

Figures

Figures reproduced from arXiv: 2607.04185 by the authors.

Figure 1
Figure 1. The picture of Z10, where A, B, C are the true vertices. The following definition of the special subdivision is the Definition 2.2 in [32]. Definition 4.7. The special subdivision of a 2-simplex ∆ is the subdivision isomorphic to Z10, where vertices of ∆ correspond to true vertices of Z10. We denote it by ∆∗ . For any 2-dimensional simplicial complex Y , the special subdivision Y ∗ is obtained by taking the first ba… view at source ↗

Review history (2 revisions) →

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

38 extracted references · 1 linked inside Pith

  1. [1]

    K. A. Adiprasito and B. Benedetti, A Cheeger-type exponential bound for the number of trian- gulated manifolds,Ann. Inst. Henri Poincaré D7(2)(2020), 233–247

    2020

  2. [2]

    Akhmejanova, I

    M. Akhmejanova, I. Vorobyev and M. Zhukovskii, Weak saturation numbers of large complete bipartite graphs, arXiv:2508.19435 (2025)

    arXiv 2025

  3. [3]

    Alon, An extremal problem for sets with applications to graph theory,J

    N. Alon, An extremal problem for sets with applications to graph theory,J. Comb. Theory Ser. A.40(1985), 82–89

    1985

  4. [4]

    Ascoli and X

    R. Ascoli and X. He, Rational values of the weak saturation limit, arXiv:2501.15686 (2025)

    arXiv 2025

  5. [5]

    Avramidi, B

    G. Avramidi, B. Okun, K. Schreve, Homology growth, hyperbolization, and fibering,Geom. Funct. Anal.34(2)(2024), 303-376. 14

    2024

  6. [6]

    Balogh, B

    J. Balogh, B. Bollobás, R. Morris and O. Riordan, Linear algebra and bootstrap percolation,J. Combin. Theory Ser. A.119(6)(2012), 1328–1335

    2012

  7. [7]

    B.Bollobás, Weaklyk-saturatedgraphs, inBeiträge zur Graphentheorie, Teubner, Leipzig, (1968), 25–31

    1968

  8. [8]

    Borowiecki and E

    M. Borowiecki and E. Sidorowicz, WeaklyP-saturated graphs,Discuss. Math. Graph Theory. 22(1)(2002), 17–29

    2002

Show all 38 references
  1. [9]

    Bulavka, M

    D. Bulavka, M. Tancer and M. Tyomkyn, Weak saturation of multipartite hypergraphs,Combi- natorica43(6)(2023), 1081–1102

    2023

  2. [10]

    C. H. Cashen, P. Dani, K. Schreve and E. Stark, Conformal dimension bounds, Pontryagin sphere boundaries, and algebraic fibering of right-angled Coxeter groups, arXiv:2510.03430 (2025)

    2025

  3. [11]

    B. L. Currie, J. R. Faudree, R. J. Faudree, and J. R. Schmitt, A survey of minimum saturated graphs,Electron. J. Combin.DS19, Dynamic Surveys, (2021), 98 pp

    2021

  4. [12]

    Constantinescu, T

    A. Constantinescu, T. Kahle and M. Varbaro, Linear syzygies, flag complexes, and regularity, Collect. Math.67(3)(2016), 357–362

    2016

  5. [13]

    Constantinescu, T

    A. Constantinescu, T. Kahle and M. Varbaro, Linear syzygies, hyperbolic Coxeter groups and regularity,Compos. Math.155(6)(2019), 1076–1097

    2019

  6. [14]

    Douba, G.-S

    S. Douba, G.-S. Lee, L. Marquis and L. Ruffoni, Convex cocompact groups with three-dimensional limit sets, arXiv:2604.00466 (2026)

    2026

  7. [15]

    A. N. Dranishnikov, Boundaries of Coxeter groups and simplicial complexes with given links,J. Pure Appl. Algebra137(2)(1999), 139–151

    1999

  8. [16]

    R. J. Faudree and R. J. Gould, Weak saturation numbers for multiple copies,Discrete Math.336 (2014), 1–6

    2014

  9. [17]

    R. J. Faudree, R. J. Gould and M. S. Jacobson, Weak saturation numbers for sparse graphs, Discuss. Math. Graph Theory.33(4)(2013), 677–693

    2013

  10. [18]

    Frankl, An extremal problem for two families of sets,European J

    P. Frankl, An extremal problem for two families of sets,European J. Combin.3(1982), 125–127

    1982

  11. [19]

    Gromov, Hyperbolic groups, inEssays in Group Theory(S

    M. Gromov, Hyperbolic groups, inEssays in Group Theory(S. M. Gersten, ed.), Math. Sci. Res. Inst. Publ.8, Springer-Verlag, New York, 1987, 75–263

    1987

  12. [20]

    Januszkiewicz and J

    T. Januszkiewicz and J. Świątkowski, Simplicial nonpositive curvature,Publ. Math. Inst. Hautes ’Etudes Sci.104(2006), 1–85

    2006

  13. [21]

    Kalai, Weakly saturated graphs are rigid,North-Holl

    G. Kalai, Weakly saturated graphs are rigid,North-Holl. Math. Stub.87(1984), 189–190

    1984

  14. [22]

    Kalmanovich, E

    D. Kalmanovich, E. Nevo and G. Sorcar, On flag-no-square 4-manifolds,Discrete Comput. Geom. (2025), 1-15

    2025

  15. [23]

    S. H. Kim and G. S. Walsh, Coxeter groups, hyperbolic cubes and acute triangulations,J. Topol. 9(1)(2016), 117–142. 15

    2016

  16. [24]

    Kopczyński, I

    E. Kopczyński, I. Pak and P. Przytycki, Acute triangulations of polyhedra andRn,Combinatorica 32(1)(2012), 85–110

    2012

  17. [25]

    Kronenberg, T

    G. Kronenberg, T. Martins and N. Morrison, Weak saturation numbers of complete bipartite graphs in the clique,J. Combin. Theory Ser. A178(2021), 105357

    2021

  18. [26]

    Lovász, Flats in matroids and geometric graphs, inCombinatorial Surveys, North-Holland, 1977, 45–86

    L. Lovász, Flats in matroids and geometric graphs, inCombinatorial Surveys, North-Holland, 1977, 45–86

    1977

  19. [27]

    Miralaei, A

    M. Miralaei, A. Mohammadian and B. Tayfeh-Rezaie, The weak saturation number ofK 2,t, Discrete Math.347(9)(2024), 114078

    2024

  20. [28]

    Morrison, J

    N. Morrison, J. A. Noel and A. Scott, Saturation in the hypercube and bootstrap percolation, Combin. Probab. Comput.26(1)(2017), 78–98

    2017

  21. [29]

    Moshkovitz and A

    G. Moshkovitz and A. Shapira, Exact bounds for some hypergraph saturation problems,J. Combin. Theory Ser. B111(2015), 242–248

    2015

  22. [30]

    J. R. Munkres,Elements of Algebraic Topology, Addison-Wesley, 1984

    1984

  23. [31]

    Osajda, A construction of hyperbolic Coxeter groups,Comment

    D. Osajda, A construction of hyperbolic Coxeter groups,Comment. Math. Helv.88(2)(2013), 353–367

    2013

  24. [32]

    Przytycki and J

    P. Przytycki and J. Świątkowski, Flag-no-square triangulations and Gromov boundaries in di- mension 3,Groups Geom. Dyn.3(3)(2009), 453–468

    2009

  25. [33]

    C. P. Rourke and B. J. Sanderson,Introduction to Piecewise-Linear Topology, Springer-Verlag, 1982 reprint

    1982

  26. [34]

    Shapira and M

    A. Shapira and M. Tyomkyn, Weakly saturated hypergraphs and a conjecture of Tuza,Proc. Amer. Math. Soc.151(07)(2023), 2795–2805

    2023

  27. [35]

    Skotnica and M

    M. Skotnica and M. Tancer, NP-Hardness of Computing PL Geometric Category in Dimension 2,SIAM J. Discrete Math.37(3)(2023), 2016–2029

    2023

  28. [36]

    Tancer and M

    M. Tancer and M. Tyomkyn, A note on the computational complexity of weak saturation,Com- binatorics, Probability and Computing.35(1)(2026), 83–88

    2026

  29. [37]

    N.TerekhovandM.Zhukovskii, Weaksaturationingraphs: acombinatorialapproach,J. Combin. Theory Ser. B172(2025), 146–167

    2025

  30. [38]

    Terekhov and M

    N. Terekhov and M. Zhukovskii, Weak saturation rank: a failure of linear algebraic approach to weak saturation,Combinatorica45(2025). 16

    2025

Pith tools

Reviewed July 13, 2026 · model on record in the stance chip above.