Supongo que [matemáticas] Q [/ matemáticas] está en el orden de [matemáticas] V [/ matemáticas] o mayor.
Buscaría algoritmos para calcular el cierre transitivo. En el caso de que el gráfico sea escaso, ejecutar DFS [math] V [/ math] veces es bastante eficiente, no creo que sea probable que puedas superarlo. Para gráficos densos, puede reducir un poco el tamaño del problema al encontrar los componentes fuertemente conectados y luego encontrar el cierre transitivo del DAG del núcleo, que a menudo es más pequeño que el gráfico original, aunque esto no mejora en el peor de los casos. Creo que el mejor momento en el peor de los casos que puede obtener es [matemática] O (M (V)) [/ matemática] donde [matemática] M (V) [/ matemática] es la complejidad temporal de multiplicar dos [matemática] V \ veces V [/ math] matrices. Actualmente esto es algo así como [math] O (V ^ {2.37}) [/ math]. (Ver https://www.cs.bgu.ac.il/~dinitz… para la reducción.) Es probable que estos algoritmos no sean más eficientes que el enfoque ingenuo en la práctica. Creo que hay enfoques con una óptima complejidad temporal esperada ; Encontré esto solo buscando en Google. Puede que quieras averiguar eso.