Tăiere maximă a graficului

Tăierea maximă a unui grafic este o tăietură a cărei dimensiune nu este mai mică decât dimensiunea oricărei alte tăieturi. Problema determinării tăieturii maxime pentru un grafic este cunoscută sub numele de problemă a tăierii maxime .

Problema poate fi formulată după cum urmează. O submulțime de vârfuri S ar trebui găsită astfel încât numărul de muchii dintre S și complementul său să fie cât mai mare posibil.

Există o versiune extinsă, problema tăieturii maxime ponderate . În această versiune, fiecărei muchii i se atribuie un număr real, greutatea sa este , iar scopul nu este de a maximiza numărul de muchii, ci greutatea totală a muchiei dintre S și complementul său. Problema tăieturii maxime ponderate este adesea, dar nu întotdeauna, limitată la ponderi nenegative, deoarece ponderile negative pot schimba natura problemei.

Complexitate computațională

Următoarea problemă de solubilitate , legată de tăietura maximă, a fost studiată pe scară largă în informatica teoretică :

Având în vedere un grafic G și un întreg k , determinați dacă există o tăietură în G care este cel puțin k .

Se știe că această problemă este NP-completă . Completitudinea NP a unei probleme poate fi arătată, de exemplu, prin reducerea de la maxim 2-satisfiability problem ( maximum satisfaciability problem cu restricții) [1] . O versiune ponderată a problemei de solubilitate este inclusă în cele 21 de probleme Karp NP-complete [2] . Karp a arătat NP-completitudine prin reducerea problemei partiției .

Varianta de optimizare canonică a problemei de solubilitate de mai sus este cunoscută sub numele de „ problema de tăiere maximă ” și este definită după cum urmează:

Fie dat graficul G , este necesar să găsim tăietura maximă.

Algoritmi de timp polinomial

Deoarece problema de tăiere maximă este NP-hard, nu există algoritmi de timp polinomial pentru problema de tăiere maximă pentru graficele generale.

Pentru graficele plane , însă, problema de tăiere maximă este duală cu problema poștașului chinez (problema găsirii celui mai scurt drum care ocolește toate muchiile cel puțin o dată), în sensul că muchiile care nu aparțin maximului cut of G sunt duale la muchii, care sunt parcurse de multe ori în parcurgerea optimă a graficului dual pentru graficul G . Mersul optim formează o curbă care se autointersectează care împarte planul în două subseturi, un subset de puncte pentru care ordinea în raport cu curba este pară și un subset de puncte pentru care ordinea este impară. Aceste două subseturi formează o tăietură care include toate muchiile care sunt duale cu muchiile care apar de un număr impar de ori în traversare. Problema poștașului chinezesc poate fi rezolvată în timp polinomial, iar această dualitate permite rezolvarea problemei de tăiere maximă pentru grafice plane în timp polinomial [3] . Se știe totuși că problema bisecției maxime este NP-hard [4] .

Algoritmi de aproximare

Problema de tăiere maximă este APX-hard (Papadimitrou și Yannakakis au dovedit MaxSNP-complet pentru această problemă [5] ), ceea ce înseamnă că nu există o schemă de aproximare a timpului polinomial (PTAS) arbitrar apropiată de soluția optimă, cu excepția cazului în care P = NP. Astfel, orice algoritm de aproximare a timpului polinomial dă un coeficient de aproximare , strict mai mic decât unu.

Există un algoritm de aproximare probabilistic simplu de 0,5 - pentru orice vârf, aruncăm o monedă pentru a decide cărei părți a tăieturii îi atribuim acest vârf [6] [7] . Se așteaptă ca jumătate din margini să fie tăiate. Acest algoritm poate fi derandomizat folosind metoda probabilităților condiționate . Astfel, există un algoritm de timp polinomial simplu determinist cu aproximație de 0,5 [8] [9] . Un astfel de algoritm începe cu o partiție arbitrară a vârfurilor unui graf dat și mută un vârf într-un pas dintr-o parte a tăieturii în alta, îmbunătățind soluția la fiecare pas, atâta timp cât este posibilă îmbunătățirea. Numărul de iterații ale algoritmului nu depășește , deoarece algoritmul îmbunătățește tăierea cu cel puțin o muchie. Când algoritmul se oprește, cel puțin jumătate din muchiile incidente oricărui vârf aparțin tăieturii, altfel mutarea vârfului ar îmbunătăți tăierea (mărește dimensiunea tăieturii). Astfel, tăietura include cel puțin margini.

Algoritmul de aproximare în timp polinomial pentru problema de tăiere maximă cu cel mai cunoscut coeficient de aproximare este metoda Gemans și Williamson folosind programare semidefinită și rotunjire probabilistică . Metoda dă un coeficient de aproximare , unde [10] [11] . Dacă ipoteza jocului unic este adevărată, acesta este cel mai bun factor de aproximare posibil pentru tăierea maximă [12] . Cu excepția unor astfel de ipoteze nedovedite, s-a dovedit că este NP-greu să aproximezi valoarea tăieturii maxime cu un factor mai bun decât [13] [14] .

Vezi și

Note

  1. ↑ Garey, Johnson, 1979 .
  2. ↑ Karp, 1972 .
  3. ↑ Hadlock, 1975 .
  4. ↑ Jansen, Karpinski, Lingas, Seidel, 2005 .
  5. ↑ Papadimitriou & Yannakakis, 1991 .
  6. ↑ Mitzenmacher, Upfal, 2005 , p. Sectă. 6.2.
  7. ↑ Motwani, Raghavan, 1995 , p. Sectă. 5.1.
  8. ↑ Mitzenmacher, Upfal, 2005 , p. Sectă. 6.3..
  9. ↑ Khuller, Raghavachari, Young, 2007 .
  10. ↑ Gaur, Krishnamurti, 2007 .
  11. ↑ Ausiello, Crescenzi et al., 2003 .
  12. ↑ Khot, Kindler, Mossel, O'Donnell, 2007 .
  13. ↑ Håstad, 2001 .
  14. ↑ Trevisan, Sorkin, Sudan, Williamson, 2000 .

Literatură

Problema de tăiere maximă (versiunea optimizată) este problema ND14 din Anexa B (p. 399). Problema de tăiere maximă (problema de solubilitate) este problema ND16 din Anexa A2.2. Subgraful bipartit maxim (problema de rezoluție) este problema GT25 din Anexa A1.2.

Lectură suplimentară

Link -uri