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

Перейти к навигации Перейти к поиску
Строка 48: Строка 48:


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




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


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




В общем случае экземпляр параметризованной задачи состоит из пары (x, k) и «границы», которая вычисляется посредством фиксации x и изменения k с последующим определением, какой ответ имеет задача разрешимости – «да» или «нет. Представляет интерес величина границы при редукции x. Типичная граничная лемма выглядит следующим образом.
В общем случае экземпляр параметризованной задачи состоит из пары (x, k) и «границы», которая вычисляется посредством фиксации x и изменения k с последующим определением, какой ответ имеет [[задача разрешимости]] – «да» или «нет. Представляет интерес величина границы при редукции x. Типичная граничная лемма выглядит следующим образом.




Лемма 2. Пусть (G, k) – экземпляр задачи построения остовного дерева с максимальным количеством листьев после редукции, для которого (G, k) является «да-экземпляром», а (G, k + 1) – «нет-экземпляром». Тогда |G| < ck (где c – небольшая константа, значение которой будет вычислено в результате решения).
'''Лемма 2.''' Пусть (G, k) – экземпляр задачи построения остовного дерева с максимальным количеством листьев после редукции, для которого (G, k) является «да-экземпляром», а (G, k + 1) – «нет-экземпляром». Тогда <math>|G| \le ck \;</math> (где c – небольшая константа, значение которой будет вычислено в результате решения).




Строка 96: Строка 96:




Цель (б): предварительная обработка с полиномиальным временем выполнения и подпрограммы редукции данных
'''Цель (б): предварительная обработка с полиномиальным временем выполнения и подпрограммы редукции данных'''


Ниже приводится пример таблицы, используемой для отслеживания каждого возможного состояния границы для возможного решения. Можно привести примеры, демонстрирующие исключительно успешное каскадное применение правил редукции данных к реальным распределениям данных и описывающие разнообразие математических феноменов, относящихся к правилам редукции. Например, некоторые правила редукции – такие как правило разложения на составляющие Клейтмана-Веста для задачи ОДМЛ (рис. 2) – имеют фиксированный «размер границы» (в данном случае равный 2), тогда как правила редукции типа «корона» не имеют такового.
Ниже приводится пример таблицы, используемой для отслеживания каждого возможного состояния границы для возможного решения. Можно привести примеры, демонстрирующие исключительно успешное каскадное применение правил редукции данных к реальным распределениям данных и описывающие разнообразие математических феноменов, относящихся к правилам редукции. Например, некоторые правила редукции – такие как правило разложения на составляющие Клейтмана-Веста для задачи ОДМЛ (рис. 2) – имеют фиксированный «размер границы» (в данном случае равный 2), тогда как правила редукции типа «корона» не имеют такового.


Цель (в): градиенты и преобразования решений для локального поиска
 
'''Цель (в): градиенты и преобразования решений для локального поиска'''


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




Цель (г): алгоритмы аппроксимации с полиномиальным временем выполнения
'''Цель (г): алгоритмы аппроксимации с полиномиальным временем выполнения'''


Теория использования экстремальных структур с полиномиальным временем выполнения напрямую приводит к получению алгоритма аппроксимации ОДМЛ с константным множителем и полиномиальным временем выполнения. Вначале выполним редукцию G при помощи правил кернелизации. Правила редукции сохраняют параметры аппроксимации. Возьмем любое дерево T (не обязательно остовное) в G. Если выполняются все утверждения касательно структуры, тогда (согласно рассуждениям граничной леммы) дерево T должно иметь не менее n/c листьев для c = 3,75. Таким образом, восстановив T с учетом произведенной редукции, получим c-аппроксимацию.
Теория использования экстремальных структур с полиномиальным временем выполнения напрямую приводит к получению алгоритма аппроксимации ОДМЛ с константным множителем и полиномиальным временем выполнения. Вначале выполним редукцию G при помощи правил кернелизации. Правила редукции сохраняют параметры аппроксимации. Возьмем любое дерево T (не обязательно остовное) в G. Если выполняются все утверждения касательно структуры, тогда (согласно рассуждениям граничной леммы) дерево T должно иметь не менее n/c листьев для c = 3,75. Таким образом, восстановив T с учетом произведенной редукции, получим c-аппроксимацию.
Строка 117: Строка 117:




Цель (г): структура, используемая для определения экологии сложности
'''Цель (д): структура, используемая для определения экологии сложности'''


Цель заключается в том, чтобы понять, как именно каждый параметр, определяющий входные данные задачи, влияет на сложность всех других задач. В качестве примера рассмотрим таблицу 1:
Цель заключается в том, чтобы понять, как именно каждый параметр, определяющий входные данные задачи, влияет на сложность всех других задач. В качестве примера рассмотрим таблицу 1:
Строка 128: Строка 128:


Здесь используются следующие сокращения: TW – это древесная ширина дерева (TREEWIDTH), BW – ширина полосы (BANDWIDTH), VC – вершинное покрытие (VERTEX COVER), DS – доминирующее множество (DOMINATING SET), G – род (GENUS), а ML – максимальное количество листьев (MAX LEAF). Обозначение во второй строке и четвертом столбце говорит о том, существует ли FPT-алгоритм для решения задачи DOMINATING SET на графе G с шириной полосы не более k. Обозначение в четвертой строке и втором столбце говорит о том, что неизвестно, может ли задача BANDWIDTH быть оптимально решена FPT-алгоритмом, если параметром является граница числа доминирования входного графа.
Здесь используются следующие сокращения: TW – это древесная ширина дерева (TREEWIDTH), BW – ширина полосы (BANDWIDTH), VC – вершинное покрытие (VERTEX COVER), DS – доминирующее множество (DOMINATING SET), G – род (GENUS), а ML – максимальное количество листьев (MAX LEAF). Обозначение во второй строке и четвертом столбце говорит о том, существует ли FPT-алгоритм для решения задачи DOMINATING SET на графе G с шириной полосы не более k. Обозначение в четвертой строке и втором столбце говорит о том, что неизвестно, может ли задача BANDWIDTH быть оптимально решена FPT-алгоритмом, если параметром является граница числа доминирования входного графа.
MAX LEAF применяется к последней строке таблицы. Для графов с максимальным количеством листьев, ограниченным k, максимальный размер независимого множества может быть вычислен за время O*(2,972k) на основе редукции ядра размером не более 7k. Использование результата решения одной задачи в качестве исходных данных для другой задачи оказывается весьма практичным.


MAX LEAF применяется к последней строке таблицы. Для графов с максимальным количеством листьев, ограниченным k, максимальный размер независимого множества может быть вычислен за время <math>O^* (2,972^k) \;</math> на основе редукции ядра размером не более 7k. Использование результата решения одной задачи в качестве исходных данных для другой задачи оказывается весьма практичным.


== Применение ==
== Применение ==
Источник — http://pco.iis.nsk.su/wega/index.php/Остовное_дерево_с_максимальным_количеством_листьев