O Problema da k-Cobertura por Vértices: uma Implementação FPT no Modelo BSP/CGM

Abstract

Em muitas situacões práticas precisamos resolver problemas NP-completos com exatidão. A Complexidade Parametrizada é um método promissor para lidarmos com a intratabilidade de alguns problemas, principalmente aqueles cuja entrada pode ser dividida em uma parte principal e um parâmetro. A parte principal da entrada contribui polinomialmente na complexidade total do problema, enquanto a aparentemente inevitável explosão combinatorial fica confinada ao parâmetro. Neste trabalho estudamos a teoria sobre Complexidade Parametrizada e o algoritmo FPT paralelo de Cheetham et al. no modelo BSP/CGM para o problema da k-Cobertura por Vértices, e nossa contribuição é apresentar uma implementação refinada e melhorada de tal algoritmo. A escolha de boas estruturas de dados e o uso da técnica de backtracking em nossa implementação foram fundamentais para que obtivessemos tempos paralelos melhores em nossos experimentos. Utilizamos cinco grafos de conflitos referentes a aminoácidos, os mesmos usados por Cheetham et al. em seus experimentos. Mesmo utilizando um ambiente computacional inferior ao usado por Cheetham et al., para dois desses grafos obtivemos tempos aproximadamente 115 vezes melhores, para um deles 16 vezes melhor e, para os grafos restantes obtivemos tempos um pouco melhores. Além disso, para três desses grafos obtivemos coberturas por vértice de tamanho menor.