Следующий вопрос связан с оптимальностью алгоритма динамического программирования Беллмана-Форда - кратчайшего пути (см. Этот пост для связи). Кроме того, положительный ответ будет означать, что минимальный размер монотонной недетерминированной программы ветвления для задачи STCONN равен . t Θ ( n 3 )
Пусть - DAG (направленный ациклический граф) с одним исходным узлом и одним целевым узлом . - разрез представляет собой множество ребер, удаление которого уничтожает все - пути длины ; мы предполагаем, что в есть такие пути . Обратите внимание, что более короткие - пути не должны быть уничтожены.S T Kt ≥ k G s t
Вопрос: Имеют ли должен иметь по крайней мере (о) непересекающемуся -cuts?
Если нет - путей короче , ответ ДА, потому что у нас есть следующий известный факт минимума-максимума (двойственный к теореме Менгера ), приписываемый Robacker . - разреза является Обрежьте для (уничтожает все - путей).
Факт: В любом ориентированном графе максимальное число отрезков - пересекающихся с ребрами, равно минимальной длине пути - .
Обратите внимание, что это верно, даже если граф не является ациклическим.
Доказательство: тривиально, минимум - это, по крайней мере, максимум, поскольку каждый путь - t пересекает каждый разрез s - t на ребре. Чтобы увидеть равенство, пусть d ( u ) - длина кратчайшего пути от s до u . Пусть U r = { u : d ( u ) = r } , для r = 1 , … , d ( t ) и пусть E rбыть набором ребер, оставляющих . Ясно, что множества E r не пересекаются, поскольку множества U r таковы. Итак, осталось показать, что каждый E r является s - t разрезом. Чтобы показать это, возьмем произвольный путь s - t p = ( u 1 , u 2 , … , u m ) с u 1 = s и u m = t . С д , последовательность расстояний d ( u 1 ) , … , d ( u m ) должна достичь значения d ( u m ) = d ( t ) , начиная с d ( u 1 ) = d ( s ) = 0 и увеличение значения не более чем на 1на каждом этапе. Если некоторое значение уменьшается, то мы должны достичь значения d ( u i ) последнего. Таким образом, должен быть j, где происходит переход от d ( u j ) = r к d ( u j + 1 ) = r + 1 , то есть ребро ( u j , u j + 1 ) принадлежит E r , так как желательно. QED
Но что, если есть также более короткие (чем ) пути? Любая подсказка / ссылка?
Дж. Т. Роккер, теоремы Мин-Макса о кратчайших цепях и непересекающихся разрезах сети, исследовательский меморандум RM-1660, RAND Corporation, Санта-Моника, Калифорния, [12 января] 1956 г.
РЕДАКТИРОВАТЬ (день спустя): С помощью короткого и очень приятного аргумента Дэвид Эппштейн ответил на первоначальный вопрос выше отрицательно : полный DAG ( переходный турнир ) не может иметь более четырех непересекающихся k -четов! Фактически он доказывает следующий интересный структурный факт, для k о √ . Разрез являетсячистым,если он не содержит ребер, инцидентныхsилиt.
Каждый чистый разрез в T n содержит путь длины k .
Это, в частности, означает, что каждые два чистых разреза должны пересекаться! Но, возможно, все еще есть много чистых k- сокращений, которые не перекрывают «слишком много». Отсюда и смягченный вопрос (последствия для STCONN будут такими же ):
Вопрос 2: Если каждый чистый разрез имеет ≥ M ребер, то должен ли граф иметь около Ω ( k ⋅ M ) ребер?
Связь со сложностью STCONN проистекает из результата Эрдеша и Галлая, что нужно удалить все, кроме ребер из (неориентированного) K m , чтобы уничтожить все пути длины k .
РЕДАКТИРОВАТЬ 2: Теперь я задал вопрос 2 в Mathoverflow .