In che modo l'algoritmo di copertura del vertice di Chen et al trova le sue tuple?

Question

Io sono ancora Combattere con il summenzionato carta "migliorati limiti superiori per la copertura del vertice" di Chen, Kanj, Xia (PDF gentilmente fornito da Yuval Filmus).

Il mio problema attuale è che si specifica che l'algoritmo di copertura del vertice principale VC (Pagina 7/21) ha la seguente intestazione VC(G, T, k), dove G è il grafico da elaborare, T è un insieme di tuple e k è il parametro di delimitazione.

La mia domanda è: Cosa dovrebbe contenere l'insieme di tuple nella prima esecuzione di VC?

Si dice più volte che l'algoritmo mantiene questa struttura e genera TUPLE. Questo è ovvio, dato il Reducing comportamento della subroutine.

Ciò che mi dà problemi è quello Reducing viene chiamato prima di qualsiasi ulteriore logica in VC e Reducing stesso inizia con un ciclo che dice for each tuple (S, q) in T, il che implica che l'insieme T dovrebbe essere pre-popolato.

Se dovessi scansionare l'intero grafico per tutte le strutture che soddisferebbero i criteri per essere inclusi in T? Questo sembra un po 'drastico, dal momento che le operazioni Struction e General-Fold causerà le strutture in T essere invalidato.

Attualmente, la mia scommessa migliore è che, dato l'elenco delle priorità (pagina 8/21) di alcune strutture e la definizione di a buona coppia (Pagina 5/21, dopo l'osservazione 3.3) Dovrei cercare l'intero grafico per TUPLE, buone coppie e vertici con livelli elevati e metterli in T con priorità appropriate. La prima frase dalla sezione 4. l'algoritmo VC (Pagina 8/21) sembra abbastanza convincente:

Una tupla, una buona coppia o un vertice di grado di almeno sette, sarà indicata dalla struttura della parola. L'algoritmo manterrà un elenco di strutture T, quindi sceglierà una struttura ed elaborerà.

Qualcuno può fornire un po 'di intuizione? Forse mi manca solo qualcosa che mi sta fissando dal giornale stesso ...

Leggere più a fondo nella sezione Aggiornamento delle tuple (Pagina 6/21), si può vedere il seguente paragrafo:

Poiché una tupla impone alcuni vincoli sulla copertura del vertice minimo richiesto, è necessario fare attenzione che i vincoli imposti dalla creazione di una tupla non siano in conflitto con le condizioni imposte da altre operazioni dell'algoritmo.

Le altre operazioni che impongono vincoli sulla copertura del vertice minimo richiesto sono la creazione di (altre) tuple, l'operazione di struttura e l'operazione di piegatura generale.

Ad esempio, l'operazione di piegatura generale presuppone che quando stiamo cercando una copertura del vertice minimo, possiamo cercarne uno che contenga il set i o il set n (i) nella struttura (i, n (i)). Questo è principalmente il motivo per cui il set n (i) può essere piegato.

Se viene applicata l'operazione di piegatura generale, Quindi questo vincolo imposto dall'operazione sulla copertura del vertice minimo potrebbe essere in conflitto con i vincoli imposti da una certa tupla. Pertanto, per essere al sicuro, quando decidiamo di applicare la struttura o le operazioni di piegatura generale, invalideremo tutti i vincoli imposti dalle tuple. Questo è, Fondamentalmente rimuoveremo tutte le tuple.

Quindi, anche quando ho pre-seed T Con alcune strutture, molto probabilmente verranno rimosse prima o poi, lasciando un set vuoto e tornando al Square 1.