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

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

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

Таким образом, кернелизация обеспечивает эффективную предварительную подготовку для решения задачи о вершинном покрытии, которая позволяет работать с графами меньшего размера (т.е. с графами, размер которых зависит только от k).