Классическая и эффективная схема для поиска минимального вершинного покрытия в двудольном графе основана на теореме Кёнига: в двудольном графе мощность минимального вершинного покрытия равна мощности максимального паросочетания. Поэтому алгоритм:

1) Найти максимальное паросочетание M.
2) Построить из него минимальное вершинное покрытие C методом «альтернативных путей» (стандартная процедура).
3) Вернуть C — это минимальное покрытие.

Далее — подробности, доказательство корректности и оценка сложности.

Описание алгоритма

Обозначения: левое множество L (|L| = 1000), правое R (|R| = 1000), ребра E (|E| = 10000). Пусть M — найденное максимальное паросочетание (сопоставления между L и R).

Шаг A. Найти максимальное паросочетание.

Используйте алгоритм Хопкрофта–Карпа (Hopcroft–Karp). Он работает на двудольном графе и находит максимальное паросочетание за время O(E √V), где V = |L| + |R|.

Шаг B. Построить множество достижимых вершин Z по «альтернативным» путям.

Пусть U — множество вершин L, не покрытых паросочетанием M (неспаренные вершины слева).Построим ориентированный «альтернативный» граф для поиска в ширину/глубину:
Из любой вершины l ∈ L можно переходить по ребру (l,r) только если (l,r) ∉ M (не в паросочетании).Из любой вершины r ∈ R можно переходить по ребру (r,l) только если (l,r) ∈ M (т.е. переход «по паре» в обратную сторону).Выполним BFS/DFS начиная из всех вершин U одновременно и найдем множество достижимых вершин Z (включает некоторые вершины из L и R).

Шаг C. Построить покрытие C:

C = (L \ Z) ∪ (R ∩ Z).

Это и есть минимальное вершинное покрытие.

Доказательство корректности (связь с теоремой Кёнига)

Теорема Кёнига: в двудольном графе размер минимального вершинного покрытия равен размеру максимального паросочетания.

Доказательство правильности построения C (стандартный аргумент):

C покрывает все ребра. Возьмём любое ребро (l,r).

Если l ∈ Z, то по конструкции обхода из l все его непарные (не в M) соседние правые вершины попадают в Z (поскольку из l разрешены переходы по непарным ребрам), а если (l,r) ∈ M то r попадает в Z потому, что по парному ребру мы переходим с r в l при построении Z (в обратную сторону) — более формально: невозможно иметь l ∈ Z и r ∉ Z для ребра (l,r), иначе был бы контрпример достижимости. Значит либо l ∉ Z, либо r ∈ Z, и тогда (L \ Z) ∪ (R ∩ Z) содержит хотя бы одну из концов ребра.Следовательно C — вершнoe покрытие.

|C| = |M|. Покажем, что каждое ребро из M имеет ровно одну вершину в C:

Для парного ребра (l,r) ∈ M верно, что ровно один из l, r принадлежит C: если l ∉ Z, то l ∈ L \ Z ⊆ C; если l ∈ Z, то, как показано, тогда r ∈ Z, и потому r ∈ R ∩ Z ⊆ C, а l ∉ L \ Z. Значит для каждой парной пары ровно один endpoint в C. Таким образом |C| = |M|.

Так как |C| = |M| и M — максимальное паросочетание, то C — минимальное вершинное покрытие (по теореме Кёнига).

Оценка сложности и практические замечания

Поиск максимального паросочетания Hopcroft–Karp: временная сложность O(E √V), где V = |L| + |R|. Для ваших чисел:
V = 2000, √V ≈ 44.7, E = 10000 → теоретически ≈ 10000 · 44.7 ≈ 4.47·10^5 «единиц работы» (величина даёт порядок, а не точное время).На практике в высокоуровневых языках (Python) такой граф решается за доли секунды — единицы секунд в худшем случае; в C++ обычно — миллисекунды–десятки миллисекунд (всё зависит от констант и реализации).Построение множества достижимых вершин Z: один BFS/DFS по ориентированному альтернативному графу — O(E) времени и O(V) памяти.Итого суммарно: O(E √V + E) = O(E √V) асимптотически. Для ваших размеров это очень эффективно.

Память:

Хранение списка смежности: O(E).Массивы пар (парное соответствие для L и R), пометки visited/dist: O(V).Для E = 10000 и V = 2000 это минимальное требование (порядок десятков тысяч элементов), легко укладывается в память.

Реализация — практические советы

Использовать списки смежности.Хопкрофта–Карп: массив pairU (для L), pairV (для R), dist для BFS уровней; реализовать стандартные BFS/DFS функции.После получения pairU/pairV строите список U (несопоставленные в L) и запускаете BFS по направленным правилам (нечётные/чётные переходы как описано).Результат C строите как (все l ∈ L, у которых visited[l] == false) ∪ (все r ∈ R, у которых visited[r] == true).

Альтернативы

Можно решать через max-flow (исток → L → R → сток) и алгоритм Dinic; для двудольной задачи Hopcroft–Karp обычно проще и быстрее.Если графы очень разреженные/малые — даже простой DFS-поиск увеличивающих путей (алгоритм Форда–Фалкерсона для паросочетаний) может сработать, но в худшем случае он медленнее.

Вывод

Алгоритм: Hopcroft–Karp для max matching + построение покрытия через множества достижимых вершин по альтернативным путям.Корректность обусловлена теоремой Кёнига; конструкция гарантированно даёт покрытие размера |M|, значит минимальное.Временная сложность O(E √V), для ваших чисел ≈ O(10000·√2000) — очень эффективно на практике.