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

В ситуации, описываемой леммой, можно сказать, что мы можем кернелизовать исходные экземпляры до экземпляров размером не более g(k). Два этих класса задач нередко бывают тесно связаны, однако результаты их выполнения различаются. Наилучший известный FPT-алгоритм задачи построения остовного дерева с максимальным количеством листьев с временем выполнения <math>O^* (8,12^k) \;</math> предложил Бонсма [1] на основе подхода на базе экстремальных структур, который разработали Эстивилл-Кастро, Феллоуз, Лэнгстон и Розамонд [8]. Этот алгоритм определяет, имеет ли граф G с n вершинами остовное дерево не менее чем с k листьями. В то же время авторы работы [8] представили FPT-алгоритм с наименьшим размером ядра.

(а) Более эффективные FPT-алгоритмы, полученные в результате применения теории более глубокой структуры, более мощных правил редукции, связанных с этой теорией, и более сильных доказательств по индукции для улучшенных границ кернелизации.

(б) Правила мощной предварительной обработки (редукции данных / кернелизации) и комбинации правил, которые могут использоваться независимо от того, насколько мал параметр, и могут комбинироваться с другими подходами – например, аппроксимацией и эвристиками. Обычно они несложны для программирования.