* Какие есть задачи, что мы про них знаем?

-- Coloring, 3-Coloring, 3-List-Coloring
-- SAT, 3-SAT
-- CSP, CSP(3,2) для 3-Coloring и CSP(2,3) для 3-SAT

-- Все описанные задачи NP-трудны
-- Также трудна задача 3-Coloring в графе, где все степени не более 4
-- 3-List-Coloring в графе, где все степени не более 3 решается за линейное время (d-list-coloring в d-degree graph, Гравин, 2010)
-- 2-List-Coloring сводится к 2-SAT

* Какие есть общеизвестные алгоритмы для решения задачи 3-Coloring

-- Наивный алгоритм за 2^n
-- Вероятностный алгоритм за 1.5^n
-- Алгоритм за 1.44^n = 3^{n/3}

* Новые результаты: CSP(3,2) за 1.3645^n (детерминировано)

-- Lm #1: если у некоторой вершины список длины 2, её можно сократить
-- Lm #2: вероятностный алгоритм за 1.42^n = 2^{n/2}
-- Далее рассматриваем CSP(4,2) и вводим n3 и n4 (количества списков длины 3 и 4)
-- Оптимальное решение 1.3645^n для CSP(3,2) (максимум из трех редукций: max="4 4 5 5", "3 3 5", "4 4 4")
-- Оптимальное решение 1.8072^n для CSP(4,2) n=n3+(2-eps)n4 --> свели к CSP(3,2)


* Новые результаты: 3-Coloring за 1.3289^n (детерминировано)

-- Сведение к CSP: x=1.3645, time=3^|S|*x^(n-|S|-|N|)
-- 3^{1/4} < 1.3161^n
-- Мои рассуждени
---- Применив 1/2 выделение и CSP за 2^{n/2} получаем (3^{1/4}*2^{1/2})^{1/2} < 1.3643 для 3-Coloring
---- Применив 1/2 выделение и CSP за 2^{n/2} получаем (3^{1/4}*1.3645)^{1/2} < 1.3401 для 3-Coloring (1.34488 в оригинальной статье)
---- Если все вершины имеют степень хотя бы 4, получаем алгоритм за 1.3091^n (3^{1/5}=1.2457 и 1.3645 в пропорции 5:6)
---- Если вершин степени 4 мало (k штук), можно за O*(3^k) решить задачу, сведя ее к 3-list-coloring в 3-degree-graph
-- Рассуждения из статьи
---- Если есть цикл на вершинах степени 3, можно применить (4,5,6)-редукцию < 1.25 (рассмотрим четный цикл, длины 3, длины хотя бы 5)
---- Если есть дерево из хотя бы 8 вершин степени 3, можно применить (2,5,6)-редукцию < 1.325 (выберем вершину, которая делит дерево на части <= k/2, худший случай, когда дерево -- путь)
---- Построение bushy-forest

* Следствия

-- 3-SAT можно решить за O*(1.3645^t), где t -- количество 3-клозов (перешли от (a,b) к (b,a) СSP -- для каждого constaint выбрали переменную, которая его удовлетворит)
-- 3-List-Coloring можно решить за O(1.3645^t) (решили CSP в явном виде)
-- CSP(d,2) можно решить за O((0.41518*d)^n) (для каждой вершины оставили случайных 4 из d значений) 
-- 3-Edge-Coloring 1.3289^{3/2}^n = 1.5319^n. Решение за 1.42^n = 2^{n/2}: редукция, для ребра, соединяющего 2 вершины степени 3.