Id: arxiv/2607.04185 Url: https://arxiv.org/abs/2607.04185 Tags: math.CO Score: 0 Title: The Complexity of Weak Saturation for Complete Graphs and Balanced Complete Bipartite Graphs Domain: math.CO Source: arxiv Authors: Yihan Chen, Tianying Xie Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-05 Page: https://delphi.science/r/arxiv/2607.04185 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…