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

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

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

Лемма 1. Параметризованная задача <math>\Pi \;</math> является задачей с фиксированными параметрами (FPT) в том и только том случае, если существует преобразование с полиномиальным временем выполнения (относительно n и k), переводящее (x, k) в (x', k,), такое, что:

(1) (x, k) является «да-экземпляром» <math>\Pi \;</math> в том и только том случае, если (x', k') является «да-экземпляром» <math>\Pi \;</math>,

(2) <math>k' \le k \;</math>,

(3) <math>|x'| \le g(k) \;</math> для некоторой фиксированной функции g.

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