## ЛКШ.2018.Июль Спецкурс по ветвлению в переборе

1. Задача: поиск максимальной клики

1. Равносильные: поиск максимального независимого множества, минимального вершинного покрытия
2. В двудольном графе задачи решаются, в произвольном NP-трудные
3. Очевидное решение: перебираем вершины, каждую или берём в ответ, или не берём... 2n?
4. На самом деле гораздо быстрее, особенно если расщепляться (ветвиться) не по произвольной вершине, а по вершине max/min степени.
5. Как решать рекуррентные соотношения вида T(n) = T(n-3) + T(n-5) + T(n-7)? Бинпоиск по 1 = α-3 + α-5 + α-7.

2. Расщепление по вершине минимальной степени

1. T(k) = (k + 1)T(n - k - 1) ⇒ T(n) ≤ 3n/3 − алгоритм для перечисления всех максимальных по включению клик

3. Оценка для независимого множества (можно переделать на клику, покрытия)

1. Добавим отсечение "вершину степени ≤ 1 выгодно жадно взять", получим T(n) = T(n - 1) + T(n - 3) = 1.466n
2. Добавим ещё оптимизацию "расщепляться по вершине максимальной степени".
   Казалось бы асимптотика в худшем случае не изменилась т.к. бывает max deg = 2.
3. Введём веса вершинам w(v) = (deg[v] ≤ 1 ? 0 : 1). Размер задачи = сумма весов.
4. Попробуем w1 = 0, w2 = w3 = 1. Попробуем w2 = 0.5.

4. Улучшаем алгоритм

1. Добавим отсечение "все вершины степени 2" ⇒ решим жадность.
2. Повторим эксперимент с весами.
3. Научимся минимизировать F(w2, w3, w4), получим заявленное время
4. Улучшаем дальше: если есть вершина степени 2, её можно удалить.