Насколько дорого может быть уничтожение всех длинных путей в DAG?

14

Мы рассматриваем DAG (ориентированные ациклические графы) с одним исходным узлом s и одним целевым узлом t ; допускаются параллельные ребра, соединяющие одну и ту же пару вершин. - разрез представляет собой набор ребер, удаление уничтожает все - пути по длиннее , чем ; более короткие - пути, а также длинные «внутренние» пути (не между и ) могут выжить!ы т к ы т ы тkstkstst

Вопрос: Достаточно ли удалить не более части ребер из DAG, чтобы уничтожить все - пути, длина которых превышает ? 1/kstk

То есть, если обозначает общее число ребер в , то каждый делает ДАГ Пользователю A Обрежьте с не более чем приблизительно ребер? Два примера:e(G)GGke(G)/k

  1. Если все - пути имеют длину , то существует разрез с ребрами. Это верно, потому что тогда должно быть непересекающихся -узлов: просто наслоите узлы соответствии с их расстоянием от исходного узла . st>kke(G)/kkkGs
  2. Если представляет собой переходный турнир (полный DAG), а затем также Обрежьте с ребро существует: фиксирует топологическое упорядочение из узлы, разбить узлы на последовательных интервалов длины и удалить все ребра, соединяющие узлы одного и того же интервала; это уничтожит все - пути больше чем . G=Tnkk(n/k2)e(G)/kkn/kstk

Замечание 1: Наивной попыткой дать положительный ответ (который я также попробовал первым) было бы попытаться показать, что каждый DAG должен иметь около непересекающихся -сечений. К сожалению, пример 2 показывает, что эта попытка может потерпеть неудачу: с помощью хорошего аргумента Дэвид Эппштейн показал, что для about граф не может иметь более четырех непересекающихся -сечений! k k k kk TnknTn k

Замечание 2: Важно, чтобы разрез должен был только уничтожить все длинные - пути, а не обязательно все длинные. А именно, существует 1 DAG, в которых каждый «чистый» образ (избегая ребер, падающих на или ) должен содержать почти все ребра. Итак, мой вопрос на самом деле: может ли возможность удалить ребра, связанные с или существенно уменьшить размер разреза? Скорее всего, ответ отрицательный, но я пока не смог найти контрпример. с т к с т с т кkstkststk

Мотивация: Мой вопрос мотивирован доказательством нижних границ монотонных сетей с коммутацией и выпрямителем. Такая сеть - просто DAG, некоторые ребра которой помечены тестами "is ?" (нет тестов ). Размер сети является количество отмеченных ребер. Входной вектор принимается, если существует путь - все тесты которого соответствуют этому вектору. Марков доказал, что если у монотонной булевой функции нет минут, меньших и нет кратчайших, чем , то размер x i = 0 s t f l w l wxi=1xi=0stflwlwэто необходимо. Положительный ответ на мой вопрос подразумевал бы, что сети размером около необходимы, если по крайней мере переменные должны быть установлены в , чтобы уничтожить все minterms длиннее, чем .w k 0 kkwkwk0k


1 Конструкция приведена в этой статье. Возьмем полное двоичное дерево глубины . Удалить все края. Для каждого внутреннего узлаlog n vTlognv нарисуйте ребро каждого листа левого поддерева T v , а ребро от v до каждого листа правого поддерева T v . Таким образом, каждые два листа T соединены путем длины 2 в DAG. Сам DAG имеет ~ п узлов и ~ п войти п ребер, а Ом ( п журналvTvvTvT2nnlogn края должны быть удалены, чтобы уничтожить все пути длиннееΩ(nlogn) .n

Стасис
источник
Длина ограниченных потоков и разрезов тесно связана с вопросами, которые вы задаете. Рекомендую посмотреть на тезис Байера. ftp.math.tu-berlin.de/pub/Preprints/combi/…
Чандра Чекури,
@Chandra Chekuri: спасибо за интересную ссылку. Тезис больше о весовой теореме Менгера для коротких путей / недостатков. Что касается Менгера для длинных путей, я нашел эту статью: минимальный размер k-разреза не более чем в k раз превышает максимальное количество длинных непересекающихся st-путей. Но это тоже не помогает.
Стасис
Извините, я неправильно понял вопрос. Спасибо за другую ссылку.
Чандра Чекури

Ответы:

8

[Самостоятельный ответ; это сокращенная версия, старую можно найти здесь ]

С Георгом Шнитгером мы поняли, что ответ на мой вопрос строго отрицателен : существуют группы DAG (даже постоянной степени), где каждый разрез должен иметь постоянную дробь всех ребер, а не только дробь около 1 / k , как в мой вопрос. (Немного более слабый результат, что может потребоваться дробь 1 / log k, может быть получен с использованием гораздо более простой конструкции, упомянутой в сноске выше. Быстрая запись здесь ) k1/k1/logk

А именно, в статье «Об уменьшении глубины и решетках» Георг построил последовательность направленных ациклических графов постоянной максимальной степени d на узлах n = m 2 m со следующим свойством:Hndn=m2m

  • Для каждой константы существует константа c > 0 такая, что, если какое-либо подмножество не более чем c n узлов удаляется из H n , оставшийся граф содержит путь длиной не менее 2 ϵ m . 0ϵ<1c>0cnHn2ϵm

Теперь возьмем два новых узла и t и нарисуем ребро от s до каждого узла H n и ребро от каждого узла от H n до t . Результирующий граф G n по- прежнему имеет не более 2 n + d n = O ( n ) ребер.stsHnHntGn2n+dn=O(n)

Для каждой константы существует константа c > 0 такая, что, если любое подмножество не более c n ребер удаляется из G n , оставшийся граф содержит путь s - t с 2 ϵ m или больше краев. 0ϵ<1c>0cnGnst2ϵm

Доказательство: Назовите узлы внутренними узлами G n . Удалите любое подмножество не более c ' n ребер из G n , где c = c / 2 . После этого удалите внутренний узел, если он был инцидент с удаленным ребром. Обратите внимание, что затем удаляются не более 2 c ' n = c n внутренних узлов. Ни один из краев, падающих на выжившие узлы, не был удален. В частности, каждый выживший внутренний узел все еще связан с обоими узлами s и tHn GncnGnc=c/22cn=cnst, При указанном выше свойстве должен оставаться путь длиной 2 ϵ m, состоящий целиком из выживших внутренних узлов. Поскольку конечные точки каждого из этих путей сохранились, каждый из них может быть расширен до s - t- пути в G n . QEDHn2ϵmstGn

Следствие печально: не существует какого-либо аналога леммы Маркова для функций со многими короткими минтермами, хотя множество длинных минтерм имеет некоторую «сложную» структуру: никакие суперлинейные нижние оценки размера сети не могут быть доказаны с помощью этот аргумент "длина-ширина"

PS Этот аргумент «длина-ширина-ширина» (когда все - t- пути достаточно длинные) ранее использовался Муром и Шенноном (1956). Разница лишь в том, что они не допускают выпрямления (немаркированные ребра). Итак, это, по сути, «аргумент Мура-Шеннона-Маркова».st

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