Compresie iterativă

Compresia iterativă  este o tehnică algoritmică de dezvoltare a algoritmilor rezolvabili parametri fix . În această tehnică, la fiecare pas , un element (cum ar fi un vârf de graf ) este adăugat problemei și, înainte de a-l adăuga, se găsește o mică soluție la problemă.

Istorie

Tehnica a fost dezvoltată de Reed, Smith și Wetta [1] pentru a arăta că problema eliminării ciclurilor impare este rezolvabilă în timp pentru graficele cu n vârfuri, m muchii și k număr de vârfuri de eliminat . Problema de eliminare a ciclului impar este problema găsirii celui mai mic set de vârfuri care include cel puțin un vârf din orice ciclu impar. Complexitatea parametrică a acestei probleme a rămas deschisă mult timp [2] [3] . Mai târziu, această tehnică a devenit foarte utilă pentru demonstrarea rezultatelor privind solvabilitatea cu parametri fixe . Acum această tehnică este considerată a fi una dintre cele fundamentale în domeniul algoritmilor parametrizați.

Compresia iterativă a fost folosită cu succes în multe probleme, cum ar fi eliminarea ciclurilor impare (vezi mai jos) și eliminarea muchiilor pentru a obține bipartite , găsirea nodurilor de tăiere a ciclului , eliminarea nodurilor cluster și găsirea vârfurilor de tăiere a ciclului orientat [4] . Metoda a fost folosită cu succes și pentru algoritmi de timp exponențial exact pentru găsirea unei mulțimi independente [5] .

Tehnica

Compresia iterativă este aplicabilă, de exemplu, problemelor parametrizate pe grafice , a căror intrare este un grafic G =( V , E ) și un număr natural k , iar problema este pusă ca verificare a existenței unei soluții (un set de vârfuri) de dimensiune . Să presupunem că problema este închisă sub subgrafe generate (dacă există o soluție pentru un grafic dat, atunci există o soluție de această dimensiune sau mai mică pentru orice subgraf generat) și că există o procedură eficientă care determină dacă o soluție de dimensiunea Y poate fi micsorat la o solutie mai mica de marime k .

Dacă această ipoteză este valabilă, atunci problema poate fi rezolvată prin adăugarea de vârfuri pe rând și găsirea unei soluții pentru subgraful generat, după cum urmează:

  1. Începem cu un subgraf generat de o mulțime de vârfuri S de mărimea k și o soluție X care este egală cu S însuși .
  2. Deocamdată , luăm următorii pași:
    • Fie v orice vârf , adăugați v la S
    • Verificăm dacă soluția cu ( k + 1) vârfuri Y = X ∪ {x } pentru S poate fi comprimată într-o soluție cu k vârfuri.
    • Dacă soluția nu poate fi comprimată, terminăm algoritmul - graficul de intrare nu are o soluție cu k vârfuri.
    • În caz contrar, presupunem că X este o nouă soluție comprimată și revenim la începutul buclei.

Acest algoritm numește rutina de compresie de un număr liniar de ori. Prin urmare, dacă o variantă a procedurii de comprimare rulează într-un timp fix-parametric rezolvabil, adică pentru o constantă c, atunci procedura de comprimare iterativă pentru rezolvarea problemei complete se execută în timp . Aceeași tehnică poate fi folosită pentru a găsi seturi de muchii pentru proprietățile graficelor care sunt închise sub subgrafe (altele decât un subgraf generat) sau alte proprietăți în teoria grafurilor. Când valoarea parametrului k este necunoscută, acesta poate fi găsit utilizând o căutare exponențială la nivel exterior sau o căutare liniară pentru alegerea optimă a lui k , cu o căutare la fiecare pas, bazată pe același algoritm de compresie iterativă.

Aplicații

În articolul original, Reed, Smith și Wetta au arătat cum să faci un grafic bipartit eliminând cel mult k vârfuri în timp . Mai târziu, Lokshtanov, Saurabh și Sikdar au dat un algoritm mai simplu, folosind și compresia iterativă [6] . Pentru a comprima setul eliminat Y de dimensiunea k + 1 într-un set X de dimensiunea k , algoritmul lor verifică toate partițiile setului Y în trei subseturi - un submult al mulțimii Y care aparține noului set eliminat și două subseturi de mulţimea Y ​​care aparţin a două părţi ale grafului bipartit rămase după eliminarea mulţimii X . Odată ce aceste trei mulțimi au fost alese, vârfurile rămase ale mulțimii X de eliminat (dacă există) pot fi găsite din ele folosind algoritmul Ford-Fulkerson .

Acoperirea vârfurilor  este un alt exemplu pentru care se poate aplica compresia iterativă. Problema acoperirii vârfurilor primește un grafic și un număr natural k ca intrare , iar algoritmul trebuie să decidă dacă există o mulțime X cu k vârfuri astfel încât orice muchie să fie incidentă la un vârf din X. În varianta de compresie, intrarea este o mulțime Y cu vârfuri care este incidentă la toate muchiile grafului, iar algoritmul trebuie să găsească o mulțime X de dimensiunea k cu aceeași proprietate, dacă există. O modalitate de a face acest lucru este să testați toate opțiunile prin care setul Y este eliminat din acoperire și inserat înapoi în grafic. O astfel de iterație poate funcționa numai dacă nu sunt adiacente două vârfuri de eliminat și pentru fiecare astfel de variantă, subprogramul trebuie să includă în acoperire toate nodurile din afara lui Y care sunt incidente cu muchia care devine descoperită prin această îndepărtare. Utilizarea unei astfel de subrutine într-un algoritm de compresie iterativă produce un algoritm simplu în timp pentru acoperirea vârfurilor.

Vezi și

Note

  1. Reed, Smith, Vetta, 2004 , p. 299–301.
  2. Niedermeier, 2006 , p. 184.
  3. Cygan, Fomin, Kowalik et al., 2015 , p. 555.
  4. Guo, Moser, Niedermeier, 2009 , p. 65–80.
  5. Fomin, Gaspers, Kratsch et al., 2010 , p. 1045–1053.
  6. Lokshtanov, Saurabh, Sikdar, 2009 , p. 380–384.

Literatură