ESTUDO DA COMPLEXIDADE E APROXIMABILIDADE DO PROBLEMA DE MÁXIMO SUBGRAFO ACÍCLICO SUJEITO A RESTRIÇÕES DE CONFLITO OU FORÇAMENTO

XXXVII Encontro de Iniciação Científica

Leonardo Cavalcante de Abreu, FELIPE ALBUQUERQUE, Manoel Bezerra Campelo Neto

Dado um grafo direcionado G = (V,A) e um grafo não direcionado Ĝ = (A,E), denominado grafo de restrições - cujos vértices são os arcos de G -, o problema do máximo subgrafo acíclico com restrições de conflito (MSARC) consiste em encontrar um subconjunto A&#039; contido em A de máxima cardinalidade tal que G&#039; = (V,A&#039;) seja acíclico e A&#039; seja conjunto independente em Ĝ. O problema do máximo subgrafo acíclico com restrições de forçamento (MSARF), por sua vez, consiste em determinar o um subconjunto A&#039; contido em A de máxima cardinalidade tal que G&#039; = (V,A&#039;) seja acíclico e A&#039; seja uma cobertura de vértices em Ĝ. Ambos fazem parte de um conjunto de versões sob restrições disjuntivas de problemas clássicos em grafos, muitos dos quais são polinomiais na sua forma padrão, mas tornam-se NP-Difíceis ao se acrescentarem as restrições de conflito ou forçamento. Determinar o máximo subgrafo acíclico, contudo, é NP-Difícil mesmo na forma padrão. Dessa forma, o MSARC é um problema de otimização classificado como NP-Difícil, e a literatura apresenta 3 algoritmos 1/2-aproximativos para ele. Não foi encontrado, entretanto, algoritmo mais eficiente que esses até então, e pouco se sabe sobre a possibilidade de existência de tais algoritmos. Já o MSARF nem mesmo possui garantia de existência de uma solução viável. De fato, verificar a existência de uma é um problema da classe NP-Completo. Neste trabalho, estudamos todos esses resultados como base para o desenvolvimento e implementação de novas heurísticas bem como de algoritmos com maior fator de aproximabilidade para o MSARC em subclasses de grafos.

Palavras-chave: máximo subgrafo acíclico. restrições disjuntivas. minimum feedback arc set. algoritmos aproximativos.

Encontros Universitários da UFC, Fortaleza, v. 3, 2018

1373