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

При рассмотрении параметризованной сложности значение k называется ''параметром'', который в определенном смысле отражает структуру входных данных или другой аспект цели вычисления. Например, k может обозначать количество ребер, которые необходимо удалить для получения графа без циклов; количество последовательностей ДНК, подлежащих выравниванию в задаче выравнивания последовательностей; максимальную глубину вложенности объявления типа у компилятора; <math>k = 1 / \epsilon \;</math> может обозначать параметризацию при анализе аппроксимации; кроме того, k также может быть составным значением, зависящим от нескольких переменных.

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

Лемма 1. Параметризованная задача <math>\Pi \;</math> является задачей с фиксированными параметрами (FPT) в том и только том случае, если существует преобразование с полиномиальным временем выполнения (относительно n и k), переводящее (x, k) в (x', k,), такое, что: