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

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

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

Если по меньшей мере одно утверждение касательно структуры не выполняется, то дерево T можно улучшить, опираясь на один из индуктивных приоритетов. Заметим, что каждое утверждение доказано посредством рассуждения, которое можно интерпретировать как подпрограмму улучшения T с полиномиальным временем выполнения в случае противоречия утверждению.

Последовательность этих действий можно применить к исходному дереву T (и его потомкам) только полиномиальное количество раз, определяемое списком индуктивных приоритетов, до того момента, как мы получим дерево V, для которого выполняются все утверждения касательно структуры. В этот момент мы должны получить решение с c-аппроксимацией.

Здесь используются следующие сокращения: 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, максимальный размер независимого множества может быть вычислен за время <math>O^* (2,972^k) \;</math> на основе редукции ядра размером не более 7k. Использование результата решения одной задачи в качестве исходных данных для другой задачи оказывается весьма практичным.