Интересная гипотеза об асимптотике Куна

Правка ru5, от AndreyPavlov, 2023-01-12 10:22:24

Предистория

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

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

Дан ориентированный граф на $$$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$$$ — диаметр графа.

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

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

Теги алгоритм куна, скорость, почему так?, асимптотика, паросочетания, быстродействие

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru5 Русский AndreyPavlov 2023-01-12 10:22:24 845 Мелкая правка: 'n~~~~~\n\nОптимизаци' -> 'n~~~~~\n\n#### Оптимизаци'
ru4 Русский AndreyPavlov 2023-01-12 10:12:54 6 Мелкая правка: 'ть как $O(n \cdot d)$' -> 'ть как $O((n + m) \cdot d)$'
ru3 Русский AndreyPavlov 2023-01-11 21:39:13 2
ru2 Русский AndreyPavlov 2023-01-11 21:36:55 0 (опубликовано)
ru1 Русский AndreyPavlov 2023-01-11 21:36:00 1577 Первая редакция (сохранено в черновиках)