Параметр: экспонента от k, а не от n

Если ты отличаешь время nᵏ от 2ᵏ · n, знаешь определение FPT и объяснишь, почему дерево поиска для вершинного покрытия не больше 2ᵏ и не зависит от размера графа, листай до «Теперь сам».

Как думаешь, что здесь трудное

Сеть из тысячи серверов и пяти тысяч связей. Нужно поставить датчики на сервера так, чтобы каждая связь наблюдалась хотя бы одним концом. Бюджет - восемь датчиков. Задача о вершинном покрытии NP-трудна, вершин тысяча.

Ответь себе до чтения: безнадёжно ли это? Перебор всех наборов из восьми серверов - C(1000, 8) ≈ 2,4 · 10¹⁹. Но заметь, что тысяча здесь - не главное. Главное - что датчиков мало. Есть алгоритм, который делает не больше 2⁸ = 256 ветвлений, сколько бы серверов ни было, и тратит на каждое линейное время по числу связей. Трудность задачи «сидит» в восьмёрке, а не в тысяче.

На что это похоже

Поиск виновника среди тысячи сотрудников, если известно, что виновных не больше трёх и каждый инцидент задевал двоих. Берёшь любой нераскрытый инцидент: виноват один из двоих - проверяешь обе версии. В каждой версии виновных осталось не больше двух, и снова берёшь нераскрытый инцидент. Глубина расследования - три шага, версий - не больше 2³ = 8. Размер компании на число версий не влияет.

Это и есть параметризованное мышление: найти малое число, которое ограничивает глубину рассуждений, и разрешить экспоненту только от него.

Механизм: дерево поиска глубины k

Определение. Параметризованная задача - вход плюс число k. Она FPT, если решается за f(k) · n^c, где f - любая вычислимая функция, а c не зависит от k. Сравни с n^k: при k = 10 и n = 1000 первое (2¹⁰ · 1000 ≈ 10⁶) - мгновенно, второе (10³⁰) - никогда. Разница не в экспоненте как таковой, а в том, перемножается ли она с n.

Дерево поиска для вершинного покрытия. Есть ли покрытие из не больше k вершин:

derevo(рёбра, k):
    рёбер нет        → да
    k = 0            → нет
    ребро u-v - любое из оставшихся:
        одна из u, v обязана быть в покрытии
        попробовать u:  derevo(рёбра без рёбер u, k − 1)
        попробовать v:  derevo(рёбра без рёбер v, k − 1)

Каждый вызов уменьшает k на единицу, глубина не больше k, ветвление на два: вызовов не больше 2ᵏ⁺¹ − 1, каждый стоит O(m) на удаление рёбер. Итого O(2ᵏ · m) - FPT.

Почему ветвиться можно по любому ребру: в покрытии обязан быть один из его концов. Это не эвристика, а полный разбор вариантов, просто вариантов на каждом уровне всего два.

Правило

Задача FPT по параметру k, если решается за f(k) · poly(n). Вершинное покрытие размера k: взять непокрытое ребро и ветвиться по двум его концам, уменьшая k; дерево не больше 2ᵏ⁺¹ − 1 узлов, и его размер не зависит от размера графа. Перебор наборов стоит C(n, k) - порядка nᵏ / k! - он не FPT.

Разбор: дерево против перебора наборов

s_pokrytiem строит граф на 60 вершинах, у которого первые k вершин - заведомо покрытие (все рёбра задевают их). derevo отвечает, есть ли покрытие из k вершин, и считает вызовы. Для каждого k два вопроса: с бюджетом k (ответ «да») и k − 1 (ответ «нет», если покрытие меньше не бывает).

import math
import random

def s_pokrytiem(n, k, m, zerno):
    # граф, у которого заведомо есть покрытие из первых k вершин
    random.seed(zerno)
    ryobra = []
    while len(ryobra) < m:
        a = random.randrange(k)
        b = random.randrange(n)
        if a != b and [a, b] not in ryobra and [b, a] not in ryobra:
            ryobra.append([a, b])
    return ryobra

def derevo(ryobra, k, schet):
    schet[0] = schet[0] + 1
    if len(ryobra) == 0:
        return True
    if k == 0:
        return False
    u = ryobra[0][0]
    v = ryobra[0][1]
    for vzyat in [u, v]:
        ostalis = []
        for r in ryobra:
            if r[0] != vzyat and r[1] != vzyat:
                ostalis.append(r)
        if derevo(ostalis, k - 1, schet):
            return True
    return False

n = 60
for k in [3, 5, 7, 9]:
    ryobra = s_pokrytiem(n, k, 2 * n, k)
    da = [0]
    net = [0]
    print(k, math.comb(n, k), derevo(ryobra, k, da), da[0],
          derevo(ryobra, k - 1, net), net[0], 2 ** (k + 1) - 1)

3 34220 True 4 False 7 15
5 5461512 True 6 False 31 63
7 386206920 True 8 False 127 255
9 14783142660 True 10 False 511 1023

Столбцы: k, число наборов из k вершин, ответ и вызовы с бюджетом k, ответ и вызовы с бюджетом k − 1, предел 2ᵏ⁺¹ − 1. При k = 9 наборов почти пятнадцать миллиардов, дерево с бюджетом k сделало 10 вызовов - генератор кладёт вершину покрытия первой в каждое ребро, и первая же ветка верна, - а с бюджетом k − 1 обошло все 511 узлов дерева глубины 8 и доказало, что покрытия из восьми вершин нет. Ответ «нет» здесь самый дорогой: пришлось проверить все листья.

Разбор: размер графа не влияет на дерево

k = 6 фиксировано, граф растёт: 20, 40, 80, 160 вершин. Вопрос с бюджетом 5 - ответ «нет», то есть полное дерево.

import random

def s_pokrytiem(n, k, m, zerno):
    random.seed(zerno)
    ryobra = []
    while len(ryobra) < m:
        a = random.randrange(k)
        b = random.randrange(n)
        if a != b and [a, b] not in ryobra and [b, a] not in ryobra:
            ryobra.append([a, b])
    return ryobra

def derevo(ryobra, k, schet):
    schet[0] = schet[0] + 1
    if len(ryobra) == 0:
        return True
    if k == 0:
        return False
    u = ryobra[0][0]
    v = ryobra[0][1]
    for vzyat in [u, v]:
        ostalis = []
        for r in ryobra:
            if r[0] != vzyat and r[1] != vzyat:
                ostalis.append(r)
        if derevo(ostalis, k - 1, schet):
            return True
    return False

k = 6
for n in [20, 40, 80, 160]:
    ryobra = s_pokrytiem(n, k, 2 * n, n)
    schet = [0]
    print(n, len(ryobra), derevo(ryobra, k - 1, schet), schet[0])

20 40 False 63
40 80 False 63
80 160 False 63
160 320 False 63

63 вызова на каждом графе - это 2⁶ − 1, полное дерево глубины 5. Рёбер в восемь раз больше, а дерево то же. Растёт только цена одного вызова: удаление рёбер просматривает их список, O(m). Время - 2ᵏ · m, линейно по графу: удвоил граф - вдвое дольше, а перебор наборов из шести вершин стал бы дороже примерно в C(40, 6) / C(20, 6) ≈ 99 раз - и с ростом n это отношение приближается к 2⁶ = 64.

Что ломается без этого

Перебирают наборы из k вершин. C(n, k) - многочлен степени k от n. При k = 8 и тысяче вершин - 10¹⁹. Это не FPT: экспонента от k сидит в показателе n.

Путают параметр с размером. «Задача NP-трудна, значит, на тысяче вершин не решить» - неверно, если ответ мал. Правильный вопрос: какое число в задаче маленькое, и можно ли загнать экспоненту в него.

Ветвятся по вершине без причины. «Вершина в покрытии или нет» без опоры на ребро даёт дерево глубины n, а не k: ветка «не в покрытии» не уменьшает параметр. Ветвление по ребру гарантирует, что каждая ветка тратит бюджет.

Зачем это в работе

Параметр - то, что мало на практике: число датчиков в бюджете, число конфликтов, которые надо разрешить, число лишних строк в данных, глубина вложенности, число изменённых файлов. Если найти его и построить алгоритм с экспонентой только от него, NP-трудная задача на миллионе объектов решается точно. Так работают проверка типов в компиляторах (трудность в глубине вложенных типов, а не в длине программы), поиск небольших исправлений в данных, анализ сетей с малым числом узких мест.

Теперь сам

1. n = 10 000, k = 12. Сколько примерно узлов в дереве поиска и сколько наборов в переборе?
2. Почему ветвление по ребру, а не по произвольной вершине, ограничивает глубину дерева числом k?
3. Время n^(k/2) - это FPT?