Verificação de transitividade vs. fechamento transitivo

9

Verificar a transitividade de um dígrafo não é mais fácil do que (em termos de complexidade assintótica) fazer o fechamento transitivo do dígrafo? Conhecemos algum limite inferior melhor que para determinar se um dígrafo é transitivo ou não?Ω(n2)

ekayaaslan
fonte
11
Armazenar todo o fechamento transitivo custará um espaço extra. Para alguns gráficos, você deve conseguir ligar e atalho a verificação de transitividade sem revisitar as arestas. Ver: Uma algoritmo conectividade paralelo, Y Shiloach, L Vishkin - Journal of Algorithms, 1982O(logn)
Chad Brewbaker
11
Aqui, Siek tem notas de implementação para a Biblioteca de Gráficos Boost boost.org/doc/libs/1_54_0/libs/graph/doc/…
Chad Brewbaker
2
Não tenho certeza do que você quer dizer com , mas um limite inferior de Ω ( | V | 2 ) é simples - considere K n{nΩ(|V|2) para obter alguma aresta e . Qualquer algoritmo solicitará que verifique se ( u , v ) E para todos os u , v V , caso contrário, a borda sobre a qual ele não perguntou pode estar faltando. O ( | V || E | )Kn{e}e(u,v)Eu,vVO(|V||E|)é um limite superior, pois esse é o tempo necessário para calcular um fechamento transitivo.
RB
2
Considere um gráfico direcionado com vértices: os vértices de origem s 1 , , s k , vértices intermediários t 1 , , estão presentes no gráfico. Isso requer a verificação de k 2 = ( n / 3 ) 2 =n=3ks1,,sk que são sucessores imediatas de cada um s i , e vértices de pia u 1 , ... , u k que são sucessores imediatos de cada t i . O dígrafo é transitivo se cada um dos arcos ( s i , u j )t1,,tksiu1,,ukti(si,uj) arestas. Por outro lado, encontrar fechamento transitivo pode ser feito no tempo O ( n ω ) , onde ω < 2,373 é o expoente da multiplicação da matriz. Esses são os limites mais conhecidos. k2=(n/3)2=Ω(n2)O(nω)ω<2.373
András Salamon
Seu DAG possivelmente possui alguma estrutura adicional ou deseja resultados totalmente gerais?
Niel de Beaudrap 11/03

Respostas:

9

Abaixo, mostrarei o seguinte: se você possui um algoritmo de tempo O ( ) para verificar se um gráfico é transitivo para qualquer ε > 0 , então você tem um O ( n 3 - εn3εε>0n3ε algoritmo de tempo ) para detectar um triângulo em um gráfico de e, portanto (por um trabalho de FOCS'10 ), você teria um algoritmo de tempo O ( n 3 - ε / 3 ) para multiplicar duas matrizes n × n booleanas e, portanto, por um resultado de Fischer e Meyer dos anos 70 , isso também implica um O ( n 3 -nn3ε/3n×nalgoritmo de tempo ε / 3 ) para fechamento transitivo.n3ε/3

Suponha que você deseja detectar um triângulo em uma G . Podemos agora criar o seguinte gráfico H . H é tripartida com partições I , J , K na n nodos cada. Aqui cada nó x de G tem cópias x I ,nGHHI,J,KnxG nas partes I , J , K . Para cada aresta ( u , v ) de G, adicione arestas direcionadas (xI,xJ,xKI,J,K(você,v)G e ( u J , v K ) . Para cada nonedge ( u , v ) de G, adicione a aresta direcionada ( u I , v K ) .(uI,vJ)(uJ,vK)(você,v)G(uI,vK)

Primeiro, se contém um triângulo u , v , w , então H não é transitivo. Isso ocorre porque as arestas ( u I , v J ) , ( v J , w K ) estão em H, mas ( u I , w K ) não estão. Segundo, se H não é transitivo, deve existir algum caminho direcionado de algum nó s para outro nó t em H, de modo que (Gu,v,wH(uI,vJ),(vJ,wK)H(uI,wK)HstH não é uma borda dirigida em H . Entretanto, os caminhos mais longos em H têm duas arestas e, portanto, esse caminho deve ter a forma ( u I , v J ) , ( v J , w K ) e ( u I , w K ) não está em H , portanto, u , v , w , formam um triângulo em L .(s,t)HH2(uI,vJ),(vJ,wK)(uI,wK)Hu,v,wG

virgi
fonte
11
Encontrar fechamento transitivo é essencialmente o mesmo que multiplicação de matrizes. A questão é se o expoente no limite inferior pode ser elevado de 2 ou se o expoente no limite superior pode ser reduzido de 2,373. A cadeia de raciocínio que você demonstra mostra que mesmo um algoritmo ideal para verificar a transitividade produziria apenas um algoritmo de tempo O ( n 2,666 ) para fechamento transitivo - mas já temos um algoritmo de tempo O ( n 2,337 ) . O(n2)O(n2.667)O(n2.373)
András Salamon
O ponto é que existem reduções na caixa preta. O algoritmo de tempo O ( ) está longe de ser prático. Um algoritmo prático de verificação de transitividade que é executado no tempo subcúbico, no entanto, pelas reduções acima, também implica um algoritmo prático para BMM e, portanto, fechamento transitivo. Além disso, mesmo que você não se importe com algoritmos práticos, é bem possível que a perda no expoente do documento FOCS'10 não seja necessária e a detecção de triângulo seja provavelmente equivalente ao BMM. n2.373
virgi
Ah, é claro, poderíamos basear a dureza do problema de transitividade apenas na dureza presumida da detecção de triângulo. Observe que não há limites inferiores conhecidos melhores que para a detecção de triângulo, e o melhor limite superior é O ( n ω )n2O(nω) .
virgi
Nós já temos um algoritmo prático subcubic, usando qualquer método de multiplicação de matrizes rápido: ver, por exemplo cacm.acm.org/magazines/2014/2/...
András Salamon
2
O artigo de Ballard et al. Que você menciona fala sobre o algoritmo de Strassen em particular. Pelo que sei, nenhum dos algoritmos de multiplicação de matrizes que usam classificação de borda é prático. Em particular, não conheço algoritmos práticos para qualquer limite em menor que 2,78 . ω2.78
virgi
7

Parece que é o limite inferior mais conhecido, pois qualquer limite inferior implica um limite inferior para a multiplicação da matriz booleana. Sabemos que a verificação de transitividade pode ser obtida usando uma multiplicação de matriz booleana, ou seja, G é transitivo se e somente se G = G 2 .Ω(n2)GG=G2

ekayaaslan
fonte
4

Descobrir se um DAG é transitivo é tão difícil quanto decidir se um dígrafo geral é transitivo (o que nos leva de volta à sua pergunta anterior :)).

Suponha que você tenha um algoritmo em execução no tempo para decidir se um DAG é transitivo.O(f(n))

Dado um gráfico direcionado , você pode usar o seguinte algoritmo aleatório para decidir se G é transitivo no tempo O ( f ( n ) log ( 1GGe probabilidade de erroδ: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.

Agora é óbvio que, se era transitivo, esse algoritmo retorna verdadeiro.G

Agora assuma que não era transitivo. Seja e 1 = ( v i , v j ) , e 2 = ( v j , v k ) E tal que ( v i , v k ) E (deve haver bordas que G não seja transitiva). A probabilidade de que e 1 , e 2G é 1Ge1=(vi,vj),e2=(vj,vk)E(vi,vk)EGe1,e2G , portanto, em cada iteração, a probabilidade de o algoritmo descobrir queGnão era transitivo é116G e apósas iteraçõesO(log(δ)),a probabilidade de falha é no máximoδ.16O(log(δ))δ

RB
fonte
11
Obrigado pela resposta. Suponha que eu tenha um algoritmo para decidir se um DAG é transitivo em como f ( n ) = Ω ( n 2 ) . Então, eu posso decidir se um gráfico direcionado G é transitivo em O ( f ( n ) ) -time como; 1) Obtenha um dígrafo fortemente conectado no tempo O ( n 2 ) . 2) Verifique se cada componente está completo em O ( n 2 )O(f(n))f(n)=Ω(n2)O(f(n))O(n2)O(n2)-Tempo. 3) Verifique se cada par de componentes, para o qual existe uma aresta no dígrafo do componente, é bi-completo, ou seja, existe uma aresta de cada vértice de um componente para cada vértice do segundo componente em -Tempo. 4) Verifique se o dígrafo do componente é transitivo no tempo O ( f ( n ) ) . O(n2)O(f(n))
ekayaaslan
1

Eu acho que isso deve ser possível em tempo linear, ou seja, onde n é o número de vértices e m o número de arestas. Talvez adaptando algum esquema de deslocamento gráfico para a configuração direcionada? Um ponto de partida pode ser o LexBFS / LexDFS descrito aqui ; para gráficos direcionados, parece que devemos usar a classificação topológica em vez do DFS; talvez seja possível descobrir com algum algoritmo LexTSA ?O(n+m)nm

Super9
fonte
2
Isso é improvável IMO, pois daria um algoritmo de tempo linear probabilístico para verificação de transitividade em dígrafos gerais, veja minha resposta.
RB
0

Com relação à resposta anterior, aqui está uma maneira simples de definir esse algoritmo. Atribua a cada vértice um índice i ( x ) , inicializado como 0 . Para cada x , deixe M ( x ) denotar o conjunto múltiplo de índices de seus vizinhos. Simulamos uma classificação topológica mantendo um conjunto R de vértices inexplorados, inicializados em todo o conjunto. Em cada etapa, fazemos o seguinte:xi(x)0xM(x)R

  1. xRM(x)

  2. i(x)xR

Esse algoritmo pode ser usado para o seu problema ou para outra aplicação?

NisaiVloot
fonte
Isso seria mais apropriado como um comentário.
Suresh Venkat 24/03