ESTUDO DA COMPLEXIDADE E APROXIMABILIDADE DO PROBLEMA DE MÁXIMO SUBGRAFO ACÍCLICO SUJEITO A RESTRIÇÕES DE CONFLITO OU FORÇAMENTO
Resumo
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' contido em A de máxima cardinalidade tal que G' = (V,A') seja acíclico e A' 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' contido em A de máxima cardinalidade tal que G' = (V,A') seja acíclico e A' 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.Publicado
2019-01-14
Edição
Seção
XXXVII Encontro de Iniciação Científica
Licença
Autores que publicam nesta revista concordam com os seguintes termos:
a. Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Creative Commons Attribution License que permitindo o compartilhamento do trabalho com reconhecimento da autoria do trabalho e publicação inicial nesta revista.
b. Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
c. Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado.