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

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

<br>
# Расщепление по вершине минимальной степени
## T(k) = (k + 1)T(n - k - 1) &rArr; T(n) &le; 3^{n/3} -- алгоритм для перечисления всех максимальных по включению клик

<br>
# Оценка для независимого множества (можно переделать на клику, покрытия)
## Добавим отсечение "вершину степени &le; 1 выгодно жадно взять", получим T(n) = T(n - 1) + T(n - 3) = 1.466^n
## Добавим ещё оптимизацию "расщепляться по вершине максимальной степени". <br> Казалось бы асимптотика в худшем случае не изменилась т.к. бывает max deg = 2.
## Введём веса вершинам w(v) = (deg[v] &le; 1 ? 0 : 1). Размер задачи = сумма весов.
## Попробуем w_1 = 0, w_2 = w_3 = 1. Попробуем w_2 = 0.5. 

<br>
# Улучшаем алгоритм
## Добавим отсечение "все вершины степени 2" &rArr; решим жадность.
## Повторим эксперимент с весами.
## Научимся минимизировать F(w_2, w_3, w_4), получим заявленное время
## Улучшаем дальше: если есть вершина степени 2, её можно удалить.