A note on the computational complexity of weak saturation

Abstract

We prove that determining the weak saturation number of a host graph $F$ with respect to a pattern graph $H$ is already a computationally hard problem when $H$ is the triangle. As our main tool we establish a connection between weak saturation and shellability of simplicial complexes.