4551
правка
Остовное дерево с максимальным количеством листьев: различия между версиями
Перейти к навигации
Перейти к поиску
м
Остовное дерево с максимальным количеством листьев (посмотреть исходный код)
Версия от 23:23, 15 августа 2016
, 15 августа 2016→Открытые вопросы
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 135: | Строка 135: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Стратегии ветвления | '''Стратегии ветвления''' | ||
Хотя экстремальные структуры в определенном смысле представляют собой правильный подход к разработке FPT-алгоритма, этот подход не единственный. В частности, он не дает ответа на вопрос, что делать с ядром. Остается открытым вопрос поиска общих стратегий использования «структурной теории с подходящими параметрами» в стратегиях ветвления при анализе ядер в сложных задачах. | Хотя экстремальные структуры в определенном смысле представляют собой правильный подход к разработке FPT-алгоритма, этот подход не единственный. В частности, он не дает ответа на вопрос, что делать с ядром. Остается открытым вопрос поиска общих стратегий использования «структурной теории с подходящими параметрами» в стратегиях ветвления при анализе ядер в сложных задачах. | ||
Кернелизуемость Тьюринга | '''Кернелизуемость Тьюринга''' | ||
Преобразование с полиномиальным временем выполнения (x, k) к более простому редуцированному экземпляру ( | Преобразование с полиномиальным временем выполнения (x, k) к более простому редуцированному экземпляру (x', k') является преобразованием «от многих к одному». Можно обобщить понятие редукции «от многих к одному» до редукции Тьюринга. Как должен развиваться поиск экстремальных структур с полиномиальным временем выполнения в контексте такого менее жесткого FPT-алгоритма? | ||
Алгоритмические формы подхода на базе граничной леммы | '''Алгоритмические формы подхода на базе граничной леммы''' | ||
Из гипотезы граничной леммы о том, что (G, k) является «да-экземпляром», следует, что существует структура, являющаяся свидетелем для данного факта. Не делается предположений о том, что к этой структуре имеется алгоритмический доступ, а когда будут найдены правила редукции, они должны представлять собой преобразования, которые могут быть применены к (G, k) и структуре, которая может быть найдена в (G, k) за полиномиальное время. Иными словами, правила редукции не могут быть определены относительно структуры-свидетеля. Возможно ли описать более общие подходы к кернелизации, при которых структура-свидетель, используемая в ходе доказательства граничной леммы, может быть вычислена за полиномиальное время, и эта структура предоставит условный контекст для некоторых правил редукции? Как эти подходы изменят метод использования экстремальной структуры? | Из гипотезы граничной леммы о том, что (G, k) является «да-экземпляром», следует, что существует структура, являющаяся свидетелем для данного факта. Не делается предположений о том, что к этой структуре имеется алгоритмический доступ, а когда будут найдены правила редукции, они должны представлять собой преобразования, которые могут быть применены к (G, k) и структуре, которая может быть найдена в (G, k) за полиномиальное время. Иными словами, правила редукции не могут быть определены относительно структуры-свидетеля. Возможно ли описать более общие подходы к кернелизации, при которых структура-свидетель, используемая в ходе доказательства граничной леммы, может быть вычислена за полиномиальное время, и эта структура предоставит условный контекст для некоторых правил редукции? Как эти подходы изменят метод использования экстремальной структуры? | ||
Задача с аннотациями | '''Задача с аннотациями''' | ||
Можно рассмотреть обобщенную задачу построения остовного дерева с максимальным количеством листьев (MAX LEAF), в которой вершины и ребра имеют различные аннотации, говорящие о том, какие вершины должны быть листьями (и внутренними вершинами) в решении, и т.д. В общем случае подобная обобщенная форма задачи будет сложнее вышеописанной более простой формы. Однако некоторые из «наиболее известных» FPT-алгоритмов для решения различных задач основаны на таких обобщенных формах с аннотациями. В качестве примеров можно привести алгоритмы нахождения доминирующего множества для планарного графа (PLANAR DOMINATING SET) и разрывающего множества вершин (FEEDBACK VERTEX SET) [4]. Должны ли аннотации быть непременным компонентом рецепта наилучшего возможного алгоритма кернелизации с полиномиальным временем выполнения? | |||
== См. также == | == См. также == | ||