\Section{Паросочетания}{4 сентября}{Сергей Копелиович}

\Subsection{Определения}

\begin{Def}
Паросочетание (matching) -- множество попарно не смежных рёбер $M$.
\end{Def}
\begin{Def}
Вершинное покрытие (vertex cover) -- \\ множество вершин $C$, что у любого ребра хотя бы один конец лежит в $C$.
\end{Def}
\begin{Def}
Независимое множество (indpendent set) -- \\ множество попарно несмежных вершин $I$.
\end{Def}
\begin{Def}
Клика (clique) -- множество попарно смежных вершин.
\end{Def}
\begin{Def}
Совершенное паросочетание -- паросочетание, покрывающее все вершины графа.\\ 
В двудольном графе совершенным является паросочетание, покрывающее все вершины меньшей доли.
\end{Def}
\begin{Def}
Относительно любого паросочетания все вершины можно поделить на \\
$\bullet\ $ покрытые паросочетанием (принадлежащие паросочетанию), \\
$\bullet\ $ не покрытые паросочетанием (свободные).
\end{Def}

Обозначения: \red{M}atching (M), \red{V}ertex \red{C}over (VС или С), \red{I}ndependent \red{S}et (IS или I).

\Subsection{Сведения}

Пусть дан граф $G$, заданный матрицей смежности $g_{ij}$.
Инвертацией $G$ назовём граф $G'$, заданный матрицей смежности $g'_{ij} = 1 - g_{ij}$.
тогда независимое множество в $G$ задаёт клику в $G'$, а клика в $G$ задаёт независимое множество в $G'$.

\begin{Cons}
Задачи поиска max клики и max IS сводятся друг к другу.
\end{Cons}

\begin{Lm}
Дополнение любого VC -- IS. Дополнение любого IS -- VC.
\end{Lm}

\begin{Cons}
Все три задачи поиска min VC, max IS, max clique сводятся друг к другу.
\end{Cons}

\begin{Prop}
Задачи поиска min VC, max IS, max clique NP-трудны.
\end{Prop}
Утверждение было доказано в прошлом семестре в разделе про сложность.

\Subsection{Поиск паросочетания в двудольном графе}

\begin{Def}
Чередующийся путь -- простой путь, в котором рёбра чередуются в смысле принадлежности паросочетанию.
\end{Def}
\begin{Def}
Дополняющий чередующийся путь (ДЧП) -- чередующийся путь, первая и последняя вершина которого не покрыты паросочетанием.
\end{Def}
\begin{Lm}
Паросочетание $P$ максимально $\EQ$ $\not\exists$ ДЧП (лемма о дополняющем пути). 
\end{Lm}
\begin{proof}
Пусть $\exists$ ДЧП $\SO$ инвертируем все рёбра на нём, получим паросочетание размера $|P+1|$. 
Докажем теперь, что если $\exists$ паросочетание $M \colon |M| > |P|$, то $\exists$ ДЧП.
Для этого рассмотрим $S = M \triangledown P$.
Степень каждой вершины в $S$ не более двух (одно ребро из $M$, одно из $P$) $\SO$ $S$ является объединением циклов и путей. 
Каждому пути сопоставим число $a_i$ -- разность количеств рёбер из $M$ и $P$. Тогда $|M| = |P| + \sum_i a_i \SO \exists a_i > 0 \SO$ один
из путей -- ДЧП.  
\end{proof}

Лемма доказана для произвольного графа, но с лёгкостью найти ДЧП мы сможем только для двудольного графа.

\begin{Lm}
Пусть $G$ -- двудольный граф, а $P$ паросочетание в нём. Построим орграф $G'$, 
в котором из первой доли во вторую есть все рёбра $G$, а из второй в первую долю только рёбра из $P$.
Тогда есть биекция между путями в $G'$ и чередующимися путями в $G$.
\end{Lm}
\begin{Lm}
Поиск ДЧП в $G$ $\EQ$ поиску пути в $G'$ из свободной вершины в свободную.
\end{Lm}
\begin{Cons}
Мы получили алгоритм поиска максимального паросочетания $M$ за $\O(|M|\cdot E)$:
\begin{MyList}
\setcounter{enumi}{-1}
\item $P \leftarrow \varnothing$
\item Попробуем найти путь dfs-ом в $G'(G, P)$
\item \t{if} не нашли $\SO M$ максимально
\item \t{else goto 1}
\end{MyList}
\end{Cons}

\up
\Subsection{Реализация}

Важной идеей является применение ДЧП к паросочетания на обратном ходу рекурсии.
\begin{codep}
def dfs(v):
	used[v] = 1 # `массив пометок для вершин первой доли`
	for x in graph[v]: # `рёбра из 1-й доли во вторую`
		if (pair[x] == -1) or (used[pair[x]] == 0 and dfs(pair[x])):
			pair[x] = v # `массив пар для вершин второй доли`
			return True
	return False
\end{codep}
Граф $G'$  в явном виде мы нигде не строим. Вместо этого, когда идём из $1$-й доли во вторую, 
перебираем все рёбра (\t{v $\to$ x in graph[v]}), а когда из $2$-й в первую, идём только по ребру паросочетания (\t{x $\to$ pair[x]}).

\Subsection{Алгоритм Куна}

\up
\begin{Lm}
Если в процессе поиска максимального паросочетания не существует ДЧП из $v$, то ДЧП из $v$ уже никогда не появится.
\end{Lm}
\begin{proof}
Пусть появился ДЧП $v \leadsto u$ после применения ДЧП $a \leadsto b$, тогда в предыдущий момент существовал ДЧП из $v$ в $a$ или $b$.
(\TODO: картинка).
\end{proof}
Получили алгоритм Куна:
\begin{codep}
for v in range(n):
	used = [0] * n
	dfs(v)
\end{codep}

\pagebreak
\vspace*{-1.5em}
\Subsection{Оптимизации Куна}

Обозначим за $k$ размер максимального паросочетания.
Сейчас время работы алгоритма Куна $\O(VE)$ даже для $k = \O(1)$.
Будем обнулять пометки \t{used[]} только, если мы нашли ДЧП.
\begin{codep}
used = [0] * n
for v in range(n):
	if dfs(v):
		used = [0] * n
\end{codep}
Алгоритм остался корректным, так как, между успешными запусками \t{dfs} граф $G'$ не меняется.
И теперь работает за $\O(kE)$.

\down
Следующая оптимизация -- ``жадная инициализация''. До запуска Куна переберём все рёбра и те из них,
что можем, добавим в паросочетание.
\begin{Lm}
Жадная инициализация даст паросочетание размера $\ge \mfrac{k}{2}$.
\end{Lm}
\begin{proof}
Если мы взяли ребро, которое на самом деле не должно лежать в максимальном паросочетании $M$,
мы заблокировали возможность взять $\le 2$ рёбер из $M$.
\end{proof}
При использовании жадной инициализации у нас появляется необходимость поддерживать массив \t{covered[v]}, 
хранящий для вершины первой доли, покрыта ли она паросочетанием.

\down
Попробуем теперь сделать следующее:
\begin{codep}
used = [0] * n
for v in range(n):
	if not covered[v]:
		dfs(v)
\end{codep}
Код работает за $\O(V+E)$. И, если паросочетание не максимально, найдёт хотя бы один ДЧП.
А может найти больше чем один... в этом и заключается последняя оптимизация ``вообще не обнулять пометки'':
пока данный код находит хотя бы один путь, запускать его.

\begin{Rem}
Докажите, что если мы используем последнюю оптимизацию, ``жадная инициализация'' является полностью бесполезной.
\end{Rem}

Напоминание: мы умеем обнулять пометки за $\O(1)$. Для этого помеченной считаем вершины \t{v}: ``\t{used[v] == cc}'', тогда
операция ``\t{cc++}'' сделает все вершины не помеченными.

\Subsection{Поиск минимального вершинного покрытия}

\up
\begin{Lm}\label{lm:vcm}
$\forall M, VC$ верно, что $|VC| \ge |M|$ 
\end{Lm}
\begin{proof}
Для каждого ребра $e \in M$, 
нужно взять в $VC$ хотя бы один из концов $e$.
\end{proof}

Пусть у нас уже построено максимальное паросочетание $M$.
Запустим \t{dfs} на $G'$ из всех свободных вершин первой доли.
Обозначим первую долю $A$, вторую $B$. Посещённые \t{dfs}-ом вершины соответственно $A^{+}$ и $B^{+}$,
а непосещённые $A^{-}$ и $B^{-}$.

\begin{Thm}
$X = A^{-} \cup B^{+}$ -- минимальное вершинное покрытие.
\end{Thm}
\begin{proof}
Если бы из $a \in A^{+}$ было бы ребро в $b \in B^{-}$, мы бы по нему прошли, и $b$ лежала бы в $B^{+} \SO$
в $A^{+} \cup B^{-}$ нет рёбер $\SO X$ -- вершинное покрытие.
Оценим размер $X$: все вершины из $A^{-} \cup B^{+}$ -- концы рёбер паросочетания $M$, т.к. \t{dfs} не нашёл дополняющего пути.
Более того это концы обязательно разных рёбер паросочетания, т.к. если один конец ребра паросочетания лежит в $B^{+}$, то
\t{dfs} пойдёт по нему, и второй конец окажется в $A^{+}$. Итого $|X| \le |M|$.
Из этого и \autoref{lm:vcm} следует $|X| = |M|$ и $|X| = \max$.
\end{proof}
\begin{Cons}
$\red{A^{+} \cup B^{-}}$ -- максимальное независимое множество.
\end{Cons}
\begin{Rem}
Мы умеем строить $\min VC$ и $\max IS$ за $\O(V+E)$ при наличии максимального паросочетания.
\end{Rem}
\begin{Cons}
$\max M = \min VC$ (теорема Кёнига).
\end{Cons}

\up
\Subsection{Обзор решений}

Мы изучили алгоритм Куна со всеми оптимизациями.\\
Асимптотически время его работы $\O(VE)$, на практике же он жутко шустрый. \\
На графах $V, E \le 10^5$ решение укладывается в секунду.

\down
$\exists$ также алгоритм Хопкрофта-Карпа за $\O(EV^{1/2})$. 
Его мы изучим в контексте потоков.

\down
В регулярном двудольном графе можно найти совершенное паросочетание за время $\O(V \log V)$.
\href{http://theory.epfl.ch/kapralov/papers/match-linear.pdf}{Статья Михаила Капралова и ко.}

\down
\Subsection{Решения для произвольного графа}

\vspace*{-0.5em}
\Subsubsection{Обзор}

Наиболее стандартным считается решение через сжатие ``соцветий'' (видим нечётный цикл -- сожмём его, найдём паросочетание в новом цикле, разожмём цикл, перестроим паросочетание).
Этот подход используют реализации Габова за $\O(V^3)$ и Тарьяна за $\O(VE\alpha)$. Подробно эту тему мы будем изучать на 3-м курсе.

\down
Оптимальный по времени -- алгоритм Вазирани, $\O(EV^{1/2})$.

\down
Кроме этого есть два подхода, которые мы обсудим подробнее.

\Subsubsection{Матрица Татта}

Рассмотрим \href{http://e-maxx.ru/algo/tutte_matrix}{матрицу Татта} $T$.
Для каждого ребра $(i,j)$ элементы $t_{ij} = x_{ij}, t_{ji} = -x_{ij}$.  \\
Остальные элементы равны нулю. Здесь $x_{ij}$ -- переменные. \\
Получается, для каждого ребра неорграфа мы ввели ровно одну переменную. \\
$\det T$ -- многочлен от $n(n-1)/2$ переменных. \\
{\bf Теорема Татта}: $\det T \not\equiv 0 \EQ \exists$ совершенное паросочетание.\\
Чтобы проверить $\det T \equiv 0$, используем лемму Шварца-Зиппеля: в каждую переменную $x_{ij}$ подставим случайное значение, 
посчитаем определитель матрицы над полем $\mathbb{F}_{p}$, где $p = 10^9+7$, получим вероятность ошибки не более $n^2/p$.

Время работы $\O(n^3)$, алгоритм умеет лишь проверять наличие совершенного паросочетания.

Алгоритм можно модифицировать сперва для определения размера максимального паросочетания, а затем для его нахождения.

Пример: $n = 3, E = \{(1,2), (2,3)\}, 
T = \begin{bmatrix}
0 & x_{12} & 0 \\
-x_{12} & 0 & x_{23} \\
0 & -x_{23} & 0 \\
\end{bmatrix}$, подставляем $x_{12} = 9, x_{23} = 7$, считаем 
$\det \begin{bmatrix}
0 & 9 & 0 \\
-9 & 0 & 7 \\
0 & -7 & 0 \\
\end{bmatrix} = 0 \SO$ с большой вероятностью нет совершенного паросочетания. 

\Subsubsection{Читерский подход}

Давайте на недвудольном графе запустим dfs из Куна для поиска дополняющей цепи... 

При этом помечать, как посещённые, будем вершины обеих долей в одном массиве \t{used}.

С некоторой вероятностью алгоритм успешно найдёт дополняющий путь.

\down
\begin{tikzpicture}
	\node[circle, draw] (x1) at (0, 0) {\bf 1};
	\node[circle, draw] (x2) at (2, 0) {\bf 2};
	\node[circle, draw] (x3) at (4, 0) {\bf 3};
	\node[circle, draw] (x4) at (5.5, 1) {\bf 4};
	\node[circle, draw] (x5) at (5.5, -1) {\bf 5};
	\node[circle, draw] (x6) at (7, 0) {\bf 6};
	\draw (x1)--(x2);
	\draw (x3)--(x4);
	\draw (x3)--(x5);
	\draw (x4)--(x6);
	\draw[line width=1mm,red] (x2)--(x3);
	\draw[line width=1mm,red] (x4)--(x5);
	% \foreach \x/\y in {1/1, 1/3}
	% 	\fill (\x,\y) rectangle (\x+1,\y+1);
	% \foreach \x/\y/\n in {2/3/7, 0/3/8, 2/1/2}
	% 	\node[circle,draw] at (\x+0.5,\y+0.5) {$\n$};
\end{tikzpicture}

\down
Если мы запускаем dfs из вершины $1$, то у неё есть шанс найти дополняющий путь $1 \to 2 \to 3 \to 5 \to 4 \to 6$.
Но если из вершины $3$ dfs сперва попытается идти в $4$, то он пометит $4$ и $5$, как посещённые, больше в них заходить не будет, путь не найдёт.

Т.е. на данном примере в зависимости от порядка соседей вершины $3$ dfs или найдёт, или не найдёт путь. Если выбрать случайный порядок, то найдёт с вероятностью $1/2$.

Это лучше, чем ``при некотором порядке рёбер вообще не иметь возможности найти путь'', поэтому  первой строкой dfs добавляем \lstinline$random_shuffle(c[v].begin(), c[v].end())$.

\down
На большинстве графов алгоритм сможет найти максимальное паросочетание.
$\exists$ графы, на которых вероятность нахождения дополняющей цепи экспоненциально от числа вершин мала.
