Предистория
Недавно писал решение на свою задачу (ниже приложен мэшап, где она находится). Обычная задача на паросочетания, и в полученном графе очень быстро искалось максимальное паросочетание, что показалось мне странным (а также я не знаю как строго доказывать такую скорость) и поэтому я решил написать этот пост.
Краткая формулировка задачи
Дан ориентированный граф на $$$n$$$ вершинах и $$$m$$$ ребрах, нужно разбить граф на минимальное количество путей. Особенностью данного графа является то, что его диаметр $$$^\dagger$$$ можно оценить как $$$O(log(n))$$$.
$$$^\dagger$$$ Диаметром графа называется максимальное кратчайшее расстояние среди всех пар вершин.
Решение
Очевидно, что данная задача является учебной — нужно дублировать вершины и провести ребра графа в новом двудольном графе. Ответом будет $$$n - x$$$, где $$$x$$$ — максимальное паросочетание в получившемся двудольном графе.
Я приложу свой код алгоритма Куна, который содержит несколько оптимизаций.
int used[N];
int mt[N], timer = 1;
vector <int> g[N];
bool dfs (int u) {
if (used[u] == timer) return false;
used[u] = timer;
for (int v: g[u]) {
if (mt[v] == -1) {
mt[v] = u;
return true;
}
}
for (int v: g[u]) {
if (dfs(mt[v])) {
mt[v] = u;
return true;
}
}
return false;
}
// ...
int main () {
// ...
for (int i = 0; i < n; ++i) {
dfs(i);
timer++;
}
// ...
}
Оптимизации:
Хранение в массиве used значение timer'а, а не зануление used'ов каждый раз
При запуске сначала ищем свободную вершину во второй доле, а потом ищем удлиняющую цепочку.
Почему так быстро?
Казалось бы, при ограничениях $$$n = 10^5, m = 10^6$$$ Кун будет работать $$$O(n \cdot m)$$$, что очень долго. Но на реальном графе Кун работает ~$$$100$$$ мс.
Лично я не знаю, как доказывать такую асимптотику, но моя гипотеза, что у Куна есть ограничение на количество проделанных операций. И данное ограничение можно оценить как $$$O((n + m) \cdot d)$$$, где $$$d$$$ — диаметр графа.
Вот ссылка на мэшап, где можно протестировать Куна.
Интересно услышать ваше мнение насчёт данной гипотезы.
Всегда хотел услышать нормальное доказательство скорости работы Куна)
Когда ты в Куне запускаешься из каждой вершинки, в худшем случае пройдешь по всем ребрам, поэтому O(n*m).
Но я не знаю точно, здесь и внизу я написал свои догадки
Мы же в Куне запускаемся из каждой вершинки dfs-ом, максимальная глубина dfs здесь — log(n), поэтому асимптотика в этой задаче будет n*log(n)
А, извиняюсь, автор в посте про это и написал
Я не знаю, какое действительно время работы алгоритма от диаметра, но оценка точно не O(n * d), потому что можно выделить N / d полных двудольных компонент (диаметр будет очевидно <= d) где кажется, что алгоритм отработает за честные O(d^3), грубо получили оценку O(N * d^2)
Эхем, неочевидно, что такое диаметр несвязного графа, но в Вашем примере он, по-видимому, равен 1.
Я если что не говорю о том, что пример плохой, напротив, мне кажется, пример замечательный: он показывает, что на полном графе диаметр 1, а асимптотика алгоритма Куна там похожа на честные $$$O(n \cdot m)$$$, то есть предположение топикстартера не работает.
Извиняюсь, что добавил свой код позже, но буду ссылаться на него.
Из-за второй оптимизации, при заходе в каждую компоненту Кун не станет искать удлиняющие цепочки вообще, так как в полном графе всегда будет существовать ребро в нетронутую вершину из правой доли. Следовательно, на полном графе (или на графе из полных компонент) Кун будет работать за количество ребёр, то есть $$$O(m)$$$.
Полный граф был взят, как красивый пример, но почему такой алгоритм будет работать все еще за O(m), если я оставлю порядка O(n ^ 2) ребер, но случайных? Кажется, что это уже неочевидно
Вот про подобные вещи я и спрашиваю других, так как сам не могу придумать.
То, что вы не смогли придумать пример, на котором алгоритм работает долго не значит, что такого примера не существует.
Чтобы примерно представить насколько это бывает непросто, предлагаю почитать вот эти посты
https://codeforces.com/blog/entry/58048
https://codeforces.com/blog/entry/17023
От себя скажу, что все доказательства основанные на "диаметр же маленький, поэтому дфс будет работать быстро". Это банально неверно. Дфс всегда работал и будет работать за $$$O(n + m)$$$.
Вроде, если запускать не Куна, а Хопкрофта-Карпа, то должно быть реально $$$O((n + m) * d)$$$ при маленьких d, потому что Хопкрофт-Карп на каждой итерации увеличивает длину кратчайшего удлиняющего пути, ну а она не может стать больше d, значит и итераций должно быть <= d.
Интересно. Это больше похоже на правду, чем остальные предположения пока что.
Ну а я очень сомневаюсь что удлиняющие пути будут длины <= d :)
Когда ребра становятся насыщенными, диаметр графа может увеличиваться, так что итераций может быть больше.
Автокомментарий: текст был обновлен пользователем AndreyPavlov (предыдущая версия, новая версия, сравнить).
Вроде бы, это неверно. Если мне не изменяет память, если разбить обе доли на две компоненты (Назовем $$$U_1, U_2$$$ и $$$V_1, V_2$$$ соответственно), между компонентами с одинаковыми номерами построить паросочетания, а на $$$U_1, V_2$$$ построить полный двудольный граф и после этого правильно занумеровать вершины, то Кун будет работать за $$$\widetilde{\Omega}(n^3)$$$, при $$$d = O(1)$$$ и $$$m = O(n^2)$$$. Все становится гораздо интереснее, если граф предварительно пошаффлить. Кажется, этому примеру это не мешает, но в общем случае оценки лучше, чем $$$\widetilde{\Omega}(m \sqrt{m})$$$ я не знаю, и, честно говоря, верю, что $$$\widetilde{O}(m \sqrt{m})$$$ верно для всех связных графов (тут уже в смысле матожидания времени работы, конечно). Во всяком случае, с экспериментами на случайных графах это сходится, да и для практических применений оценка тоже весьма реалистичная.
Да, безусловно, оценивать Куна через функцию только от $$$m$$$ гораздо интереснее, потому что $$$m$$$ — это и есть наш размер входа, как правило.
Вообще, точной оценкой разных версий Куна в коммьюнити интересуются довольно давно, к двум ссылкам в одном из соседних комментариев я могу разве что добавить еще один наш вопрос на stackexchange, где рассказано много всего интересного, но ответа на самый главный вопрос так и нет.
Естественно, всех, кто узнает что-то лучшее, чем описанное на stackexchange, я активно призываю связываться со мной и об этом рассказывать, потому что мне (и не только мне) тоже очень интересно.