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?
9
Respostas:
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−ε ε>0 n3−ε 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 -n n3−ε/3 n×n algoritmo de tempo ε / 3 ) para fechamento transitivo.n3−ε/3
Suponha que você deseja detectar um triângulo em uma nó 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 ,n G H H I,J,K n x G nas partes I , J , K . Para cada aresta ( u , v ) de G, adicione arestas direcionadas (xI,xJ,xK I,J,K (u,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) (u,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 (G u,v,w H (uI,vJ),(vJ,wK) H (uI,wK) H s t H 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) H H 2 (uI,vJ),(vJ,wK) (uI,wK) H u,v,w G
fonte
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) G G=G2
fonte
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 ( 1G G e probabilidade de erro≤δ:O(f(n)⋅log(1δ)) ≤δ
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 2 ∈ G ′ é 1G e1=(vi,vj),e2=(vj,vk)∈E (vi,vk)∉E G e1,e2∈G′ , portanto, em cada iteração, a probabilidade de o algoritmo descobrir queGnão era transitivo é116 G e apósas iteraçõesO(log(δ)),a probabilidade de falha é no máximoδ.16 O(log(δ)) δ
fonte
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) n m
fonte
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:x i(x) 0 x M(x) R
Esse algoritmo pode ser usado para o seu problema ou para outra aplicação?
fonte