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

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

Если перефразировать задачу в терминах теории структур, важнейший вопрос будет звучать следующим образом: какова структура графов, не имеющих подграфа с k листьями? Результат Клейтмана и Веста из теории графов показывает, что граф с минимальной степенью не менее 3, не включающий подграф с k листьями, имеет не более 4(k - 3) вершин. На рис. 1 показано, что это лучший возможный результат для данной гипотезы. Однако исследование структуры при помощи экстремальных методов выявляет необходимость в применении правила редукции, показанного на рис. 2. Примерно двадцати различных правил редукции с полиномиальным временем выполнения (некоторые из них являются намного более сложными и «глобальными» по своей структуре, чем приведенное для примера простое локальное правило редукции) будет достаточно для кернелизации графа с минимальной степенью 2, имеющего не более 3,5k вершин.