Параметризованные алгоритмы. Лекция 4

Метод итеративного сжатия. Демонстрация метода на примере вершинного покрытия. Задачи:

• Задача разрезание контуров в графах турнирах(Feedback Vertex Set in Tournaments) 2^kn^O(1).
• Задача разрезание контуров в произвольных неориентированных графах 5^kn^O(1).