¿Comprobar la transitividad de un dígrafo no es más fácil que (en términos de complejidad asintótica) tomar el cierre transitivo del dígrafo? ¿Conocemos algún límite inferior mejor que para determinar si un dígrafo es transitivo o no?
9
Respuestas:
A continuación, mostraré lo siguiente: si tiene un algoritmo de tiempo O ( ) para verificar si un gráfico es transitivo para cualquier , entonces tiene un O ( ) algoritmo de tiempo para detectar un triángulo en un gráfico de nodos, y por lo tanto (por un documento de FOCS'10 ) tendrías un algoritmo de tiempo O ( ) para multiplicar dos matrices booleanas y, por lo tanto, como resultado de Fischer y Meyer de los años 70 , esto también implica un algoritmo de tiempo O ( ) para el cierre transitivo. ε > 0norte3 - ε ε > 0 n n 3 - ε / 3 n × n n 3 - ε / 3norte3 - ε norte norte3 - ε / 3 n × n norte3 - ε / 3
Supongamos que se desea detectar un triángulo en un nodo . Ahora podemos crear el siguiente gráfico . es tripartito con particiones en nodos cada una. Aquí cada nodo de tiene copias en las partes . Para cada arista de agregue aristas dirigidas y . Para cada no borde de agregue el borde dirigido .G H H I , J , K n x G x I , x J , x K I , J , K ( u , v ) G ( u I , v J ) ( u J , v K ) ( u , v ) G ( u I , v K )norte sol H H yo, J, K norte X sol Xyo, xJ, xK yo, J, K (u,v) G (uI,vJ) (uJ,vK) (u,v) G (uI,vK)
Primero, si contiene un triángulo , entonces no es transitivo. Esto se debe a que los bordes están en pero no lo está. En segundo lugar, si no es transitivo, entonces no debe existir algún camino dirigido desde algún nodo a algún nodo en tal que no es un borde dirigido en . Sin embargo, las rutas más largas en tienen aristas, por lo que dicha ruta debe tener la forma y no está enu , v , w H ( u I , v J ) , ( v J , w K ) H ( u I , w K ) H s t H ( s , t ) H H 2 ( u I , v J ) , ( v J , w K ) ( u I ,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) H u , v , w sol(uI,wK) H , por lo tanto, forma un triángulo en .u,v,w G
fuente
Parece que es el límite inferior más conocido, ya que cualquier límite inferior implica un límite inferior para la multiplicación de matriz booleana. Sabemos que la verificación de transitividad se puede lograr usando una multiplicación de matriz booleana, es decir, es transitiva si y solo si .Ω(n2) G G=G2
fuente
Calcular si un DAG es transitivo es tan difícil como decidir si un dígrafo general es transitivo (lo que nos lleva de vuelta a su pregunta anterior :)).
Suponga que tiene un algoritmo ejecutándose en el tiempo para decidir si un DAG es transitivo.O(f(n))
Dado un gráfico dirigido , puede usar el siguiente algoritmo aleatorio para decidir si G es transitivo en el tiempo O ( f ( n ) ⋅ log ( 1G G y probabilidad de error≤δ:O(f(n)⋅log(1δ)) ≤δ
Ahora es obvio que si fue transitivo, este algoritmo devuelve verdadero.G
Ahora suponga que no era transitivo. Sea e 1 = ( v i , v j ) , e 2 = ( v j , v k ) ∈ E tal que ( v i , v k ) ∉ E (tiene que haber bordes como G no sea transitivo). La probabilidad de que e 1 , e 2 ∈ G ′ es 1G e1=(vi,vj),e2=(vj,vk)∈E (vi,vk)∉E G e1,e2∈G′ , por lo tanto, en cada iteración, la probabilidad de que el algoritmo descubra queGno era transitivo es116 G y después de lasiteracionesO(log(δ))la probabilidad de falla es como máximoδ.16 O(log(δ)) δ
fuente
Creo que esto debería ser factible en tiempo lineal, es decir, donde n es el número de vértices ym el número de aristas. ¿Tal vez adaptando algún esquema transversal del gráfico a la configuración dirigida? Un punto de partida podría ser el LexBFS / LexDFS descrito aquí ; para los gráficos dirigidos, parece que deberíamos usar la clasificación topológica en lugar de DFS, ¿entonces tal vez sea posible descubrir algún algoritmo LexTSA ?O(n+m) n m
fuente
Con respecto a la respuesta anterior, aquí hay una manera simple de definir dicho algoritmo. Asigne a cada vértice un índice i ( x ) , inicializado a 0 . Para cada x , supongamos que M ( x ) denota el conjunto múltiple de índices de sus vecinos. Simulamos una ordenación topológica manteniendo un conjunto R de vértices inexplorados, inicializados en todo el conjunto. En cada paso, hacemos lo siguiente:x i(x) 0 x M(x) R
Elija un vértice cuyo multiset M ( x ) es mínimo (en el orden multiset);x∈R M(x)
Actualización de a los actuales de control del bucle y quitar x de R .i(x) x R
¿Se puede usar este algoritmo para su problema o para alguna otra aplicación?
fuente