Предистория

Недавно писал решение на свою задачу (ниже приложен мэшап, где она находится). Обычная задача на паросочетания, и в полученном графе очень быстро искалось максимальное паросочетание, что показалось мне странным (а также я не знаю как строго доказывать такую скорость) и поэтому я решил написать этот пост.

Краткая формулировка задачи

Дан ориентированный граф на $$$n$$$ вершинах и $$$m$$$ ребрах, нужно разбить граф на минимальное количество путей. Особенностью данного графа является то, что его диаметр $$$^\dagger$$$ можно оценить как $$$O(log(n))$$$.

$$$^\dagger$$$ Диаметром графа называется максимальное кратчайшее расстояние среди всех пар вершин.

Очевидно, что данная задача является учебной — нужно дублировать вершины и провести ребра графа в новом двудольном графе. Ответом будет $$$n - x$$$, где $$$x$$$ — максимальное паросочетание в получившемся двудольном графе.

Почему так быстро?

Казалось бы, при ограничениях $$$n = 10^5, m = 10^6$$$ Кун будет работать $$$O(n \cdot m)$$$, что очень долго. Но на реальном графе Кун работает ~$$$100$$$ мс.

Лично я не знаю, как доказывать такую асимптотику, но моя гипотеза, что у Куна есть ограничение на количество проделанных операций. И данное ограничение можно оценить как $$$O((n + m) \cdot d)$$$, где $$$d$$$ — диаметр графа.

Вот ссылка на мэшап, где можно протестировать Куна.

Интересно услышать ваше мнение насчёт данной гипотезы.