Convexidade Cíclica em Grafos

Abstract

Convexidades em grafos são inspiradas no conceito de mesmo nome em geometria mas adaptadas para esse contexto. Diferentes definições do que constitui um conjunto convexo já foram estudadas, entre as mais conhecidas estão aquelas definidas sobre caminhos, como as convexidades P₃ [3] e geodética [4]. Além do interesse teórico, processos como a propagação de informações ou epidemias podem ser modelados por conceitos de convexidade em grafos – estruturas que capturam regras de influência em redes sociais complexas. Nesses contextos, as regras de propagação estão diretamente relacionadas com uma definição de uma convexidade em grafos e o objeto de estudo se torna a função de intervalo da convexidade, que é o conceito análogo à combinação convexa, da geometria. Neste trabalho, abordamos a convexidade cíclica, inicialmente motivada por aplicações em teoria dos nós [2]. Formalmente, dado um grafo G e um subconjunto S ⊆ V(G), a função de intervalo infecta v ∉ S se existe um ciclo em G[S ∪ {v}]. Alguns aspectos dessa convexidade já foram estudados, com resultados recentes sobre seus números de intervalo [1] e de convexidade [6]. Nosso objetivo é responder uma terceira questão de interesse na área de convexidade em grafos para a convexidade cíclica, que chamamos de Partição em Conjuntos Convexos Cíclicos (PCCC): dado um grafo G e um inteiro k, é possível particionar G em exatamente k conjuntos convexos? Este problema já foi considerado em diversas outras convexidades. Uma breve revisão da literatura, bem como resultados recentes podem ser encontrados em [5]. O principal resultado deste trabalho é o teorema a seguir. Teorema 1. O problema PCCC é NP-completo mesmo se k = 2. A demonstração é baseada em uma redução do problema 2-in-3-SAT, uma variação conhecida do problema 3-SAT. Nela, exatamente dois literais devem ser verdadeiros em cada cláusula para a instância ser satisfeita. Na redução feita, foram utilizados dois gadgets principais, que podem ser visualizados nas Figuras 1, ??, e ??. Intuitivamente, queremos que cada cópia esteja sempre particionada em dois conjuntos; para os gadgets de literais, isso se traduz em uma atribuição que torna o literal correspondente verdadeiro ou falso; para isso adicionamos arestas entre gadgets oriundos de literais de uma mesma variável para forçar que as partições sejam globalmente coerentes. O ponto chave da prova é a introdução de um ciclo c_i,1, x_i,1, x_i,2, c_i,2, y_i,1, y_i,2, c_i,3, z_i,1, z_i,2 para cada cláusula i que contém as variáveis x, y, z. Intuitivamente, se dois dos literais não são verdadeiros, isso deve forçar que o conjunto {c_i,1, c_i,2, c_i,3} seja subconjunto de um dois conjuntos convexos e que o gadget da cláusula C_i também está no mesmo conjunto. Com a adição das arestas adequadas, isso implicaria que o grafo não foi particionado. Com o Teorema 1, podemos generalizar nosso resultado para todo k ≥ 2. Formalizamos esse resultado no Teorema 2. Teorema 2. Para qualquer k ≥ 2 fixo, o problema PCCC é NP-completo. A prova do Teorema 2 é feita por indução, tendo como caso base k = 2. Para o passo indutivo, a partir de uma instância H, construímos uma instância H’ da seguinte maneira. Seja V(H) = {v₁, v₂, ..., v_n} temos que V(H’) = V(H) ∪ {u₁, u₂, ..., u_n} e E(H’) = E(H) ∪ {v_iu_i | i ∈ [n]}. A partir dessa construção, é possível provar que H’ possui uma partição em k conjuntos convexos se, e somente se H possui uma partição em k − 1 conjuntos convexos. Além desses resultados de NP-completude, encontram-se em desenvolvimento algoritmos polinomiais para casos particulares onde o grafo de entrada pertence a determinadas classes de grafos, como grafos cordais e disco unitários. [...]