Клика и W[1]: параметр, который не помогает

Если ты знаешь, что такое W[1], чем параметрическое сведение отличается от обычного и почему вершинное покрытие FPT, а независимое множество - нет, хотя это дополнения друг друга, листай до «Теперь сам».

Как думаешь, всё ли сдаётся параметру

Найти в социальном графе пятерых, знакомых каждый с каждым, - клику размера 5. Параметр маленький, как у датчиков из прошлых уроков. Хочется построить дерево поиска глубины 5: взять вершину, ветвиться «в клике / не в клике».

Ответь себе до чтения: что пойдёт не так? Ветка «не в клике» не тратит бюджет: она просто убирает вершину, и таких веток может быть n подряд. Глубина дерева - уже не 5, а n. Обойти это пока не удалось никому, и есть веская причина думать, что не удастся: клика - образцовая задача класса, где параметр не помогает.

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

Две похожие задачи поиска в архиве. Первая: «найди пять документов, которые закрывают все темы» - каждая тема, которую нельзя закрыть иначе, сразу диктует выбор, и выбор быстро сужается. Вторая: «найди пять документов, попарно ссылающихся друг на друга» - ни одна часть архива не диктует ответ, и кандидатов в каждую позицию остаются тысячи.

Обе задачи «про пять документов», но в первой малое число ограничивает рассуждение, а во второй - нет. Теория параметризованной сложности различает их так же строго, как P и NP.

Механизм: W[1] и параметрические сведения

W[1]. Класс параметризованных задач, сводящихся к клике параметрическими сведениями; клика в нём полна (Дауни, Феллоуз, 1995). Гипотеза FPT ≠ W[1] - параметрический аналог P ≠ NP: если она верна, ни одна W[1]-трудная задача не решается за f(k) · poly(n). Лучший известный алгоритм для клики - n^(ωk/3) (при k, кратном трём), где ω < 2,38 - показатель быстрого умножения матриц (Нешетржил, Поляк, 1985).

Параметрическое сведение из (x, k) в (x', k'): работает за f(k) · poly(|x|) и даёт k' ≤ g(k) - новый параметр зависит только от старого. Тогда FPT-алгоритм для второй задачи даёт FPT-алгоритм для первой.

независимое множество (G, k)  →  клика (дополнение G, k)
    параметр тот же: сведение параметрическое
вершинное покрытие (G, k)     →  независимое множество (G, n − k)
    параметр n − k: сведение НЕ параметрическое

Обычные сведения из раздела о сложности сохраняют размер, но не параметр. Вершинное покрытие и независимое множество - одна задача («удалить вершины, чтобы не осталось рёбер» - «оставить вершины без рёбер»), но параметр «сколько удалить» мал, когда покрытие мало, а параметр «сколько оставить» мал, когда множество мало. Первый случай FPT, второй - W[1]-трудный.

Дальше по лестнице. Доминирующее множество из k вершин - W[2]-полно, ещё на ступень выше. Иерархия FPT ⊆ W[1] ⊆ W[2] ⊆ … повторяет картину полиномиальной иерархии для параметров.

Правило

W[1] - класс параметризованных задач, сводящихся к клике параметрически. При FPT ≠ W[1] W[1]-трудные задачи не решаются за f(k) · poly(n); для всех задач класса этого утверждать нельзя, потому что FPT ⊆ W[1]. Параметрическое сведение обязано давать новый параметр, ограниченный функцией от старого. Поэтому вершинное покрытие FPT по размеру покрытия, а независимое множество и клика W[1]-трудны по размеру ответа.

Разбор: клика растёт вместе с n

Случайные графы, ребро между любыми двумя вершинами с вероятностью 1/2. klik перечисляет клики размера l, наращивая их по вершинам в порядке номеров, и считает вызовы. Для каждого n - размеры 3, 4 и 5.

import random

def graf(n, zerno):
    random.seed(zerno)
    sosedi = []
    for v in range(n):
        sosedi.append([False] * n)
    for a in range(n):
        for b in range(a + 1, n):
            if random.random() < 0.5:
                sosedi[a][b] = True
                sosedi[b][a] = True
    return sosedi

def klik(sosedi, kandidaty, l, schet):
    # сколько клик размера l можно достроить из кандидатов
    schet[0] = schet[0] + 1
    if l == 0:
        return 1
    vsego = 0
    for i in range(len(kandidaty)):
        v = kandidaty[i]
        dalshe = []
        for u in kandidaty[i + 1:]:
            if sosedi[v][u]:
                dalshe.append(u)
        if len(dalshe) >= l - 1:
            vsego = vsego + klik(sosedi, dalshe, l - 1, schet)
    return vsego

for n in [10, 20, 40]:
    sosedi = graf(n, n)
    stroka = [n]
    for l in [3, 4, 5]:
        schet = [0]
        klik(sosedi, list(range(n)), l, schet)
        stroka.append(schet[0])
    print(stroka)

[10, 36, 9, 2]
[20, 286, 291, 149]
[40, 1631, 2493, 1710]

Удвоение n с 20 до 40 умножило работу для l = 3 почти в 6 раз, для l = 4 - в 8,5, для l = 5 - в 11,5. Чем больше размер клики, тем круче рост по n: экспонента от l стоит в показателе n. У дерева поиска для покрытия из первого урока удвоение графа не меняло числа вызовов вовсе - это и есть разница между FPT и n^(O(k)).

Разбор: одна задача, два параметра

Граф на 60 вершинах с покрытием из шести вершин. Дерево поиска для покрытия находит его, а дополнение покрытия - независимое множество из 54 вершин.

import math
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 pokrytie(ryobra, k, schet):
    schet[0] = schet[0] + 1
    if len(ryobra) == 0:
        return [[]]
    if k == 0:
        return []
    for v in ryobra[0]:
        ostalis = []
        for r in ryobra:
            if r[0] != v and r[1] != v:
                ostalis.append(r)
        otvet = pokrytie(ostalis, k - 1, schet)
        if len(otvet) > 0:
            return [otvet[0] + [v]]
    return []

n = 60
k = 6
ryobra = s_pokrytiem(n, k, 120, 3)
schet = [0]
p = pokrytie(ryobra, k, schet)[0]
nezavisimoe = []
for v in range(n):
    if v not in p:
        nezavisimoe.append(v)
print(sorted(p), schet[0])
print(len(nezavisimoe), math.comb(n, len(nezavisimoe)))

[0, 1, 2, 3, 4, 5] 7
54 50063860

Покрытие найдено за 7 вызовов, независимое множество из 54 вершин - его дополнение. Перебор множеств размера 54 - пятьдесят миллионов наборов. Одна и та же задача: если ответ «почти весь граф», её решает FPT-алгоритм по маленькому дополнению.

Но если нужно независимое множество из пяти вершин в большом плотном графе, дополнение - покрытие из n − 5 вершин, и параметр огромен. Здесь помощи от покрытия нет: это клика в дополнении графа, W[1].

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

Сводят обычным сведением и делают вывод о FPT. Вершинное покрытие сводится к независимому множеству, но FPT покрытия ничего не говорит о множестве: параметр не сохранился.

Строят дерево поиска, где ветка не тратит параметр. «В клике / не в клике» - глубина n. Если ветка не уменьшает k, это не FPT-ветвление.

Выбирают неудачный параметр. «Задача W[1]-трудна» относится к паре «задача + параметр». Та же задача может быть FPT по другому параметру: независимое множество - по древесной ширине графаРазбирается в разделе 22, глава «Древесная ширина, цветное кодирование и нижние границы»: Древесное разложение: насколько граф похож на дерево, о ней следующая глава.

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

Прежде чем строить параметризованный алгоритм, проверяют: не W[1]-трудна ли задача по выбранному параметру. Поиск клики, плотного подграфа, доминирующего множества по размеру ответа - типичные ловушки, где ждать 2ᵏ · n бесполезно. Тогда ищут другой параметр, который мал в данных: степень вершин, древесную ширину, число изменений относительно известного решения.

Теперь сам

1. Граф на 1000 вершинах, ищем независимое множество из 995. Какой параметр взять и какой алгоритм?
2. Почему сведение «клика (G, k) → независимое множество (дополнение G, k)» параметрическое?
3. Задача W[2]-полна. Может ли она быть FPT, если FPT ≠ W[1]?