Участник:Siziyman

Тут будет черновичок конспекта, который вовремя сдан не был.

Задача о количестве полных подграфов в графе

Дан граф [math]G[/math], в котором [math]N[/math] вершин. Требуется подсчитать количество полных подграфов графа [math]G[/math] (такие подграфы также называются кликами — clique).

1. Наивное решение - перебор всех возможных подграфов и проверка для каждого, что он является кликой, сложность - [math]O(2^N \times N^2)[/math]

2. Этот алгоритм можно улучшить до [math]O(2^N)[/math]. Для этого нужно в функции перебора хранить маску вершин, которые мы ещё можем добавить. Поддерживая эту маску, можно добавлять только «нужные» вершины, и тогда не нужно будет в конце проверять подграф на то что он — клика. Добавлять вершину можно за [math]O(1)[/math], используя побитовое «и» текущей маски и строчки матрицы смежности добавляемой вершины.

Решение с meet-in-the-middle

Разбиваем граф [math]G[/math] на 2 графа [math]{G}_1[/math] и [math]{G}_2[/math] по [math]N/2[/math] вершин. Находим за [math]O(2^{N/2})[/math] все клики в каждом из них.

Теперь надо узнать для каждой клики графа [math]{G}_1[/math] количество клик графа [math]{G}_2[/math], таких, что их объединение — клика. Их сумма и есть итоговый ответ.

Для одной клики [math]K[/math] графа [math]{G}_1[/math] может быть несколько подходящих клик в [math]{G}_2[/math]. О клике [math]K[/math] мы "знаем" только маску вершин графа [math]{G}_2[/math], которые ещё можно добавить. Для каждой такой маски в [math]{G}_2[/math] нужно предподсчитать ответ. С помощью динамического программирования предподсчитаем для каждой маски вершин графа [math]{G}_2[/math] количество клик, вершины которой являются подмножеством выбранной маски. Количество состояний - [math]2^{N/2}[/math]. Количество переходов:[math]N[/math] . Асимптотика - [math]O(2^{N/2} \times N)[/math].

Для каждой клики [math]K[/math] (в том числе и пустой) графа [math]{G}_1[/math] прибавим к глобальному ответу предподсчитанное количество клик, которые можно добавить к [math]K[/math] (В том числе и пустых). Асимптотика: [math]O(2^{N/2})[/math].

Псевдокод подсчёта ответа:

for mаsk = 0 to (1 << N)
  dp[mask] = 1 + sum( [p[mask & matrix[i]  for i = 0 to N if ((mask & ( 1 << i )) > 0))
ans = sum(dp[clique1_mask[i]])

Итоговая сложность: [math]O(2^{N/2} \times N)[/math]