Verificare se esiste un percorso tra due vertici nel grafico aciclico diretto - query

Question

Questa domanda può essere facilmente risolta in O (n + m) per query, tuttavia è possibile rispondere a tali query in una complessità migliore con preelaborazione migliore di O (n²)?

In albero può essere fatto facilmente lavorando con pre-ordine e in ordine. Ho provato qualcosa di simile in DAG ma non ha alcun senso.

Ho anche provato a modificare questo problema in LCA nel problema DAG, ma non è possibile trovare rapidamente LCA in DAG.

---

Per essere precisi vincoli diciamo:

n - numero di vertici, fino a 10^5

m - numero di spigoli, fino a 10^5

q - numero di domande, fino a 10^5

Answer 1

Interessante domanda. La mia intuizione dice "no". Non ci ho pensato comunque.

Tuttavia (supponendo che questa domanda non sia teorica), per scopi, è possibile utilizzare uno Bloom filter.

Una possibile soluzione al problema utilizzando un filtro Bloom genera innanzitutto K diversi ordini del grafico e, per ciascuno, memorizza la mappatura da un nodo al relativo indice in tale ordine. Quindi, per testare "raggiungibilità" da N1 a N2, si controlla (ordine foreach) se index-of-N1 è inferiore a index-of-N2 (questo controllo è O (1)). Se questo vale per tutti gli ordini, è raggiungibile con una buona probabilità (assuming K is big enough). (A seconda del tuo caso d'uso nel mondo reale, potrebbe anche essere opportuno gerarchizzare occasionalmente tali falsi positivi, oppure puoi eseguire il controllo O (N + M) affidabile). Altrimenti, non è assolutamente.

Answer 2

Ho la sensazione che potrebbe esserci una soluzione lungo le linee seguenti, ma questa non è affatto una soluzione completa.

Sia S un sottoinsieme di vertici. Per ogni vertice V nel grafico, considera l'insieme D_S (V), che definisco come segue: D_S (V) = {V} se V in S, e in caso contrario, D_S (V) è l'unione di {V} con gli insiemi D_S (W) per tutti i discendenti diretti W di V. (Cioè, è "tutti i discendenti finali di V, ma fermano la ricorsione ogni volta che si preme un elemento di V".) La domanda è: possiamo trovare un set S tale che la dimensione di S sia O (f (N)) e anche D_S (V) sia di dimensione O (g (N)) per tutto V, e dove f e g siano asintoticamente sublimatici? (Forse possiamo ottenere sqrt per entrambi, per esempio.)

Se possiamo trovare questo, quindi suggerisco la seguente strategia. Per la pre-elaborazione, creare per ogni U in S una tabella hash contenente tutti i vertici alla fine raggiungibili da U. Ciò può essere ottenuto in O (f (N) * M); questo non è necessariamente migliore di O (N^2), ma meglio di O (M * Q) almeno.

Ora per rispondere a una query "è U raggiungibile da V?", Questo è banale se V in S. Altrimenti, verifichiamo se V = U, nel qual caso è anche banale. Infine, applichiamo lo stesso processo a tutti i discendenti di V, in modo ricorsivo, restituendo "sì" se la risposta è "sì" attraverso uno dei due casi sopra, ma "no" solo se non troviamo mai U. Questa ricorsione richiede O (g (N)) passi.

La domanda che rimane è come scegliere S. Penso che se il grafico deriva da un processo in cui l'out-degree segue una legge di potenza, uno potrebbe semplicemente prendere i vertici sqrt (N) con gli out-gradi più alti.Ma per esempio se abbiamo il grafico su N = 2 * K vertici (i, 0) e (i, 1), con bordi K^2: da ciascuno (i, 0) a ciascuno (j, 1); allora non esiste un sottoinsieme adatto S. Ma forse i grafici che non hanno un S adatto hanno necessariamente un grado di uniformità che possiamo sfruttare ... O forse no. Non lo so. Qualche idea, fammi sapere!