Конспект: древесная ширина, цветное кодирование и нижние границы

Понятия

Древесное разложение - мешки вершин, связанные в дерево: каждая вершина и каждое ребро в каком-то мешке, мешки с одной вершиной связны. Ширина - наибольший мешок минус один; древесная ширина - наименьшая ширина.

Динамика по разложению - лучшее значение для каждого состояния мешка.

Цветное кодирование - случайные цвета вместо памяти о посещённых вершинах.

ETH - 3-SAT не решается за 2^o(n). SETH - k-SAT при больших k не быстрее (2 − ε)ⁿ.

Что унести

ДЕРЕВО: независимое множество с весами
s(v) = w(v) + Σ bez(дети);   bez(v) = Σ max(s, bez)(дети)
снизу вверх, n − 1 шаг;  10 000 вершин - 9999 шагов

ДРЕВЕСНАЯ ШИРИНА
дерево при n >= 2: 1; одна вершина: 0
цикл: 2; решётка k × k при k >= 2: k; полный граф: n − 1
плоский граф - O(√n)
оценка сверху: исключать вершину наименьшей степени,
    соседей соединять; ширина - наибольшая степень при исключении
точная ширина - NP-трудно; при фиксированной - линейно (Бодлендер)

ДИНАМИКА ПО МЕШКАМ
решётка k × N по столбцам: маска без соседних единиц
    масок F(k + 2): 3, 5, 8, 13, 21, …;  пар ~ 2,4ᵏ
    новое[m] = вес(m) + max лучшее[p], m & p = 0
8 × 100: 137 907 переходов вместо 2⁸⁰⁰
общее: независимое множество 2^w · w^O(1) · n

ЦВЕТНОЕ КОДИРОВАНИЕ: путь из k вершин
est[v][S]: путь с цветами S, кончается в v;  2ᵏ · m
разноцветен с вероятностью k!/kᵏ >= e^(−k)
    k = 6: 1,5%;  повторов ~ eᵏ  →  (2e)ᵏ · poly
«нашёл» - точно есть; «не нашёл» - с вероятностью ошибки

ETH И SETH
сведение N = O(n)  → не 2^o(N);   N = O(n²) → не 2^o(√N)
ETH: покрытие не 2^o(k); клика не f(k)·n^o(k);
     плоские графы не 2^o(√n) (а 2^O(√n) есть)
бюджет 10⁹: основа 2 - 29 переменных, 1,308 - 77, 1,01 - 2082
SETH: расстояние редактирования не n^(2 − ε) (Бакурс, Индик)

Ловушки джокера

Хранил одно число на вершину дерева. Родитель не знает, можно ли брать его вместе с этим лучшим.

Нарушил связность мешков. Мешок перестаёт быть перемычкой, динамика врёт.

Шёл по разложению поперёк. Мешок-строка решётки - экспонента от длины.

Сделал одну раскраску. Единственный путь найдётся с вероятностью k!/kᵏ.

Взял меньше k цветов. Разноцветного пути из k вершин не бывает.

Сделал вывод «не 2^o(n)» по сведению с раздуванием. Размер сведения - часть вывода.

Счёл ETH доказанной. Это гипотеза, сильнее P ≠ NP.

Проверь себя

Напиши динамику для независимого множества на дереве. Сформулируй три условия древесного разложения и назови ширину дерева, цикла, решётки и полного графа. Как устроена динамика по столбцам решётки и сколько у неё состояний? Почему цветное кодирование не допускает повторов вершин и сколько нужно раскрасок? Что утверждают ETH и SETH и что из них следует?

Курсель: MSO₂ и разложение ширины t дают f(|φ|,t)·n. Двумерность связывает планарную ширину O(√k) с ростом параметра на решётке; подэкспонента требует явной подходящей динамики.