Implementações alternativas FPT BSP/CGM para o problema k-Cobertura por Vértices

Abstract

Muitas das aplicações do mundo real requerem soluções para problemas NP-Completos. A inexistência de algoritmos polinomiais conhecidos para resolvê-los resulta na grande variedade de propostas de soluções. Estas soluções utilizam principalmente heurísticas e algoritmos de aproximação. Uma abordagem alternativa é a utilização de algoritmos FPT (Fixed Parameter Tractability). Enquanto as técnicas baseadas em heurísticas e em algoritmos de aproximação relaxam a busca por soluções ótimas ou exatas, mas usualmente insistem em algoritmos de tempo polinomial, as técnicas que utilizam algoritmos FPT sempre encontram resultados exatos, mas podem apresentar soluções eficientes na teoria, embora inviáveis na prática. Para controlar o tempo de processamento, os algoritmos FPT possuem um parâmetro k associado à instânica do problema que resolvem. Neste sentido, pequenos valores configurados no parâmetro k produzem soluções polinomiais. Mas, como nem sempre, pequenos valores no parâmetro são suficientes para suprir a real necessidade de um problema, estratégias como utilizar o paralelismo tem sido pesquisadas com objetivo de melhorar tanto o tempo de resposta quanto ao tamanho da instânica do problema que pode ser resolvida. Neste trabalho, estaremos interessados na pesquisa de algoritmosFPT e na implementação eficiente destes algoritmos utilizando o poder do paralelismo no modelo BSP/CGM para diferentes abordagens do problema NP-Completo k-Cobertura por Vértices (k-Vertex Cover).