Остовное дерево с максимальным количеством листьев

Ключевые слова и синонимы

Связное доминирующее множество; экстремальная структура

Постановка задачи

Задача построения максимального листового остовного дерева (МЛОД) заключается в нахождении остовного дерева, имеющего не менее k листьев, на неориентированном графе. Версия с принятием решений параметризованной задачи построения МЛОД выглядит следующим образом:

Дано: связный граф G, целое число k.

Параметр: целое число k.

Вопрос: имеет ли граф G с не менее чем k листьями?

Параметризованная сложность недетерминированного алгоритма МЛОД с полиномиальным временем выполнения широко изучалась [2, 3, 9, 11] с использованием кернелизации, ветвления и других техник с фиксированными параметрами (fixed-parameter tractable, FPT). Авторы работы [8] первыми предложили метод экстремальной структуры для решения сложных вычислительных задач. Этот метод, напоминающий подход Гротендика и по духу сходный с проектом миноров графов Робертсона и Сеймура, заключается в том, что математический проект должен представлять собой серию небольших шагов, выполняемых по общей траектории, описываемой подходящей «математической машиной». Авторы подхода предпочитают высказывания следующего типа: Каждый связный граф с n вершинами, удовлетворяющий определенному набору свойств, имеет остовное дерево с не менее чем k листьями, и это остовное дерево можно найти за время O(f(k) + nc), где c – константа (независимая от k), а / - произвольная функция.

При рассмотрении параметризованной сложности значение k называется параметром, который в определенном смысле отражает структуру входных данных или другой аспект цели вычисления. Например, k может обозначать количество ребер, которые необходимо удалить для получения графа без циклов; количество последовательностей ДНК, подлежащих выравниванию в задаче выравнивания последовательностей; максимальную глубину вложенности объявления типа у компилятора; k = 1/e может обозначать параметризаций при анализе аппроксимации; кроме того, k также может быть составным значением, зависящим от нескольких переменных.

Существуют два основных способа сравнения FPT-алгоритмов, в результате чего появилось два класса FPT-задач. В классе «f(k)» задача заключается в поиске еще более медленно растущих функций от параметра f(k), управляющих сложностью FPT-алгоритмов. Класс «кернелизации» опирается на следующую лемму, утверждающую, что задача принадлежит к разряду FPT в том и только том случае, если входные данные могут быть предварительно обработаны (кернелизованы) за «обычное» полиномиальное время до экземпляра, размер которого ограничивается только функцией от k.

Лемма 1. Параметризованная задача П является задачей с фиксированными параметрами (FPT) в том и только том случае, если существует преобразование с полиномиальным временем выполнения (относительно n и k), переводящее (x, k) и (x0 ; k0), такое, что: (1) (x, k) является «да-экземпляром» TI в том и только том случае, если (x0; k0) является «да-экземпляром» П, (2) k0 < k, (3) \x'\ < g(k) для некоторой фиксированной функции g.

В ситуации, описываемой леммой, можно сказать, что мы можем кернелизовать исходные экземпляры до экземпляров размером не более g(k). Два этих класса задач тесно связаны, однако результаты их выполнения различаются. Наилучший известный FPT-алгоритм задачи построения максимального листового остовного дерева с временем выполнения O*(8.12) предложил Бонсма [ ] на основе подхода на базе экстремальных структур, который разработали Эстивилл-Кастро, Феллоуз, Лэнгстон и Розамонд [8]. Этот алгоритм определяет, имеет ли граф G с n вершинами остовное дерево не менее чем с k листьями. В то же время авторы работы [8] представили FPT-алгоритм с наименьшим размером ядра.

Можно выделить пять независимых объектов, связанных с теорией экстремальных структур и иллюстрирующих все цели алгоритма построения максимального листового остовного дерева. Перечислим эти пять целей:

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

(б) Правила мощной предварительной обработки (редукции данных / кернелизации) и комбинации правил, которые могут использоваться независимо от того, насколько мал параметр, и могут комбинироваться с другими подходами – например, аппроксимацией и эвристиками. Обычно они несложны для программирования.

(в) Градиенты и правила преобразования для эвристик локального поиска.

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

(д) Структура, используемая для решения других задач.

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

Основным результатом является метод использования экстремальной структуры в качестве системного подхода к разработке FPT-алгоритмов. Рассмотрим пять перечисленных выше взаимосвязанных целей, проиллюстрировав каждую при помощи задачи.

Цель (а): FPT-алгоритмы

Задача заключается в нахождении правил предварительной обработки (кернелизации) с полиномиальным временем выполнения, где g(k) насколько возможно мало. Это будет важно впоследствии в контексте цели (б).

Рис. 1. Правила редукции были выведены для редукции данной структуры графа Клейтмана-Веста

Если перефразировать задачу в терминах структурной теории, важнейший вопрос будет звучать следующим образом: какова структура графов, не имеющих подграфа с k листьями? Результат Клейтмана и Веста из теории графов показывает, что граф с минимальной степенью не менее 3, не включающий подграф с k листьями, имеет не более 4(k - 3) вершин. На рис. 1 показано, что это лучший возможный результат для данной гипотезы. Однако исследование структуры при помощи экстремальных методов выявляет необходимость в применении правила редукции, показанного на рис. 2. Примерно 20 различных правил редукции с полиномиальнымвременем выполнения (некоторые из них являются намного более сложными и «глобальными» по своей структуре, чем приведенное для примера простое локальное правило редукции) будет достаточно для кернелизации графа с минимальной степенью 2, имеющего не более 3,5k вершин.

Рис. 2. Правило редукции для графа Клейтмана-Веста