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

Формальное определение задачи выглядит следующим образом. Пусть G – неориентированный граф. Подмножество C вершин графа G является [[вершинное покрытие|вершинным покрытием]] G, если хотя бы одна конечная точка каждого ребра G принадлежит к C. Пример (параметризованной) задачи о вершинном покрытии представляет собой пару (G, k), где G – граф, а k – целочисленный параметр; в задаче требуется определить, имеет ли граф G вершинное покрытие из k вершин. Наша цель заключается в разработке параметризованных алгоритмов с временем выполнения O(f(k)p(n)) для нахождения вершинного покрытия, где p(n) – полином более низкой степени от размера входного графа n, а f(k) – неполиномиальная часть, являющаяся функцией от параметра k и не зависящая от n. Ожидается, что неполиномиальная функция f(k) будет насколько возможно малой. Такой алгоритм будет эффективным на практике, если параметр k будет малым. Следует отметить, что за исключением редко встречающихся в теории сложности случаев функция f(k) является по меньшей мере экспоненциальной относительно параметра k [8].

== Основные результаты ==

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

== Свертка ==

Операция свертки позволяет уменьшить значение параметра k без применения ветвления. Такие операции оказались весьма эффективными для разработки экспоненциальных по времени алгоритмов решения задачи о вершинном покрытии. Недавно было предложено расширение операции свертки, допускающее применение к множеству из нескольких вершин графа [6].

== Ветвление и поиск ==

== Открытые вопросы ==