Particularidades do Problema de Partição na Convexidade P3 em Grafos com Treewidth Limitada
Resumo
Neste trabalho, apresentamos um algoritmo que resolve o problema de partição na convexidade P3 quando restrito a grafos com treewidth limitada. Dados um grafo G = (V;E) e X ⊆ V , dizemos que X é um conjunto p3-convexo se todo vértice com pelo menos dois vizinhos em X também pertence a X. A coleção de todos os subconjuntos p3-convexos de V constitui a convexidade P3 em G. O problema da p-partição na convexidade P3 consiste em particionar V em p conjuntos p3-convexos não-vazios e mutualmente disjuntos, para um inteiro p ≥ 2. Apesar da NP-completude mesmo para grafos split, mostramos que o problema é resolvido em tempo linear para grafos com treewidth e o número p limitados.
Palavras-chave:
árvore de decomposição, treewidth, Convexidade P3
Referências
Centeno, C. C., Dantas, S., Dourado, M. C., Rautenbach, D., e Szwarcfiter, J. L. (2010). Convex Partitions of Graphs induced by Paths of Order Three. Discrete Mathematics and Theoretical Computer Science, 12(5):175–184.
Centeno, C. C., Dourado, M. C., e Szwarcfiter, J. L. (2009). On the convexity of paths of length two in undirected graphs. Electronic Notes in Discrete Mathematics, 32:11 –18. DIMAP Workshop on Algorithmic Graph Theory.
Courcelle, B. (1990). The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Inf. Comput., 85(1):12–75.
Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., e Saurabh, S. (2015). Parameterized Algorithms. Springer Publishing Company, Incorporated, 1st edition.
Fiala, J., Golovach, P. A., e Kratochvíl, J. (2011). Parameterized complexity of coloring problems: Treewidth versus vertex cover. Theoretical Computer Science, 412(23):2513 – 2523.
Centeno, C. C., Dourado, M. C., e Szwarcfiter, J. L. (2009). On the convexity of paths of length two in undirected graphs. Electronic Notes in Discrete Mathematics, 32:11 –18. DIMAP Workshop on Algorithmic Graph Theory.
Courcelle, B. (1990). The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Inf. Comput., 85(1):12–75.
Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., e Saurabh, S. (2015). Parameterized Algorithms. Springer Publishing Company, Incorporated, 1st edition.
Fiala, J., Golovach, P. A., e Kratochvíl, J. (2011). Parameterized complexity of coloring problems: Treewidth versus vertex cover. Theoretical Computer Science, 412(23):2513 – 2523.
Publicado
30/06/2020
Como Citar
DE CASTRO, Lorrana F.; DE OLIVEIRA, Rodolfo A.; PROTTI, Fábio.
Particularidades do Problema de Partição na Convexidade P3 em Grafos com Treewidth Limitada. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 5. , 2020, Cuiabá.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2020
.
p. 25-28.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2020.11081.
