Мы рассматриваем DAG (ориентированные ациклические графы) с одним исходным узлом и одним целевым узлом ; допускаются параллельные ребра, соединяющие одну и ту же пару вершин. - разрез представляет собой набор ребер, удаление уничтожает все - пути по длиннее , чем ; более короткие - пути, а также длинные «внутренние» пути (не между и ) могут выжить!ы т к ы т ы т
Вопрос: Достаточно ли удалить не более части ребер из DAG, чтобы уничтожить все - пути, длина которых превышает ?
То есть, если обозначает общее число ребер в , то каждый делает ДАГ Пользователю A Обрежьте с не более чем приблизительно ребер? Два примера:
- Если все - пути имеют длину , то существует разрез с ребрами. Это верно, потому что тогда должно быть непересекающихся -узлов: просто наслоите узлы соответствии с их расстоянием от исходного узла .
- Если представляет собой переходный турнир (полный DAG), а затем также Обрежьте с ребро существует: фиксирует топологическое упорядочение из узлы, разбить узлы на последовательных интервалов длины и удалить все ребра, соединяющие узлы одного и того же интервала; это уничтожит все - пути больше чем .
Замечание 1: Наивной попыткой дать положительный ответ (который я также попробовал первым) было бы попытаться показать, что каждый DAG должен иметь около непересекающихся -сечений. К сожалению, пример 2 показывает, что эта попытка может потерпеть неудачу: с помощью хорошего аргумента Дэвид Эппштейн показал, что для about граф не может иметь более четырех непересекающихся -сечений! k k √ Tnk
Замечание 2: Важно, чтобы разрез должен был только уничтожить все длинные - пути, а не обязательно все длинные. А именно, существует 1 DAG, в которых каждый «чистый» образ (избегая ребер, падающих на или ) должен содержать почти все ребра. Итак, мой вопрос на самом деле: может ли возможность удалить ребра, связанные с или существенно уменьшить размер разреза? Скорее всего, ответ отрицательный, но я пока не смог найти контрпример. с т к с т с т к
Мотивация: Мой вопрос мотивирован доказательством нижних границ монотонных сетей с коммутацией и выпрямителем. Такая сеть - просто DAG, некоторые ребра которой помечены тестами "is ?" (нет тестов ). Размер сети является количество отмеченных ребер. Входной вектор принимается, если существует путь - все тесты которого соответствуют этому вектору. Марков доказал, что если у монотонной булевой функции нет минут, меньших и нет кратчайших, чем , то размер x i = 0 s t f l w l ⋅ wэто необходимо. Положительный ответ на мой вопрос подразумевал бы, что сети размером около необходимы, если по крайней мере переменные должны быть установлены в , чтобы уничтожить все minterms длиннее, чем .w k 0 k
1 Конструкция приведена в этой статье. Возьмем полное двоичное дерево глубины . Удалить все края. Для каждого внутреннего узлаlog n v нарисуйте ребро каждого листа левого поддерева T v , а ребро от v до каждого листа правого поддерева T v . Таким образом, каждые два листа T соединены путем длины 2 в DAG. Сам DAG имеет ~ п узлов и ~ п войти п ребер, а Ом ( п журнал края должны быть удалены, чтобы уничтожить все пути длиннее √ .
Ответы:
[Самостоятельный ответ; это сокращенная версия, старую можно найти здесь ]
С Георгом Шнитгером мы поняли, что ответ на мой вопрос строго отрицателен : существуют группы DAG (даже постоянной степени), где каждый разрез должен иметь постоянную дробь всех ребер, а не только дробь около 1 / k , как в мой вопрос. (Немного более слабый результат, что может потребоваться дробь 1 / log k, может быть получен с использованием гораздо более простой конструкции, упомянутой в сноске выше. Быстрая запись здесь )k 1/k 1/logk
А именно, в статье «Об уменьшении глубины и решетках» Георг построил последовательность направленных ациклических графов постоянной максимальной степени d на узлах n = m 2 m со следующим свойством:Hn d n=m2m
Теперь возьмем два новых узла и t и нарисуем ребро от s до каждого узла H n и ребро от каждого узла от H n до t . Результирующий граф G n по- прежнему имеет не более 2 n + d n = O ( n ) ребер.s t s Hn Hn t Gn 2n+dn=O(n)
Доказательство: Назовите узлы внутренними узлами G n . Удалите любое подмножество не более c ' n ребер из G n , где c ′ = c / 2 . После этого удалите внутренний узел, если он был инцидент с удаленным ребром. Обратите внимание, что затем удаляются не более 2 c ' n = c n внутренних узлов. Ни один из краев, падающих на выжившие узлы, не был удален. В частности, каждый выживший внутренний узел все еще связан с обоими узлами s и tHn Gn c′n Gn c′=c/2 2c′n=cn s t , При указанном выше свойстве должен оставаться путь длиной 2 ϵ m, состоящий целиком из выживших внутренних узлов. Поскольку конечные точки каждого из этих путей сохранились, каждый из них может быть расширен до s - t- пути в G n . QEDHn 2ϵm s t Gn
Следствие печально: не существует какого-либо аналога леммы Маркова для функций со многими короткими минтермами, хотя множество длинных минтерм имеет некоторую «сложную» структуру: никакие суперлинейные нижние оценки размера сети не могут быть доказаны с помощью этот аргумент "длина-ширина"
PS Этот аргумент «длина-ширина-ширина» (когда все - t- пути достаточно длинные) ранее использовался Муром и Шенноном (1956). Разница лишь в том, что они не допускают выпрямления (немаркированные ребра). Итак, это, по сути, «аргумент Мура-Шеннона-Маркова».s t
источник