Не проще ли проверить транзитивность орграфа, чем (с точки зрения асимптотической сложности) взять транзитивное замыкание орграфа? Знаем ли мы какую-либо нижнюю границу лучше, чем определить, является ли орграф транзитивным или нет?
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 ,
источник
Это выглядит такΩ(n2) является самой известной нижней границей, поскольку любая нижняя граница подразумевает нижнюю границу для умножения логической матрицы. Мы знаем, что проверка транзитивности может быть достигнута с помощью умножения одной логической матрицы, то естьG транзитивен тогда и только тогда, когда G=G2 ,
источник
Определить, является ли DAG транзитивным, так же сложно, как решить, является ли общий орграф транзитивным (что возвращает нас к вашему предыдущему вопросу :)).
Предположим, у вас есть алгоритм, работающий во времениO(f(n)) для принятия решения, является ли DAG транзитивным.
Дан ориентированный графG , вы можете использовать следующий рандомизированный алгоритм, чтобы решить, G транзитивен во времени O(f(n)⋅log(1δ)) и вероятность ошибки ≤δ :
Теперь очевидно, что еслиG был транзитивным, этот алгоритм возвращает истину.
Теперь предположимG не был переходным. Позволятьe1=(vi,vj),e2=(vj,vk)∈E такой, что (vi,vk)∉E (должны быть такие ребра как G не переходный). Вероятность того, чтоe1,e2∈G′ является 16 поэтому в каждой итерации вероятность того, что алгоритм будет фигурировать G не был переходным 16 и после O(log(δ)) итерации вероятность отказа не более δ ,
источник
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?
источник
Regarding the previous answer, here's a simple way of defining such an algorithm. Assign to each vertexx 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:
Chose a vertexx∈R whose multiset M(x) is minimal (in the multiset order);
Updatei(x) to the current loop counter and remove x from R .
Can this algorithm be used for your problem, or for some other application?
источник