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

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

Можно рассмотреть обобщенную задачу построения остовного дерева с максимальным количеством листьев (MAX LEAF), в которой вершины и ребра имеют различные аннотации, говорящие о том, какие вершины должны быть листьями (и внутренними вершинами) в решении, и т.д. В общем случае подобная обобщенная форма задачи будет сложнее вышеописанной более простой формы. Однако некоторые из «наиболее известных» FPT-алгоритмов для решения различных задач основаны на таких обобщенных формах с аннотациями. В качестве примеров можно привести алгоритмы нахождения доминирующего множества для планарного графа (PLANAR DOMINATING SET) и разрывающего множества вершин (FEEDBACK VERTEX SET) [4]. Должны ли аннотации быть непременным компонентом рецепта наилучшего возможного алгоритма кернелизации с полиномиальным временем выполнения?