Complexidade de alguns parâmetros na convexidade de ciclos

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

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

Resumo

O conceito de convexidade em grafos é bastante explorado na literatura, principalmente as chamadas convexidades de intervalo. Neste trabalho, exploramos a convexidade de ciclos, cuja função de intervalo é I(S) = S∪{u | G[S ∪ {u}] possui um ciclo contendo u}. Nessa convexidade, provamos que os problemas de decisão atrelados aos parâmetros rank e número de convexidade são problemas NP-completos e W[1]-difíceis quando parametrizados pelo tamanho da solução. Provamos também que determinar se o tempo de percolação é pelo menos k é NP-completo, porém polinomial para cactos ou quando k ≤ 2.

Referências

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.