Дерево Штейнера и покрытие ориентированного графа k циклами (5 марта 2014)

  1. Про treewidth (древесную ширину) и pathwidth (путевую ширину)
    1. Определение
    2. nice tree: Leaf, Root, Join, Introduce Vertex, Forget Vertex, Introduce Edge (каждому ребру соотвтествует одна introduce edge вершина)
    3. Как обычно ведет себя динамика для pathwidth: состояние = какие вершины мы взяли, переход = добавить новую вершину
    4. Как обычно ведет себя динамика для treewidth: тоже самое + для Join имеем одинаковую покраску слева и справа
    5. Пример обеих динамик для задачи <<максимальное по весу независимое пожмножество>>
  2. Задача про дерево Штейнера
    1. Формулировка: проверить, можно ли соединить несколько вершин остовным деревом из не более чем k вершин
    2. Формулировка для точек на плоскости, решение для трех и четырех точек (три точки точно, четыре точки итерациями)
    3. Решение за 3km, где m − количество ребер, а k − количество вершин, которые мы соединяем
    4. Решение за (t = tw = treewidth) t! ≈ (t/e)t, проблема со связностью
  3. Идея Cut & Count
    1. Пусть f − количество хороших подмножеств, а задача − проверить, существует ли хотя бы одно хорошее подмножество, тогда f можно считать по модулю 2
    2. Isolation Lemma: если вершинам сопоставить случайные веса от 1 до N, то с вероятностью хотя бы 1 - N/|U|, будет ровно одно хорошее подмножество минимального веса
    3. Получили общую схему: сопоставить вершинам случайные веса от 1 до 2|U|, решить по модулю 2, получили одностороннюю ошибку 1/2
    4. Как использовать условие <<по модулю 2>> чтобы на пустом месте заработать связность? Нужно, чтобы несвязных решений было четное число
    5. Будем считать количество пар (X, cut = (X1, X2)), где X − множество вершин, которые мы взяли, а cut − разрез согласованный с X.
      У связного X будет ровно один разрез такой, что v1 ∈ X1
  4. Применяем идею Cut & Count
    1. Дерево Штейнера за 3t * Poly(n) состояний и времени.
      1. Состояние = [(A0, X1, X2), size, weight]
      2. A0 − не берем, X1 − слева от разреза, X2 − справа от разреза, всего троек (A0, X1, X2) 3t штук
      3. size ≤ n, wight ≤ 2n2, итого получили O(3tn2) состояний
      4. Переход в Join вершине: (A0, X1, X2) слева и справа одинаковы, переберем size1, weight1, size2, weight2
        (n6, но можно увидеть умножение многочленов, применить Фурье м будет n3logn). Итого время работы = O(3tn3logn)
    2. Гамильтоновы циклы и покрытия циклами
      1. Покрытие ориентированного графа циклам (in ≤ 1, out ≤ 1) за 4t = (2t)2 состояний и время 9t = (3t)2.
      2. Гамильтонов цикл в ориентированном графе за 2t4t * Poly(n) состояний и время 2t9t * Poly(n) (используем Cut & Count)
      3. Гамильтонов цикл в неориентированном графе за 2t3t * Poly(n) состояний и время 2t6t * Poly(n) (используем Cut & Count)
      4. Гамильтонов цикл в неориентированном графе за 3t * Poly(n) состояний и время 6t * Poly(n) (используем число ориентаций)