În teoria grafurilor, un graf direcționat poate conține cicluri direcționate , un inel de arce care au aceeași direcție. În unele aplicații, astfel de cicluri sunt nedorite, le putem elimina și obține un grafic aciclic direcționat (Grafic aciclic direcționat, DAG). O modalitate de a elimina arcele este să eliminați pur și simplu arcele din grafic. Un set de arc de feedback ( FAS ) sau un set de muchii de tăiere a ciclului este un set de arce care, atunci când sunt îndepărtate dintr-un grafic, formează un DAG. Privit dintr-un unghi diferit, este un set care conține cel puțin o muchie din fiecare ciclu al graficului.
Un concept strâns înrudit este setul de vârfuri de tăiere a ciclului, care include cel puțin un vârf din fiecare ciclu al unui grafic direcționat, și arborele de întindere minim , care este o versiune nedirecționată a problemei găsirii unui set de arce de tăiere a ciclului.
Un set minim de arce de tăiere a ciclului (care nu poate fi redus în dimensiune prin eliminarea muchiilor) are proprietatea suplimentară că, dacă muchiile sale sunt inversate mai degrabă decât îndepărtate, graficul rămâne aciclic. Găsirea unui set mic de muchii cu această proprietate este un pas cheie în stratificarea unui grafic [1] [2] .
Uneori este de dorit să se arunce cât mai puține arce posibil, formând cel mai mic set de arce de tăiere a ciclului sau cel mai mare subgraf aciclic dublu . Problema este o problemă complexă de calcul pentru care au fost dezvoltate câteva soluții de aproximare.
Ca exemplu simplu, imaginați-vă următoarea situație ipotetică în care trebuie făcut ceva pentru a obține ceva:
Putem exprima această situație ca o problemă pe un grafic. Fie ca fiecare vârf să reprezinte un element și adăugăm un arc de la A la B dacă trebuie să avem A pentru a obține B. Din păcate, nu aveți niciunul dintre aceste trei lucruri și, deoarece graficul este ciclic, nu puteți avea oricare dintre acele lucruri.get.
Totuși, să presupunem că îi dai lui George 100 de dolari pentru pianul lui. Dacă le acceptă, va elimina arcul de la mașina de tuns iarba la pian. Astfel, ciclul este rupt și poți face două schimburi pentru a obține râvnita mașină de tuns iarba. Acest arc unic constituie un set de arce de tăiere a ciclului.
Ca și în exemplul de mai sus, există de obicei un anumit preț asociat cu întreruperea arcului. Din acest motiv, este de dorit să eliminați cât mai puține arce posibil. Ștergerea unui singur arc este suficientă pentru a întrerupe un ciclu simplu, dar, în general, găsirea celui mai mic număr de arce de șters este o problemă dificilă NP și se numește cel mai mic set de arce de tăiere a ciclului sau cea mai mare problemă a subgrafului aciclic.
Această problemă este deosebit de dificilă pentru graficele k - muchii conectate pentru k mare , unde fiecare arc se termină în multe cicluri diferite. Problema de solubilitate , care este NP-completă , întreabă dacă este posibil să tăiați toate ciclurile eliminând cel mult k arce. Această problemă este inclusă în lista lui Karp cu 21 de probleme NP-complete [3] [4] .
Fiind NP-complet, problema găsirii unui set de cicluri de tăiere a arcurilor este fix-parametric rezolvabilă — există un algoritm de rezolvare, al cărui timp de rulare depinde polinom de mărimea graficului de intrare (dar nu depinde de numărul de muchii), dar timpul depinde exponențial de numărul de muchii din setul de arce de tăiere ciclului [5] .
Viggo Kann a arătat în 1992 că problema găsirii setului minim de arc de tăiere a ciclului este APX-hard , ceea ce înseamnă că există o constantă c astfel încât, presupunând P≠NP, nu există un algoritm de aproximare în timp polinomial , care întotdeauna găsește un set de muchii de cel mult c ori mai mare decât cel optim [6] [7] . Până în 2006, cea mai mare valoare a lui c , pentru care se știe că nu există un astfel de algoritm, este egală cu c = 1,3606 [8] . Cel mai cunoscut algoritm de aproximare are o estimare a lui O (log n log log n ) [7] [9] . Pentru problema duală a aproximării numărului de muchii dintr-un subgraf aciclic, este posibil un algoritm cu un coeficient puțin mai bun decât 1/2 [10] [11] .
Dacă digrafele de intrare sunt limitate la turnee , problema este cunoscută sub numele de problemă de setare a arcului de feedback minim la turnee ( FAST ). Această problemă restrânsă permite o schemă de timp polinomială aproximativă și această afirmație rămâne adevărată pentru versiunea ponderată restrânsă a problemei [12] . Un algoritm cu un parametru sub-exponențial fix pentru FAST ponderat a fost propus de Karpinski și Schudi [13] .
Pe de altă parte, dacă muchiile sunt nedirecționate , sarcina de a elimina muchiile pentru a ajunge la un grafic fără ciclu este echivalentă cu găsirea unui arbore de acoperire minim , care poate fi făcut cu ușurință în timp polinomial.
Unii algoritmi de aproximare au fost dezvoltați pentru problema [14] . Un algoritm foarte simplu este următorul:
Acum, atât L , cât și R sunt subgrafe aciclice ale lui G și cel puțin unul dintre aceste grafice are cel mult jumătate din dimensiunea unui subgraf aciclic maxim [15] .