{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-05","reactions":{}}