Вершинное покрытие и деревья поиска: различия между версиями

Предположим, что (G, k) – экземпляр задачи о вершинном покрытии, где G – граф, а k – параметр. Операция кернелизации применяет к экземпляру (G, k) подпрограмму обработки с полиномиальным временем выполнения, которая строит еще один экземпляр (G’, k’), где G’ – граф меньшего размера (ядро), а k’ < k, такой, что G’ имеет вершинное покрытие из k’ вершин в том и только том случае, если G имеет вершинное покрытие из k вершин. В классической работе Немхаузера и Троттера [9] был получен следующий результат, относящийся к кернелизации.

Теорема 1. Существует алгоритм решения задачи о вершинном покрытии с временем выполнения O(kn + k3), который для экземпляра (G, k) строит еще один экземпляр задачи (G’, k’), где граф G’ содержит не более 2k’ вершин, а k’ < k, такой, что граф G имеет вершинное покрытие из k вершин в том и только том случае, если граф G’ имеет вершинное покрытие из k’ вершин.