День 6. NP-трудные задачи (3 января)

  1. [Сережа.М] Динамика по подмножествам
    1. Формулировки: независимое множество, клика, задачи вершинной раскраски
    2. Битовые операции с множествами (пересечение, объединение, разность, i-й бит, вкладывается ли)
    3. Перебор множеств, перебор старшего бита, для каждого множества посчитать число элементов (бит), сумму весов элементов
    4. Раскраска графа в минимальное число цветов за O(3n) и предподсчет за O(2n) для каждого множества, независимое ли оно.
    5. Гамильтонов путь, цикл за O(2nn2), O(2nn)
    6. Для каждого множества посчитать количество подклик за O(2n)
    7. Найти количество подклик и max подклику за O(2n/2)
  2. [Сережа.K] NP-hard задачи
    1. Общие слова
    2. Формула включения-исключения
      1. Гамильтонов путь за O*(2n) с полиномиальной памятью
      2. Раскраска графа в минимальное число цветов O*(2n) с полиномиальной памятью
    3. vertex cover размера k за O(n + m + 1.325k × Poly(k))
      1. Алгоритм за O(2k)
      2. Расщепление по вершине максимальной степени, T(k) = T(k-1) + T(k-deg), решение реккурентных соотношений бинраным поиском
      3. Избавляемся от вершин степени 1 ⇒ T(k) = T(k-1) + T(k-2) = 1.62n = Fibn
      4. Избавляемся от вершин степени 2 ⇒ T(k) = T(k-1) + T(k-3) = 1.47n
      5. Пусть есть вершина степени 3 ⇒ T(k) = max(T(k-1) + T(k-4), T(k-2) + T(k-3)) = max((1,4); (2,3)) 1.38n
      6. [не успеем] Пусть есть вершина степени хотя бы 5 ⇒ (1,5) = 1.325k
      7. [не успеем] Пусть все вершины степени 4 ⇒ ((1+2,1+4),4) = 1.325k
    4. Рандом
      1. Тест на изоморфность графов, в среднем хорошо работающий
      2. Алгоритм поиска простого пути длины k с помощью случайной покраски за O*((2e)k), где e = 2.71828...