Транзитивное уменьшение DAG

13

Я ищу O (V + E) алгоритм для нахождения транзитивного сокращения с учетом DAG.

То есть удалите как можно больше ребер, чтобы, если бы вы могли достичь v от u, для произвольных v и u вы все еще можете достичь после удаления ребер.

Если это стандартная проблема, пожалуйста, укажите мне какое-нибудь модельное решение.

algorithms graphs dag Каран
источник

Вы не можете использовать ссылку, приведенную в лемме Википедии, которую вы цитируете?

Хендрик Янв

2

Хорошо, алгоритм, обсуждаемый в Википедии, работает в

(в лучшем случае, то есть в случае ациклических графов) вместо

как было запрошено. Я думаю, что правильный ответ здесь заключается в том, что алгоритм, который вы ищете в настоящее время, может не существовать

O (V \times E)

$O(V\times E)$

O (V + E)

$O(V+E)$

Карлос Линарес Лопес

1

Договорились, что не ясно, что то, о чем вы просите, существует. Есть немало статей, которые были бы неинтересны, если бы существовал такой алгоритм, например, sciencedirect.com/science/article/pii/0012365X9390164O . Тем не менее, если вы можете быть более конкретным в отношении вашей мотивации, могут быть более конкретные решения. Например, знаете ли вы что-нибудь еще о графике или

работать?

O (n (n + m))

$O(n(n+m))$

Уильям Макрэй

Я где-то видел проблему, но не было никакой дополнительной информации, возможно, опечатка в проблеме.

Каран

1

Что делать , если вы топологическую сортировку в вашем DAG, но следить за достижимые вершины с помощью детей, то есть

r e a c h a b l e [v] = \cup_{v^{'} \in c h i l d r e n_{v}} r e a c h a b l e [v^{'}]

$reachable[v] = \cup_{v' \in children_v} reachable[v']$ , затем начните с последнего элемента в отсортированном графе, удалите неиспользуемые ребра и поднимитесь, сохранив достижимую функцию, это даст вам максимально возможные ребра для удаления, но я не уверен, что это максимально возможно (это

.

O (| E | + | V |)

$O(|E|+|V|)$

8

Мы можем решить эту проблему, просто используя DFS для каждой вершины.

Для каждой вершины начните DFS с каждой вершины , чтобы был прямым потомком , т.е. это ребро. $u \in G$ $v$ $v$ $u$ $(u,v)$
Для каждой вершины достижимой DFS из , удалите ребро . $v'$ $v$ $(u, v')$

Общая сложность описанного выше - сложность запуска DFS ', которая равна . $N$ $O(N(N+M))$

pratyaksh
источник

1

Обратите внимание, что асимптотически это имеет ту же сложность, что и алгоритм

в статье Википедии, связанной с самим вопросом.

O (N M)

$O(NM)$

Дэвид Ричерби,

1

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

является IMO, маловероятным.

O (N)

$O(N)$

pratyaksh

3

Это не то что вы ищете. Но только для обмена знаниями цели, вы можете сделать это с сообщений , если предположить , что каждая вершина , чтобы выступать в качестве процессора . Обратите внимание, что каждая вершина имеет сопоставимое значение. Следовательно, существуют некоторые вершины, такие, что они больше, чем все их соседи. Эти вершины делают следующее: $O(|E|)$

Пусть будет максимальным меньшим соседом , $u$ $v$
послать сообщение и включают в себя ребро на выходе. $u$ $(v,u)$
Для каждого соседа из и (и меньшего, чем оба) не включайте в выходные данные. $w$ $u$ $v$ $(v,w)$
Повторяйте шаги до тех пор, пока все ребра для меньшего соседа вершины будут включены или не включены в выходные данные. $(v,v')$ $v'$ $v$

$v$ $(v',v)$ $v$

$O(|E|)$

AJed
источник

1

Лемма: Если существует ребро V -> Y и Y также является косвенным преемником V (например, V -> W -> + Y), то ребро V -> Y транзитивно и не является частью транзитивного корня.

Метод: Отслеживайте транзитивное замыкание каждой вершины, работая от терминала к начальным вершинам в обратном топологическом порядке. Множество косвенных наследников V - это объединение транзитивных замыканий непосредственных наследников V. Транзитивное замыкание V - это объединение косвенных наследников и его непосредственных наследников.

Алгоритм:

    Initialise Visited as the empty set.
    For each vertex V of G, 
        Invoke Visit(V).

    Visit(V):
        If V is not in Visited,
            Add V to Visited, 
            Initialise Indirect as the empty set,
            For each edge V -> W in G,
                Invoke Visit(W),
                Add Closure(W) to Indirect.
            Set Closure(V) to Indirect.
            For each edge V -> W in G,
                Add W to Closure(V),
                If W is in the set Indirect,
                    Delete the edge V -> W from G.

Это предполагает, что у вас есть какой-то эффективный способ отслеживания наборов вершин (например, битовых карт), но я думаю, что это предположение сделано и в других алгоритмах O (V + E).

Потенциально полезным побочным эффектом является то, что он находит транзитивное замыкание каждой вершины G.

DRBD
источник

Я удалил ответ, опубликованный в вашем предыдущем аккаунте. Если вы по-прежнему хотите объединить две учетные записи, следуйте инструкциям в справочном центре . При этом, поскольку у более ранней учетной записи больше нет видимого контента, вы можете просто придерживаться новой.

Жиль "ТАК - перестань быть злым"

0

Я решил ту же проблему, но это было не совсем то же самое. Он попросил минимальное количество ребер в графе после редукции, чтобы изначально соединенные вершины все еще были соединены, и новые соединения не выполнялись. Как понятно, здесь говорится не о том, чтобы найти сокращенный граф, а о том, сколько избыточных ребер имеется. Эта проблема может быть решена в O (V + E). Ссылка на объяснение: https://codeforces.com/blog/entry/56326 . Но я думаю, что на самом деле сделать график будет сложнее, чем O (N)

Кумар Мохит
источник

Транзитивное уменьшение DAG

Ответы: