Set de vârfuri de tăiere ciclului

În teoria grafurilor, setul de vârfuri de tăiere a ciclului al unui graf  este setul de vârfuri a căror eliminare duce la întreruperea ciclurilor . Cu alte cuvinte, setul de vârfuri de tăiere a ciclului conține cel puțin un vârf din orice ciclu de grafic. Problema mulțimii de vârfuri de tăiere a ciclului este o problemă NP-completă în teoria complexității computaționale . Problema este inclusă în lista de 21 de probleme NP-complete a lui Karp . Problema are o aplicație largă în sisteme de operare , baze de date și dezvoltare VLSI .

Definiție

Problema setului de vârfuri de tăiere a ciclului  este următoarea problemă de solubilitate :

Dat: Un grafic (nedirecționat sau direcționat) și un număr pozitiv . Întrebare: Există o submulțime pentru care , astfel încât cu vârfurile eliminate aparținând , nu conține cicluri ?

Graficul rămas după eliminarea vârfurilor aparținând mulțimii din grafic este o pădure generată (pentru graficele nedirecționate, sau un grafic aciclic direcționat generat pentru graficele direcționate ). Astfel, căutarea unui ciclu minim care decupează un set de vârfuri într-un graf echivalează cu căutarea unei păduri maxime generate (respectiv, un graf aciclic maxim generat în cazul grafurilor direcționate ).

NP-dificultate

Karp [1] a arătat că problema setului de vârfuri de tăiere a ciclului pentru graficele direcționate este NP-complet . Problema rămâne NP-completă pentru grafurile direcționate cu un grad maxim de arc de intrare și ieșire egal cu doi, iar pentru grafurile plenare dirijate cu un grad maxim de arce de intrare și de ieșire egal cu trei [2] . Reducerea Karp implică, de asemenea, NP-completitudinea problemei setului de vârfuri de tăiere a ciclului pe grafice nedirecționate, iar problema rămâne NP-hard pe grafice cu gradul maxim patru. Problema unui set de vârfuri de tăiere a ciclului poate fi rezolvată în timp polinomial pe grafice cu un grad maxim care nu depășește trei [3] [4] .

Rețineți că sarcina de a elimina cât mai puține muchii posibil pentru a întrerupe ciclurile (într-un grafic nedirecționat) este echivalentă cu găsirea unui arbore de întindere , iar această sarcină poate fi finalizată în timp polinomial . În schimb, problema eliminării muchiilor dintr -un graf direcționat pentru a-l face aciclic , adică problema unui set de arce de tăiere ciclului , este NP-complet [1] .

Algoritmi exacti

Problema corespunzătoare de optimizare NP-completă de găsire a mărimii setului minim de vârfuri de tăiere a ciclului poate fi rezolvată în timp O (1.7347 n ), unde n  este numărul de vârfuri din graficul [5] . De fapt, acest algoritm găsește pădurea maximă generată și complementul acestei păduri va fi setul dorit de vârfuri. Numărul de seturi minime de vârfuri de tăiere a ciclului este limitat la O (1,8638 n ) [6] . Problema setului minim de tăiere a ciclului pentru un graf direcționat poate fi rezolvată în timp O* (1,9977 n ), unde n  este numărul de vârfuri dintr-un graf direcționat dat [7] . Versiunile parametrizate ale problemelor orientate și nedirecționate sunt rezolvabile fix-parametric [8] .

Aproximare

Problema este APX-completă , care decurge direct din complexitatea APX a problemei acoperirii vârfurilor [9] și existenței unei aproximări care păstrează L-reducerea din problema acoperirii vârfurilor la această problemă [1] . Cel mai cunoscut algoritm pentru graficele nedirecționate are un factor de doi [10] .

Borduri

Conform teoremei Erdős-Pose, dimensiunea setului minim de vârfuri de tăiere a ciclului este limitată de factorul logaritmic al numărului maxim de cicluri disjuncte vârf într-un grafic dat [11] .

Aplicații

În sistemele de operare, setul de vârfuri de tăiere a buclei joacă un rol proeminent în detectarea blocajului . În graficul de așteptare al sistemului de operare, fiecare buclă orientată corespunde unui blocaj. Pentru a ieși din toate blocajele, unele procese blocate trebuie să fie terminate. Setul minim de vârfuri de tăiere a ciclului din grafic corespunde numărului minim de procese care ar trebui întrerupte [12]

În plus, setul de cicluri de tăiere a vârfurilor are aplicații în dezvoltarea VLSI [13] .

Note

  1. ↑ 1 2 3 Karp, 1972 .
  2. ↑ Rezultat nepublicat datorat lui Garey și Johnson (Garey, Johnson), vezi Garey, Johnson, 1979 : GT7
  3. ↑ Ueno, Kajitani, Gotoh, 1988 .
  4. ↑ Li, Liu, 1999 .
  5. ↑ Fomin, Villagenger, 2010 .
  6. ↑ Fomin, Gaspers, Pyatkin, Razgon, 2008 .
  7. ↑ Razgon, 2007 .
  8. ↑ Chen, Liu, Lu, O'Sullivan, Razgon, 2008 .
  9. ↑ Dinur, Safra, 2005 .
  10. ↑ Becker, Geiger, 1996 . Vezi și Bafna, Berman, Fujito, 1999 pentru un algoritm alternativ de aproximare cu același coeficient.
  11. ↑ Erdős, Posa, 1965 .
  12. ↑ Silberschatz, Galvin, Gagne, 2008 .
  13. ↑ Festa, Pardalos, Resende, 2000 .

Literatură

Articole și cărți de cercetare

Manuale și articole de recenzie