ЛКШ.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, её можно удалить.