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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 15: Строка 15:


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


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


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

Версия от 20:47, 5 августа 2016

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

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


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

Задача построения максимального листового остовного дерева (МЛОД) заключается в нахождении остовного дерева, имеющего не менее 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-алгоритм с наименьшим размером ядра.