Algoritmo de ordenación topológica sin lista explícita de aristas

Question

Supongamos que tengo un conjunto de vértices $V$ y una función $f(V_1, V_2)$ que dados dos vértices devuelve +1 si hay una arista desde $V_1$ a $V_2$ -1 si hay una arista desde $V_2$ a $V_1$ y 0 en caso contrario.

Entonces dejemos que $S_0$ sea el conjunto de vértices sin aristas entrantes, $S_1$ sea el conjunto de vértices con aristas entrantes desde vértices en $S_0$ sólo, $S_2$ sea el conjunto de vértices con aristas entrantes desde vértices en $S_0$ y $S_1$ etc.

Estoy buscando un algoritmo que pueda ordenar el conjunto $V$ para que cada vértice de $S_0$ se coloca antes de cada vértice en $S_1$ y así sucesivamente. Ya sé que está relacionado con la ordenación topológica, pero calcular todo el conjunto de aristas para utilizarlo en cualquiera de los algoritmos que se dan en la Wikipedia llevaría $O(n^2)$ tiempo.

He escrito mi propio algoritmo que utiliza la función $f()$ directamente en lugar de precomputar las aristas, pero también se necesita $O(n^2)$ tiempo. Mi pregunta es: ¿es posible hacer algo mejor que $O(n^2)$ ¿tiempo? Estaría muy agradecido incluso de tener uno con un tiempo de ejecución menor.

--editar

Supongamos que $f()$ está garantizado que produce un grafo acíclico dirigido.

Answer 1

Estoy bastante seguro de que es imposible encontrar un algoritmo (pesimistamente) más rápido que $O(n^2)$ . Supongamos que tienes un algoritmo (llamémoslo $G$ ), que es capaz de ordenar sus vértices $V_i$ de manera topológica. Puedo darle un "mal jugador" (llámelo $B$ ), lo que creará un contraejemplo para su estrategia, obligándole a preguntar exactamente $\frac{n(n-1)}{2}$ veces sobre los bordes.

Supongamos que $G$ no hace ninguna pregunta, y se da cuenta de algunos pedidos $\sigma$ y $||V||=n$ .

Estamos viendo su respuesta $\sigma(1)$ que es un ID del vértice de $S_0$ . $B$ construye el gráfico, donde cualquier vértice dado (digamos - el que tiene el menor $id$ diferente entonces $\sigma(1)$ que no forma un ciclo), tiene una arista de salida hacia el $\sigma(1)$ . De esta manera $G$ tiene que pedir este conocimiento antes de hacer un pedido.

Como resultado, hay un nuevo $\sigma(1)$ valor, por lo que $B$ repite su movimiento.

...

Es fácil ver, que después de exactamente $\frac{n(n-1)}{2}$ preguntas, no hay más vértices que podamos conectar al particular $\sigma(1)$ y así $B$ no puede hacer $G$ la vida de los niños ya no es más difícil. Como resultado, $G$ construyó una ordenación correcta, pero tuvo que preguntar $O(n^2)$ preguntas, qed.

Modelar esto como un juego puede parecer contra intuitivo al principio, pero en realidad es un enfoque bastante natural. $B$ es simplemente nuestro método para pensar en el peor de los casos para cualquier algoritmo posible $G$ . Al mismo tiempo, acabamos de demostrar que para cada algoritmo existe un gráfico de entrada que requiere preguntar por cada par de vértices al menos una vez (sin contar las transposiciones). Esto no significa que un algoritmo no pueda correr más rápido, si lo piensas en términos de programación paralela, podrías hacerlo mucho mejor. Pero para un enfoque de "hilo", se necesita $O(n^2)$ tiempo en el peor de los casos. Por supuesto, puede haber un algoritmo que en el caso medio (o incluso en el 99,9% de los casos) funcione mucho más rápido.