Разрывающее множество вершин на неориентированном графе: различия между версиями

Для входного графа G с множеством вершин <math>\{ v_1, ..., v_n \} \;</math> алгоритм с фиксированным параметром из работ [6, 10] решает задачу UFVS путем итеративного рассмотрения подграфов <math>G_i := G[ \{v_1, ...,  v_i \} ] \;</math>. Для i = 1 оптимальное разрывающее множество вершин является пустым. Предположим, что в случае i > 1 оптимальное разрывающее множество вершин Xi для Gi неизвестно. Очевидно, что <math>X_i \cup \{ v_{i+1} \} \;</math> является искомым множеством для <math>G_{i+1} \;</math>. Используя подпрограмму сжатия, алгоритм за время <math>O(c^k \cdot m) \;</math> может определить, является ли <math>X_i \cup \{ v_{i+1} \} \;</math> оптимальным разрывающим множеством вершин для <math>G_{i+1} \;</math>, и в случае, если оно таковым не является, вычислить оптимальное разрывающее множество вершин для <math>G_{i+1} \;</math>. Таким образом, в случае i = n мы получаем оптимальное разрывающее множество вершин для графа G за время <math>O(c^k \cdot mn) \;</math>.