Максимальное независимое множество и минимальное покрытие путями в двудольном графе через паросочетание

Обе задачи опираются на König и max-matching.

(1) Максимальное независимое множество в двудольном графе. В двудольном графе (и только в нём — в общем NP-трудно):

Это прямое следствие König: максимальное независимое множество = дополнение минимального вершинного покрытия, а $|\text{мин. покрытие}| = |\text{макс. паросочетание}|$. Само множество восстанавливается как $V \setminus (\text{вершинное покрытие из конструкции König})$.

(2) Минимальное покрытие путями DAG (minimum path cover). Нужно покрыть все вершины ориентированного ациклического графа минимальным числом вершинно-непересекающихся путей. Сводим так:

• Каждую вершину $v$ дублируем: $v_{out}$ в левой доле, $v_{in}$ в правой.
• Ребро $u\to v$ исходного DAG → ребро $u_{out} - v_{in}$ в двудольном графе.
• Считаем максимальное паросочетание $M$.

Тогда:

Интуиция: каждое ребро паросочетания «склеивает» два пути в один, сокращая их число на 1. Изначально $V$ путей (по одной вершине), и каждое ребро $M$ уменьшает счётчик.

Важно: эта формула — для вершинно-непересекающихся путей в DAG. Для путей, которые могут делить вершины, нужно сначала транзитивно замкнуть граф. Асимптотика — стоимость паросочетания, $O(VE)$ Куном или $O(E\sqrt{V})$ Хопкрофтом-Карпом.