The complexity of convexity number and percolation time in the cycle convexity

Abstract

The subject of graph convexity is well explored in the literature, the so-called interval convexities above all. In this work, we explore the cycle convexity, an interval convexity whose interval function is $I(S)=S\cup \{u\mid G[S\cup \{u\}]$ has a cycle containing $u\}$. In this convexity, we prove that determine whether the convexity number of a graph $G$ is at least $k$ is \NP-complete and \W[1]-hard when parameterized by the size of the solution when $G$ is a thick spider, but polynomial when $G$ is an extended $P_4$-laden graph. We also prove that determining whether the percolation time of a graph is at least $k$ is \NP-complete even for fixed $k\ge 9$, but polynomial for cacti or for fixed $k\le 2$.