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

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.

Disclosure

“eral Ks,t . Acknowledgement Tianying Xie was supported by National Key R and D Program of China 2023YFA1010201 and National Natural Science Foundation of China grants 12501474 and 12471336. Declaration on the use of AI The authors used generative AI tools to assist in discussing proof strategies, checking proofs, and improving the exposition. The authors take full responsibility for the mathematical arguments, results, and conclusions, all of which were carefully reviewed and verified”

PDF page 14

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-24T00:34:05.733Z

Structural counts