Проверка транзитивности против транзитивного закрытия

9

Не проще ли проверить транзитивность орграфа, чем (с точки зрения асимптотической сложности) взять транзитивное замыкание орграфа? Знаем ли мы какую-либо нижнюю границу лучше, чемΩ(n2) определить, является ли орграф транзитивным или нет?

ekayaaslan
источник
1
Хранение всего переходного замыкания обойдется вам в дополнительное место. Для некоторых графиков вы должны иметь возможность подключать и сокращать проверку транзитивности, не возвращаясь к ребрам. Смотрите: АнO(logn)алгоритм параллельной связности, Y Shiloach, U Vishkin - Алгоритм Журнал, 1982
Чад Brewbaker
1
Здесь у Siek есть заметки по реализации библиотеки Boost Graph Library boost.org/doc/libs/1_54_0/libs/graph/doc/…
Чад Брюбейкер,
2
Не уверен, что вы подразумеваете под n, но нижняя граница Ω(|V|2) просто - посмотрим Kn{e} для какого-то края e, Любой алгоритм попросит обязательно проверить(u,v)E для всех u,vVиначе не хватало бы края, о котором он не спрашивал. O(|V||E|)верхняя граница, так как это время, необходимое для вычисления транзитивного замыкания.
РБ
2
Рассмотрим ориентированный граф с n=3k вершины: исходные вершины s1,,skпромежуточные вершины t1,,tk которые являются непосредственными преемниками каждого siи утопить вершины u1,,uk которые являются непосредственными преемниками каждого ti, Орграф транзитивен, если каждая из дуг(si,uj)присутствует на графике. Это требует проверкиk2=(n/3)2=Ω(n2)кромки. С другой стороны, найти транзитивное замыкание можно вO(nω) время, где ω<2.373показатель степени умножения матриц. Это самые известные границы.
Андрас Саламон
Возможно, у вашей группы обеспечения доступности баз данных есть какая-либо дополнительная структура или вы хотите получить общие результаты?
Ниль де Бодрап

Ответы:

9

Ниже я покажу следующее: если у вас есть O (n3ε) алгоритм времени для проверки, является ли граф транзитивным для любого ε>0, тогда у вас есть O (n3ε) алгоритм времени для обнаружения треугольника в nграф узлов, и, следовательно, (по документу из FOCS'10 ) у вас будет O (n3ε/3) алгоритм времени для умножения двух логических n×nматрицы, и, следовательно, в результате Фишера и Мейера из 70-х годов , это также подразумевает O (n3ε/3) алгоритм времени для транзитивного замыкания.

Предположим, что вы хотите обнаружить треугольник в n узел G, Теперь мы можем создать следующий графикH, H трехсторонний с перегородками I,J,K на nузлы каждый. Здесь каждый узелx из G имеет копии xI,xJ,xK по частям I,J,K, Для каждого края(u,v) из G добавить направленные края (uI,vJ) а также (uJ,vK), Для каждого неграда(u,v) из G добавить направленный край (uI,vK),

Во-первых, если G содержит треугольник u,v,w, тогда Hне является переходным. Это с краев(uI,vJ),(vJ,wK) находятся в H но (uI,wK)не является. Во-вторых, еслиH не транзитивен, то должен существовать некоторый направленный путь от некоторого узла s в какой-то узел t в H такой, что (s,t) не направленный край в H, Тем не менее, самые длинные пути вH иметь 2 ребра, и поэтому любой такой путь должен иметь форму (uI,vJ),(vJ,wK) а также (uI,wK) не в Hотсюда u,v,w сформировать треугольник в G,

Virgi
источник
1
Нахождение транзитивного замыкания по существу совпадает с умножением матрицы. Вопрос заключается в том, можно ли повысить показатель степени в нижней границе с 2, или показатель степени в верхней границе можно уменьшить с 2,337. Цепочка рассуждений, которую вы демонстрируете, показывает, что даже оптимальноеO(n2) алгоритм проверки транзитивности даст только O(n2.667) алгоритм времени для транзитивного закрытия - но у нас уже есть O(n2.373)алгоритм времени.
Андрас Саламон,
Дело в том, что сокращения черного ящика существуют. О (n2.373Время алгоритма далеко не практично. Практический алгоритм проверки транзитивности, который выполняется в субкубическое время, однако, с помощью вышеуказанных сокращений также подразумевает практический алгоритм для BMM и, следовательно, транзитивного замыкания. Кроме того, даже если вы не заботитесь о практических алгоритмах, вполне возможно, что потеря показателя степени из документа FOCS'10 не является необходимой, и обнаружение треугольника, вероятно, эквивалентно BMM.
Дева
Да, и конечно, мы могли бы просто обосновать сложность проблемы транзитивности только на предполагаемой твердости обнаружения треугольника. Обратите внимание, что нет известных нижних границ лучше, чемn2 для обнаружения треугольника, и лучшая верхняя граница O(nω),
virgi
У нас уже есть субкубический практический алгоритм с использованием любого метода быстрого умножения матриц: см., Например, cacm.acm.org/magazines/2014/2/…
Саламон,
2
В статье Балларда и др., Которую вы цитируете, говорится, в частности, об алгоритме Штрассена. Из того, что я знаю, ни один из алгоритмов умножения матриц, использующих границу ранга, не является практичным. В частности, я не знаю практических алгоритмов для каких-либо ограниченийω ниже чем 2.78,
virgi
7

Это выглядит так Ω(n2)является самой известной нижней границей, поскольку любая нижняя граница подразумевает нижнюю границу для умножения логической матрицы. Мы знаем, что проверка транзитивности может быть достигнута с помощью умножения одной логической матрицы, то естьG транзитивен тогда и только тогда, когда G=G2,

ekayaaslan
источник
4

Определить, является ли DAG транзитивным, так же сложно, как решить, является ли общий орграф транзитивным (что возвращает нас к вашему предыдущему вопросу :)).

Предположим, у вас есть алгоритм, работающий во времени O(f(n)) для принятия решения, является ли DAG транзитивным.

Дан ориентированный граф G, вы можете использовать следующий рандомизированный алгоритм, чтобы решить, G транзитивен во времени O(f(n)log(1δ)) и вероятность ошибки δ:

 1. for $O(\log{\frac{1}{\delta}})$ iterations:

   1.1. Compute a random permutation on $V$. Denote the result by $<v_1,v_2,...,v_n>$.

   1.2. Set $G'=(V,E\cup \{(v_i,v_j)|i<j\})$ (i.e. compute a random acyclic orientation).

   1.3. If $G'$ (which is acyclic) is not transitive return false.

 2. return true.

Теперь очевидно, что если G был транзитивным, этот алгоритм возвращает истину.

Теперь предположим Gне был переходным. Позволятьe1=(vi,vj),e2=(vj,vk)E такой, что (vi,vk)E (должны быть такие ребра как Gне переходный). Вероятность того, чтоe1,e2G является 16поэтому в каждой итерации вероятность того, что алгоритм будет фигурировать G не был переходным 16 и после O(log(δ)) итерации вероятность отказа не более δ,

RB
источник
1
Спасибо за ответ. Предположим, у меня есть алгоритм для решения, является ли DAG транзитивным вO(f(n)) такие f(n)=Ω(n2), Тогда я могу решить, является ли ориентированный граф G транзитивным вO(f(n))-time as; 1) Obtain strongly connected digraph in O(n2)-time. 2) Check if each component is complete in O(n2)-time. 3) Check if each pair of components, for which there is an edge in the component digraph, is bi-complete, that is there is an edge from every vertex of one component to every vertex of the second component in O(n2)-time. 4) Check if the component digraph transitive in O(f(n))-time.
ekayaaslan
1

I think this should be feasible in linear time, i.e. O(n+m) where n is the number of vertices and m the number of edges. Maybe by adapting some graph traversal scheme to the directed setting? A starting point could be the LexBFS / LexDFS described here; for directed graphs it seems that we should use topological sorting rather than DFS, so maybe it's possible with some LexTSA algorithm to discover?

Super9
источник
2
This is unlikely IMO, as it would give a probabilistic linear time algorithm for transitivity checking in general digraphs, see my answer.
R B
0

Regarding the previous answer, here's a simple way of defining such an algorithm. Assign to each vertex x an index i(x), initialized to 0. For each x, let M(x) denote the multiset of indices of its in-neighbors. We simulate a topological sorting by maintaining a set R of unexplored vertices, initialized to the entire set. At each step, we do the following:

  1. Chose a vertex xR whose multiset M(x) is minimal (in the multiset order);

  2. Update i(x) to the current loop counter and remove x from R.

Can this algorithm be used for your problem, or for some other application?

NisaiVloot
источник
This would be more appropriate as a comment.
Suresh Venkat