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.

16 pages, 1 figure