%\author{Савон Юлия}
%\date{18 марта 2016}
\Section{Max independent set, min cover}{24 марта}{Савон Юлия}

\THE{Обозначения:}

{\bf$M$} -- matching, паросочетание (множество попарно не смежных рёбер).

{\bf$C$} -- cover, вершинное покрытие или контролирующее множество (множество вершин таких, что для любого ребра хотя бы один конец лежит в множестве).

{\bf$I$} -- independent set, независимое множество (множество вершин таких, что никакие две из них не соединены ребром).

\Subsection{Алгоритм за $\O(V + E)$}

Cчитаем, что нам уже дано максимальное паросочетание $M$. 
Задача: найти максимальное независимое множество, минимальное вершинное покрытие.
Запустим на имеющемся графе dfs из всех вершин первой доли, из которых не исходит ни одного ребра максимального паросочетания.
Назовём помеченные вершины из первой доли $A^{+}$, помеченные вершины из второй доли $B^{+}$, а непомеченные соответственно $A^{-}$ и $B^{-}$.

\THE{Утверждение:} из этих групп мы можем получить всю нужную информацию.

\vspace*{-0.5em}
$$\bf { I_{max} = A^{+} \cup B^{-} }$$
$$\bf { C_{min} = A^{-} \cup B^{+} }$$

\underline{Часть нужная с точки зрения ``закодить задачу'' закончилась.} 

\Subsection{Корректность алгоритма} 

\begin{Lm}\label{Lm:maxMminC} $\max |M| \le \min |C|$ \end{Lm}
\begin{proof}
  Рассмотрим любые паросочетание $M$, вершинное покрытие $C$. \\
  У каждого ребра $M$ один конец должен лежать в $C$, получили $\forall M, C \colon |M| \le |C|$.
\end{proof}

\begin{Lm} $A^{+} \cup B^{-}$ -- независимое, $A^{-} \cup B^{+}$ -- cover \end{Lm}
\begin{proof}
Независимость $A^{+} \cup B^{-}$: пусть есть ребро между $a \in A^{+}$ и $b \in B^{-}$, тогда \t{dfs}
бы прошёл по нему, получается $b \in B^{+}$. $A^{-} \cup B^{+}$ -- cover, как дополнение независимого.
\end{proof}

\begin{Lm}\label{Lm:findCover} $A^{-} \cup B^{+} = |M|$ \end{Lm}
%Т.к. это концы рёбер, в одном случае мы не заходили в $A^{-}$ т.к. они имеют исходящее выбранное ребро. 
%И из каждого $B^{+}$ тоже есть(если нет, то мы получаем цепочку нечётной длины, у которой концы не имёют рёбер, такого бы нам Кун не позволил), 
%они не ведут в $A^{-}$, иначе бы они были в $A^{+}$.
%Так же не бывает рёбер из $A^{+}$ в $B^{-}$
%Таким образом это покрывающее множество с количеством элементов равным количеству рёбер в максимальном паросочетании.
\begin{proof}\hspace*{1em}\\
Вершина из $A^{-}$ -- конец ребра паросочетания.\\
Вершина из $B^{+}$ -- конец ребра паросочетания.\\
Между $A^{-}$ и $B^{+}$ нет ребер из паросочетания: ребро паросочетания или $\q{A^{+}, B^{+}}$, или $\q{A^{-}, B^{-}}$.\\
Получили $A^{-} \cup B^{+} \le |M|$. Поскольку $A^{-} \cup B^{+}$ -- cover, применяем \autoref{Lm:maxMminC}, получаем равенство.
\end{proof}

\begin{Thm} \emph{Кёнига.} $\max |M| = \min |C|$ \end{Thm} 
\begin{proof}
В лемме \autoref{Lm:findCover} мы предъявили вершинное покрытие равный максимальному паросочетанию.
По \autoref{Lm:maxMminC} это вершинное покрытие минимально.
\end{proof}

\THE{Следствие:} заодно доказали, что $A^{-} \cup B^{+}$ -- минимальное вершинное покрытие.

\THE{Следствие:} $A^{+} \cup B^{-}$ -- максимальное независимое множество, как дополнение покрытия.

\Subsection{Всяческие ускорения алгоритма Куна}

\THE{Обычный Кун}

Асимптотика $\O(VE)$

\lstinputlisting{savon/easy_kun.cpp} 

\THE{Кун$^{\t{+}}$}

Асимптотика $\O(V + |M| \cdot E)$

\lstinputlisting{savon/up_kun.cpp}

Он обнуляет пометки вершин только, если мы нашли дополняющий чередующийся путь.
%, в противном случае в эту ветку бесполезно идти, там точно не будет интересующего нас куска.

\THE{Быстрое обнуление массива за $\O(1)$:} 
нам лень бегать и обнулять весь массив, поэтому заведём число которое будет отвечать за ``обнулённость'',
увеличивать его каждый раз когда должны были обнулить массив, сравнивать с ним и присваивать его.

\THE{Жадная инициализация}
 
\lstinputlisting{savon/up_up_kun.cpp}
 
Таким образом мы сразу же нашли паросочетание размера хотя бы $\frac{1}{2} |M_{max}|$

Далее запускаем алгоритм Кун$^{\t{+}}$, который теперь работает в 2 раза быстрее.
 
\THE{И ещё одна оптимизация Куна}
 
Асимптотика тоже $\O(|M|E)$, но работает ещё быстрее, так как за 1-ю итерацию нашли сразу 
хотя бы $\frac{1}{2} |M_{max}|$ рёбер паросочетания. На каждой новой итерации находим хотя бы \t{+1} ребро, возможно, больше.
 
\lstinputlisting{savon/up3_kun.cpp}
 
% пометки обнуляем или используем \textbf{фишку} перед каждой итерацией
 