Сколько непересекающихся сокращений кромок должно иметь DAG?

10

Следующий вопрос связан с оптимальностью алгоритма динамического программирования Беллмана-Форда - кратчайшего пути (см. Этот пост для связи). Кроме того, положительный ответ будет означать, что минимальный размер монотонной недетерминированной программы ветвления для задачи STCONN равен . t Θ ( n 3 )stΘ(n3)

Пусть - DAG (направленный ациклический граф) с одним исходным узлом и одним целевым узлом . - разрез представляет собой множество ребер, удаление которого уничтожает все - пути длины ; мы предполагаем, что в есть такие пути . Обратите внимание, что более короткие - пути не должны быть уничтожены.S T KGstkt k G s tstkGst

Вопрос: Имеют ли G должен иметь по крайней мере (о) k непересекающемуся k -cuts?

Если нет s - t путей короче k , ответ ДА, потому что у нас есть следующий известный факт минимума-максимума (двойственный к теореме Менгера ), приписываемый Robacker . s - t разреза является k Обрежьте для k=1 (уничтожает все s - t путей).

Факт: В любом ориентированном графе максимальное число отрезков s - пересекающихся с ребрами, tравно минимальной длине пути s - t .

Обратите внимание, что это верно, даже если граф не является ациклическим.

Доказательство: тривиально, минимум - это, по крайней мере, максимум, поскольку каждый путь - t пересекает каждый разрез s - t на ребре. Чтобы увидеть равенство, пусть d ( u ) - длина кратчайшего пути от s до u . Пусть U r = { u : d ( u ) = r } , для r = 1 , , d ( t ) и пусть E rststd(u)suUr={u:d(u)=r}r=1,,d(t)Erбыть набором ребер, оставляющих . Ясно, что множества E r не пересекаются, поскольку множества U r таковы. Итак, осталось показать, что каждый E r является s - t разрезом. Чтобы показать это, возьмем произвольный путь s - t p = ( u 1 , u 2 , , u m ) с u 1 = s и u m = t . С дUrErUrErststp=(u1,u2,,um)u1=sum=t , последовательность расстояний d ( u 1 ) , , d ( u m ) должна достичь значения d ( u m ) = d ( t ) , начиная с d ( u 1 ) = d ( s ) = 0 и увеличение значения не более чем на 1d(ui+1)d(ui)+1d(u1),,d(um)d(um)=d(t)d(u1)=d(s)=01на каждом этапе. Если некоторое значение уменьшается, то мы должны достичь значения d ( u i ) последнего. Таким образом, должен быть j, где происходит переход от d ( u j ) = r к d ( u j + 1 ) = r + 1 , то есть ребро ( u j , u j + 1 ) принадлежит E r , так как желательно. QED d(ui)d(ui)jd(uj)=rd(uj+1)=r+1(uj,uj+1)Er

Но что, если есть также более короткие (чем ) пути? Любая подсказка / ссылка? k


Дж. Т. Роккер, теоремы Мин-Макса о кратчайших цепях и непересекающихся разрезах сети, исследовательский меморандум RM-1660, RAND Corporation, Санта-Моника, Калифорния, [12 января] 1956 г.
РЕДАКТИРОВАТЬ (день спустя): С помощью короткого и очень приятного аргумента Дэвид Эппштейн ответил на первоначальный вопрос выше отрицательно : полный DAG ( переходный турнир ) не может иметь более четырех непересекающихся k -четов! Фактически он доказывает следующий интересный структурный факт, для k о Tnkk . Разрез являетсячистым,если он не содержит ребер, инцидентныхsилиt.nst

Каждый чистый разрез в T n содержит путь длины k . kTnk

Это, в частности, означает, что каждые два чистых разреза должны пересекаться! Но, возможно, все еще есть много чистых k- сокращений, которые не перекрывают «слишком много». Отсюда и смягченный вопрос (последствия для STCONN будут такими же ):kk

Вопрос 2: Если каждый чистый разрез имеет M ребер, то должен ли граф иметь около Ω ( k M ) ребер? kMΩ(kM)

Связь со сложностью STCONN проистекает из результата Эрдеша и Галлая, что нужно удалить все, кроме ребер из (неориентированного) K m , чтобы уничтожить все пути длины k . (k1)m/2Kmk


РЕДАКТИРОВАТЬ 2: Теперь я задал вопрос 2 в Mathoverflow .

Стасис
источник

Ответы:

9

Краткий ответ: нет.

Пусть - полный DAG (транзитивный турнир) на n вершинах с s и t его источником и стоком, и пусть k = Gnst . Заметьте, что может быть не более четырех непересекающихся разрезов, которые содержат больше чемn/3ребер, падающих наs,или больше чемn/3ребер, падающих наt. Итак, если должно быть много непересекающихся разрезов, мы можем предположить, что существует разрезC, который не содержит большого числа ребер, инцидентныхsиt.k=n/3n/3sn/3tCst

Пусть теперь будет полный подграф , индуцированный в G с множеством вершин х таким образом, что ребра ы х и х т не принадлежат C . Число вершин в X не менее n / 3 , потому что в противном случае C коснется слишком большого количества ребер, инцидентных s или t . Однако X C не может содержать k- путь, потому что если такой путь существует, его можно объединить с s и t, чтобы сформировать длинный путь в GXGxsxxtCXn/3CstXCkst . Следовательно,многослойное слоение X C имеет меньше k слоев и имеет слой, содержащий более ( n / 3 ) / k = k вершин. Поскольку это слой с самым длинным слоем пути, он не зависит от X C и поэтому завершен в C , поэтому C содержит путь P через вершины этого слоя длины k . Этот путь должен отличаться от всех других путей.GCXCk(n/3)/k=kXCCCPk

Каждый разрез, который не является должен содержать либо ребро от s до начала пути P, либо ребро от конца пути P до t , иначе он не будет блокировать путь s - P - t . Таким образом, если C существует, может быть не более трех непересекающихся разрезов. И если C не существует (то есть, если все разрезы покрывают более n / 3 ребер, инцидентных s или t ), может быть не более четырех непересекающихся разрезов. В любом случае, это намного меньше, чем k сокращений.CsPPtsPtCCn/3stk

Дэвид Эппштейн
источник
@ Дэвид: Интересный аргумент (хотя я еще не совсем понял: почему C должен иметь k-путь). Но где аргумент терпит неудачу (он должен), если все st пути длинные, длиной не менее k?
Стасис
1
@Stasys: G - турнир, доказательство использует этот факт, так что, по-моему, именно поэтому он потерпит неудачу.
domotorp
@domotorp: спасибо, я действительно пропустил слово «завершить». Я пока не могу найти недостаток, но это было бы довольно противоречивым фактом: даже если в ациклическом турнире много k-путей, мы не можем выбрать много непересекающихся систем их представителей (ребер).
Стасис
@ Дэвид: На самом деле, чтобы иметь упомянутые последствия, мы можем допустить, чтобы срезы были только «почти непересекающимися», то есть могли иметь общие ребра, инцидентные s или t (у нас есть только 2n этих специальных ребер). Реальная цель - показать, что G должно иметь около kN ребер, если мы знаем, что каждый «чистый» k-разрез (без этих специальных ребер) должен иметь N ребер. Может ли ваш (очень хороший, как я теперь вижу) аргумент быть изменен в этой (почти непересекающейся) ситуации?
Стасис
2
Если вы разрешите разрезам совместно использовать ребра, инцидентные s или t, то почему вы не можете сделать так, чтобы все разрезы состояли точно из набора ребер, инцидентных s? С другой стороны, мой аргумент показывает, что (с его выбором и k ) может быть только один чистый разрез. Gk
Дэвид Эппштейн