Algoritmo rápido para averiguar si un subgráfico inducido está completo

Tengo un gráfico no ponderado no dirigido G = (V, E) y un subconjunto S elegido al azar de sus vértices. Quiero comprobar si los vértices en S son mutuamente adyacentes (es decir, formar un subgrafo/una camarilla completa).

I tienen el siguiente algoritmo (pseudo-código):Algoritmo rápido para averiguar si un subgráfico inducido está completo

foreach vertex in S { 
    // Check that the vertex has enough edges 
    if (vertex.edges.count < S.size - 1) 
    return false; 

    // Check that there is an edge to each vertex in S 
    foreach vertex2 in S { 
    if (!vertex.hasEdgeTo(vertex2)) 
     return false; 
    } 
} 
return true;

El problema es que el rendimiento del peor caso de este algoritmo es O (| V |) (en el caso cuando el subconjunto S contiene toda los vértices de un gráfico completo).

Mi pregunta es: ¿hay un algoritmo más rápido que se ejecute con una mayor complejidad de O peor caso?

Fuente

2010-07-31 Karel Petranek

No quiere decir _O (| V | ²) _? – Svante

Puede reducir a la mitad el factor constante comprobando cada borde una sola vez. Para eso, el bucle interno debe ejecutarse solo a través de todos los vértices que aún no se manejen en el exterior. Esto no da una mejor _O_ complejidad, por supuesto. – Svante

Sí, es O (| V |^2) en lugar de O (| E |^2), corregido. Sé que pude hacerlo la mitad del tiempo, omití eso por claridad. Gracias por tus comentarios. –

Suponiendo que puede comprobar si dos vértices son incidentes en O(1), su algoritmo tiene O(|V|²) = O(|E|) complejidad de tiempo en el peor de los casos. No creo que pueda hacerlo mejor que O(|E|), ya que realmente debe verificar todos los bordes del subgrafo.

Fuente

2010-07-31 23:58:25 Bolo

Pensé que ... esperaba un buen truco que posiblemente lo convertiría en O (| V | log (| V |) pero parece que tendré que seguir con este. –

@dark_charlie Bueno, mientras tú probablemente no se puede superar la 'O (| S | ²)' peor de los casos complejidad del tiempo, todavía puede acelerar el tiempo de ejecución medio de su algoritmo utilizando una serie de trucos Uno que viene a la mente es:. pedir al 'x .hasEdgeTo (y) 'preguntas en un orden tal que los más propensos a fallar se les pide primero por ejemplo, puede ordenar los vértices de ascender por su grado. (en' O (| S | log | S |) ') y ejecutar el bucle externo en ese orden. – Bolo

No creo que obtenga un algoritmo que no sea O (| E |^2) para realizar esta comprobación. Lógicamente, cada borde V1-V2 se debe buscar para probar la integridad. Separando en dos bucles, el primero que verifica el límite cuenta y el segundo luego verifica las conexiones de los vértices que podrían acelerar el algoritmo. Quizás otra forma de representar el gráfico (con los bordes en lugar de los vértices) ayudaría?

Fuente

2010-07-31 23:59:28

Buen punto @Bolo re: O (| V |^2). –

¿Cuál cree que sería la ventaja de representar el gráfico usando una lista de bordes/establecer para este problema? No tengo experiencia .. con dicha representación –

¿Cómo funciona su hasEdgeTo? Si usa un conjunto basado en árbol para almacenar los bordes, esa función no es solo O (1).

Al usar un bitvector para los bordes, puede ir con O (| S | * min (| E |, | V |, | S |)).

Fuente

2010-09-26 21:59:51 Albert

hasEdgeTo es O (1), estoy usando una matriz de adyacencia ¿Cuál es su idea de la O (| S | * Algoritmo min (log (| E |), | S |)))? –

@dark_charlie: Lo siento, o ya no recuerdo lo que pensé ayer o fue una mierda. La len del bitvector será | E | o | V | (en realidad, dividido por 8 porque usas bits). Pero todavía estoy pensando si podría haber otra representación que lo haga más rápido. Escribiré de nuevo si tengo una idea o recuerdo de nuevo. :) – Albert

Algoritmo rápido para averiguar si un subgráfico inducido está completo

Respuesta

Cuestiones relacionadas