The complexity of convexity number and percolation time in the cycle convexity
<|reference_start|>The complexity of convexity number and percolation time in the cycle convexity: 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 \geq 9$, but polynomial for cacti or for fixed $k\leq2$.<|reference_end|>
@article{lima2024the,
    title={The complexity of convexity number and percolation time in the cycle
  convexity},
    author={Carlos V.G.C. Lima, Thiago Marcilon and Pedro Paulo de Medeiros},
    journal={arXiv preprint arXiv:2404.09236},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.09236},
    primaryClass={cs.CC}
}