Complexity of some parameters in the convexity of cycles

• Carlos V. G. C. Lima UFCA
• Thiago Marcilon UFCA
• Pedro Paulo de Medeiros UFC

DOI: https://doi.org/10.5753/etc.2024.2281

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, whose interval function is I(S) = S ∪ {u | G[S ∪ {u}] has a cycle containing u}. In this convexity, we prove that the decision problems associated to the parameters rank and convexity number are in NP-complete and W[1]-hard when parameterized by the solution size. We also prove that to determine whether the percolation time of a graph is at least k is NP-complete, but polynomial for cacti or when k ≤ 2.

References

Araujo, J., Ducoffe, G., Nisse, N., and Suchan, K. (2018). On interval number in cycle convexity. Discret. Math. Theor. Comput. Sci., 20(1):1–28.

Benevides, F., Campos, V., Dourado, M. C., Sampaio, R. M., and Silva, A. (2015). The maximum time of 2-neighbour bootstrap percolation: Algorithmic aspects. European Journal of Combinatorics, 48:88–99.

Bollobás, B. and Riordan, O. (2006). Percolation. Cambridge University Press.

Chartrand, G. and Zhang, P. (1999). Convex sets in graphs. Congr. Numer., 136:19–32.

Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., and Pilipczuk, M. (2015). Parameterized Algorithms. Springer, 1st edition.

Dourado, M. C., Ponciano, V. S., and da Silva, R. L. O. (2022). On the monophonic rank of a graph. Discrete Mathematics & Theoretical Computer Science, vol. 24, no 2.

Farber, M. and Jamison, R. (1986). Convexity in graphs and hypergraphs. SIAM J. Algebraic Discrete Methods, 7:433–444.

Harary, F. and Nieminen, J. (1981). Convexity in graphs. J. Differ. Geom., 16(2):185–190.

Jaffke, L., Kwon, O., and Telle, J. (2020). Mim-width ii. the feedback vertex set problem. Algorithmica, 82:118–145.

Pelayo, I. (2013). Geodesic Convexity in Graphs. Springer.