Максимальное независимое множество и минимальное покрытие путями в двудольном графе через паросочетание
Две связанные задачи, которые, говорят, решаются через паросочетание в двудольном графе: (1) максимальное независимое множество вершин; (2) минимальное число путей, покрывающих все вершины DAG (path cover). Как они сводятся к паросочетанию и какие тут формулы?
2 ответа
Обе задачи опираются на König и max-matching.
(1) Максимальное независимое множество в двудольном графе. В двудольном графе (и только в нём — в общем NP-трудно): $$|\text{макс. независимое}| = |V| - |\text{макс. паросочетание}|.$$ Это прямое следствие 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$.
Тогда: $$|\text{мин. покрытие путями}| = (\text{число вершин}) - |M|.$$
Интуиция: каждое ребро паросочетания «склеивает» два пути в один, сокращая их число на 1. Изначально $V$ путей (по одной вершине), и каждое ребро $M$ уменьшает счётчик.
Важно: эта формула — для вершинно-непересекающихся путей в DAG. Для путей, которые могут делить вершины, нужно сначала транзитивно замкнуть граф. Асимптотика — стоимость паросочетания, $O(VE)$ Куном или $O(E\sqrt{V})$ Хопкрофтом-Карпом.
Уточнение к path cover, на котором часто ошибаются: формула $V - M$ верна для минимального покрытия вершинно-непересекающимися путями. Если же разрешено покрывать вершину несколькими путями (пути могут пересекаться) — задача меняется: нужно построить транзитивное замыкание DAG (добавить ребро $u\to w$, если есть путь $u\rightsquigarrow w$), и уже на нём считать паросочетание. Без замыкания вы решаете задачу про непересекающиеся пути. Внимательно читайте условие: «пути не пересекаются по вершинам» или «можно пересекаться» — это два разных ответа.