PROBLEMA DO SUBGRAFO ACÍCLICO MÁXIMO SOB RESTRIÇÕES DE CONFLITO EM GRAFOS DE GRAU LIMITADO

Abstract

O problema do subgrafo acíclico máximo sob restrições de conflito (MASNDC) consiste em, dados um grafo direcionado D=(V,A) e um grafo de conflitos G=(A,E), encontrar um subconjunto A' de A de cardinalidade máxima tal que o subgrafo induzido por A' em D seja acíclico e A' seja conjunto independente em G. Esse problema generaliza os problemas do subgrafo acíclico máximo (caso E seja vazio) e do conjunto independente máximo (caso D seja acíclico). Estudamos a complexidade e aproximabilidade do problema limitando o grau máximo dos grafos de entrada, tanto do digrafo quanto do grafo de conflitos. Conseguimos caracterizar uma dicotomia entre casos polinomiais e NP-Difíceis do problema, em função dos graus máximos de D e G. Mostramos que o MASNDC é NP-Difícil se o mínimo entre o grau máximo de D e o de G é pelo menos 2 (min{∆(D),∆(G)}≥2) ou o máximo entre os graus máximos e D e G é pelo menos 3 (max{∆(D),∆(G)}≥3), e que é polinomial caso contrário. Para isso, apresentamos uma redução do problema 3-SAT para a versão de decisão do MASNDC que mostra o caso NP-Difícil e um algoritmo polinomial que resolve o caso complementar. Adicionalmente, desenvolvemos algoritmo aproximativo para o caso geral do problema, estendendo resultados de Mapa e Urrutia (2015), que consideram o caso particular onde o conjunto independente máximo de G pode ser determinado em tempo polinomial. Apresentamos, portanto, um algoritmo (2.5/(3+∆(G)))-aproximativo para o MASNDC.