L'ordine ottimale dei vertici grafici ST minimizza i bordi ai vertici successivi un problema ben noto?

Question

Non ho familiarità con la teoria dei grafici e ho trovato un problema interessante nel mio lavoro che non so se sia già noto o può essere facilmente mappato a un altro. Se dovessi esprimere il problema più formalmente:

Dato un grafico non ponderato diretto $ langle v, e rangle $, trova un ordine totale tra i vertici $ v_1 <v_2 < dots <v_n $ tale che minimizza $ vert f vert $, dove $ f = { langle lengle v_i, v_j rangle vert v_i <v_j, langle v_i, v_j rangle in e } $. Questo è trovare un ordine totale tra vertici in modo tale da ridurre al minimo il numero di bordi che "in avanti" nell'ordine.

Supponiamo che un semplice grafico diretto:

L'elenco dei bordi sarebbe $ [A Rightarrow B $, $ B Rightarrow C $, $ A Rightarrow C] $.

Un cattivo ordine sarebbe $ b <a <c $, perché, ad esempio, $ c $ viene dopo $ b $ nell'ordine e abbiamo il bordo $ b destrorrow c $. Pertanto, $ f = { langle b, c rangle, langle a, c rangle } $, $ vert f vert = 2 $.

Un buon ordine sarebbe $ c <b <a $, perché $ b <a $ e $ c <b $. Questo dà $ f = vuoto $ e quindi l'ottimale: $ vert f vert = 0 $.

Ho grafici densi, con alcuni componenti fortemente connessi e quando provo a risolverlo usando un risolutore SMT funziona davvero male con istanze non banali. La mia intuizione dice che è come un problema di buco di piccione. Quindi, le mie domande sono:

• È un problema ben noto nella comunità della teoria dei grafici?
• Può essere facilmente mappato a qualsiasi altro problema?
• In tal caso, c'è qualche buon algoritmo per risolverlo?
• È possibile calcolare facilmente un buon euristico?

Molte grazie in anticipo :)