Dokładne algorytmy dla problemu pokrycia wierzchołkowego

Celem tej pracy jest implementacja i porównanie kilku algorytmów dla problemu pokrycia wierzchołkowego w grafach. Wiadomo, że jeżeli P jest różne od NP, problemu pokrycia wierzchołkowego nie można rozwiązać w czasie wielomianowym. Zaimplementowane przez nas algorytmy są algorytmami dokładnymi i działają w czasie wykładniczym lub są w klasie FPT przy tzw. parametryzacji powyżej progu gwarantowanego. Okazuje się, że algorytmy takie i ich modyfikacje, w pewnych podklasach grafów, są bardzo wydajne.

We implement and compare algorithms for the Vertex Cover problem. It is known that Vertex Cover is NP-complete, and thus, assuming P not equal to NP, it does not admit a polynomial-time algorithm. The algorithms considered in this paper are exact and work in exponential time. Two of them are fixed-parameter tractable for the above guarantee parameterization of the Vertex Cover problem.