Come la riduzione transitiva, ma la rimozione dei vertici piuttosto che i bordi?

Question

Supponiamo di avere un grafico diretto $ G = (v, e) $ (o, che è lo stesso, una relazione sul set $ V $ come definito dalla matrice di adiacenza) che può contenere tre vertici $ x, y, z $, tale che $ xy, xz, yz in e $ - Vale a dire, la relazione si limita a $ x, y, z $ è transitivo, c'è un triangolo. Chiamiamo questa situazione a "Transitività locale". Il mio obiettivo è quello di ottenere tutti i sottgrafi di $ G $ indotto dal taglio dei vertici medi dalle transitività locali fino a quando non rimane, cosa che dub "risoluzione".

Potrebbero esserci più soluzioni. Ad esempio, considera un grafico dato da questa relazione:

  a b c d  
a □ ■ ■ □  
b □ □ ■ ■  
c □ □ □ ■  
d □ □ □ □  

(Sembra un quadrato con una diagonale.)

Ci sono due modi in cui può essere risolto:

  a b d        a c d  
a □ ■ □      a □ ■ □  
b □ □ ■      c □ □ ■  
d □ □ □      d □ □ □  

Un modo in cui posso calcolare le risoluzioni di un grafico è dando un "non deterministico" funzione $ f: g destrorrow {g } $ Ciò rimuove qualsiasi singola transitività locale. Applicando ripetutamente $ f $ A qualsiasi grafico, alla fine convergerò in una serie di sottografi indotti completamente privi di transitività locali.

Un modo per definire $ f $ è considerando tutte le triple di vertici distinti e controllandoli per la transitività locale. Da ogni triplo corrispondente, il vertice centrale viene estratto e uno di questi vertici viene tagliato. Ma c'è circa $ | V |^3 $ Tali triple.

C'è un modo migliore? C'è una precedente arte che posso studiare?

 

Ps Rispondere alle domande dei commenti:

1. La "transitività locale" è la stessa di un triangolo? O potrebbe (ad esempio) coinvolgere più di 3 vertici?

   Nel caso in cui ho in mente, sono specificamente triangoli che devo rimuovere. Ma posso vedere come si può offrire una generalizzazione dove, dati due percorsi $ p_1, p_2: a dots b $ tale che $ | p_1 | leq n $ e $ | P_2 | leq m $ (Conteggio dei bordi), possiamo rimuovere più a lungo. Il mio problema specifico è quindi il caso speciale con $ n = 1, m = 2 $.

2. Nel tuo esempio, penso che ci siano più di due modi in cui può essere risolto. Ad esempio, è possibile rimuovere il vertice A (dal triangolo ABC) ...

   Stavo pensando che fosse permesso rimuovere solo un punto medio da un triangolo, così che "iniziale" e "terminale" I vertici non possono essere rimossi e quindi viene conservata la lunghezza del percorso più breve.

3. Qual'è la tua domanda? È la tua domanda "Posso elencare tutti i triangoli più velocemente di $ O (| v |^3) $ tempo? "La tua domanda" è in modo efficiente in modo efficiente tutti possibili sottgrafi senza triangolo? "

   Questo e anche quello. Principalmente, ho bisogno dei sottgrafi indotti dal triangolo. L'enumerazione dei triangoli è solo un mezzo a tal fine, ma può essere una tecnica utile per altri algoritmi, altrove, quindi sarebbe bello sapere.