TRATABILIDADE POR PARÂMETRO FIXO DE PROBLEMAS COM RESTRIÇÕES DISJUNTIVAS

Resumo

Um problema parametrizado é um problema de decisão com instâncias do tipo (x, k) com k natural. Um problema parametrizado é tratável por parâmetro fixo (FPT) se existe uma constante c, uma função computável f:N→R e um algoritmo que resolve o problema em tempo f(k)|x|ᶜ para todos x e k. Esse algoritmo também é dito FPT. Estudamos a tratabilidade por parâmetro fixo de problemas clássicos de teoria dos grafos quando sujeitos a restrições disjuntivas positivas e negativas. Restrições disjuntivas positivas, ou restrições de forçamento, determinam que pelo menos um elemento de certos pares de elementos deve estar presente em qualquer solução viável. As restrições disjuntivas negativas, por sua vez, impedem que ambos os elementos de certos pares de elementos estejam presentes simultaneamente em soluções viáveis e, por isso, também as chamamos de restrições de conflito. Representamos essas restrições por um grafo simples, chamado de grafo de forçamento ou grafo de conflito, de acordo com o tipo de restrição. Diversos problemas polinomiais se tornam NP-Difíceis quando adicionam-se essas restrições, como é o caso do problema da árvore geradora mínima e do emparelhamento máximo. Descrevemos um algoritmo parametrizado, baseado na estratégia clássica de bounded search tree, que resolve problemas parametrizados pelo tamanho da solução e sujeitos a restrições de forçamento. Mostramos que ele é FPT desde que seja possível estender uma solução parcial em tempo polinomial em x e k. Já no caso de restrições de conflito, alguns dos problemas estudados, como o problema do emparelhamento, tornam-se W-hard e, portanto, não é esperado que exista algoritmo FPT que os resolvam. Entretanto, mostramos que o problema do u,v-caminho parametrizado pelo tamanho da solução é FPT mesmo com restrições de conflito.