Tăiere maximă - Maximum cut

Pentru un grafic , o tăiere maximă este o tăietură a cărei dimensiune este cel puțin de dimensiunea oricărei alte tăieturi. Adică este o partiție a vârfurilor grafului în două mulțimi complementare S și T , astfel încât numărul muchiilor dintre mulțimea S și mulțimea T să fie cât mai mare posibil. Problema găsirii unei tăieturi maxime într-un grafic este cunoscută sub numele de Problema de tăiere maximă.

Problema poate fi afirmată pur și simplu după cum urmează. Se dorește un subset S al setului de vârfuri astfel încât numărul muchiilor dintre S și subsetul complementar să fie cât mai mare posibil. În mod echivalent, se dorește un subgraf bipartit al graficului cu cât mai multe margini posibil.

Există o versiune mai generală a problemei numită Max-Cut ponderată, în care fiecare margine este asociată cu un număr real, greutatea sa , iar obiectivul este de a maximiza greutatea totală a marginilor dintre S și complementul său, mai degrabă decât numărul de marginile. Problema Max-Cut ponderată care permite atât greutăți pozitive cât și negative poate fi transformată în mod banal într-o problemă de tăiere minimă ponderată prin răsucirea semnului în toate greutățile.

Complexitatea computațională

Următoarea problemă de decizie legată de reduceri maxime a fost studiată pe larg în domeniul informaticii teoretice :

Fiind dat un graf G și un număr întreg k , a determina dacă există o reducere de dimensiune de cel puțin k în G .

Se știe că această problemă este NP-completă . Este ușor de văzut că problema este în NP : un răspuns da este ușor de demonstrat prin prezentarea unei tăieturi suficient de mari. NP-completitudinea problemei poate fi arătată, de exemplu, printr-o reducere de la maximul de 2 satisfacții (o restricție a problemei de satisfacție maximă ). Versiunea ponderată a problemei deciziei a fost una dintre cele 21 de probleme complete ale Karp ; Karp a arătat completitudinea NP printr-o reducere de la problema partiției .

Varianta de optimizare canonică a problemei de decizie de mai sus este de obicei cunoscută sub numele de Problema de tăiere maximă sau Max-Cut și este definită ca:

Având în vedere un grafic G , găsiți o tăiere maximă.

Se știe că varianta de optimizare este NP-Hard. Problema opusă, aceea de a găsi o reducere minimă, este cunoscută a fi soluționată eficient prin intermediul algoritmului Ford-Fulkerson .

Algoritmi

Algoritmi de timp polinomial

Deoarece problema Max-Cut este NP-hard , nu se cunosc algoritmi de timp polinomial pentru Max-Cut în grafice generale.

Grafice plane

Cu toate acestea, în graficele plane , problema de tăiere maximă este dublă cu problema de inspecție a rutei (problema găsirii unui tur mai scurt care să viziteze fiecare margine a unui grafic cel puțin o dată), în sensul că marginile care nu aparțin unei a unui grafic maxim stabilit cut- G sunt duali marginilor care sunt dublate într - un tur de inspecție optimă a Graficul dublu de G . Turul optim de inspecție formează o curbă de auto-intersecție care separă planul în două subseturi, subsetul de puncte pentru care numărul de înfășurare al curbei este par și subsetul pentru care numărul de înfășurare este impar; aceste două subseturi formează o tăietură care include toate marginile ale căror duale apar de un număr impar de ori în tur. Problema inspecției traseului poate fi rezolvată în timp polinomial, iar această dualitate permite rezolvarea problemei de tăiere maximă și în timp polinomial pentru grafice plane. Cu toate acestea, se știe că problema cu Bisecția maximă este dificilă pentru NP.

Algoritmi de aproximare

Problema Max-Cut este APX-hard , ceea ce înseamnă că nu există o schemă de aproximare timp polinomial (PTAS), în mod arbitrar aproape de soluția optimă, pentru aceasta, cu excepția cazului în care P = NP. Astfel, fiecare algoritm cunoscut de aproximare timp-polinom atinge un raport de aproximare strict mai mic decât unul.

Există un algoritm simplu de randomizare de aproximativ 0,5 : pentru fiecare vârf întoarceți o monedă pentru a decide cărei jumătate a partiției să o atribuiți. În așteptare, jumătate din margini sunt tăiate. Acest algoritm poate fi derandomizat cu metoda probabilităților condiționale ; prin urmare, există și un algoritm simplu de aproximare a 0,5-timp polinomial determinist. Un astfel de algoritm începe cu o partiție arbitrară a vârfurilor grafului dat și mută în mod repetat un vârf la un moment dat de la o parte a partiției la cealaltă, îmbunătățind soluția la fiecare pas, până când nu se mai pot face îmbunătățiri de acest tip . Numărul de iterații este cel mult deoarece algoritmul îmbunătățește tăierea cu cel puțin o margine la fiecare pas. Când algoritmul se termină, cel puțin jumătate din marginile incidente fiecărui vârf aparțin tăieturii, pentru că altfel mutarea vârfului ar îmbunătăți tăierea. Prin urmare, tăietura include cel puțin margini. ${\ displaystyle G = (V, E)}$${\ displaystyle | E |}$${\ displaystyle | E | / 2}$

Algoritmul de aproximare timp polinomial pentru Max-Cut cu cel mai cunoscut raport de aproximare este o metodă de Goemans și Williamson care utilizează programare semidefinită și rotunjire randomizată care atinge un raport de aproximare unde ${\ displaystyle \ alpha \ approx 0.878,}$

${\ displaystyle \ alpha = {\ frac {2} {\ pi}} \ min _ {0 \ leq \ theta \ leq \ pi} {\ frac {\ theta} {1- \ cos \ theta}}.}$

Dacă presupunerea unică a jocurilor este adevărată, acesta este cel mai bun raport de aproximare posibil pentru tăierea maximă. Fără astfel de ipoteze nedovedite, s-a dovedit a fi NP-greu pentru a aproxima valoarea de tăiere maximă cu un raport de aproximare mai bun decât . ${\ displaystyle {\ tfrac {16} {17}} \ approx 0.941}$

Există o analiză extinsă a 10 euristici pentru această problemă, inclusiv implementarea open-source.

Aplicații

Fizica teoretica

În fizica statistică și sistemele dezordonate , problema Max Cut este echivalentă cu minimizarea Hamiltonianului unui model de sticlă rotativă, cel mai simplu modelul Ising . Pentru modelul Ising pe un grafic G și numai interacțiunile cu cel mai apropiat vecin, Hamiltonianul este

${\ displaystyle H [s] = - \ sum _ {ij \ in E (G)} J_ {ij} s_ {i} s_ {j}}$

Aici fiecare vârf i al graficului este un site de rotire care poate lua o valoare de rotire. O configurație de rotire partiționează în două seturi, cele cu rotire în sus și cele cu rotire în jos . Notăm cu setul de margini care conectează cele două seturi. Putem apoi rescrie hamiltonienul ca. ${\ displaystyle s_ {i} = \ pm 1.}$${\ displaystyle V (G)}$${\ displaystyle V ^ {+}}$${\ displaystyle V ^ {-}.}$${\ displaystyle \ delta (V ^ {+})}$

${\ displaystyle {\ begin {align} H [s] & = - \ sum _ {ij \ in E (V ^ {+})} J_ {ij} - \ sum _ {ij \ in E (V ^ {- })} J_ {ij} + \ sum _ {ij \ in \ delta (V ^ {+})} J_ {ij} \\ & = - \ sum _ {ij \ in E (G)} J_ {ij} +2 \ sum _ {ij \ in \ delta (V ^ {+})} J_ {ij} \\ & = C + 2 \ sum _ {ij \ in \ delta (V ^ {+})} J_ {ij } \ end {align}}}$

Minimizarea acestei energii este echivalentă cu problema min-cut sau prin setarea greutăților grafice ca problema max-cut. ${\ displaystyle w_ {ij} = - J_ {ij},}$

Proiectarea circuitului

Problema max cut are aplicații în proiectarea VLSI .

Vezi si

• Tăiere minimă
• K-cut minim
• Ciclu impar transversal , echivalent cu solicitarea celui mai mare subgraf indus de bipartit

Note

Referințe

• Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, Alberto; Protasi, Marco (2003), Complexitate și aproximare: probleme de optimizare combinatorie și proprietățile lor de aproximabilitate , Springer.

Tăierea maximă (versiunea de optimizare) este problema ND14 din Anexa B (pagina 399).

• Garey, Michael R .; Johnson, David S. (1979), Computers and Intractability: A Guide to Theory of NP-Completeness , WH Freeman, ISBN 978-0-7167-1045-5.

Tăierea maximă (versiunea de decizie) este problema ND16 din Anexa A2.2.

Subgraful bipartit maxim (versiunea de decizie) este problema GT25 din Anexa A1.2.

• Gaur, Daya Ram; Krishnamurti, Ramesh (2007), „LP rounding and extensions”, în Gonzalez, Teofilo F. (ed.), Handbook of Approximation Algorithms and Metaheuristics , Chapman & Hall / CRC.
• Goemans, Michel X .; Williamson, David P. (1995), „Algoritmi de aproximare îmbunătățiți pentru probleme maxime de tăiere și satisfacție folosind programarea semidefinită”, Journal of the ACM , 42 (6): 1115–1145, doi : 10.1145 / 227683.227684 , S2CID  15794408.
• Hadlock, F. (1975), „Găsirea unei tăieturi maxime a unui grafic plan în timp polinomial”, SIAM J. Comput. , 4 (3): 221-225, doi : 10.1137 / 0204019.
• Håstad, Johan (2001), „Unele rezultate de inapproximabilitate optimă”, Journal of the ACM , 48 (4): 798-859, doi : 10.1145 / 502090.502098 , S2CID  5120748.
• Jansen, Klaus; Karpinski, Marek ; Lingas, Andrzej; Seidel, Eike (2005), „Scheme de aproximare a timpului polinomial pentru MAX-BISECTION pe grafice plane și geometrice”, SIAM Journal on Computing , 35 (1): 110-119, CiteSeerX  10.1.1.62.5082 , doi : 10.1137 / s009753970139567x.
• Karp, Richard M. (1972), „ Reducibilitatea printre problemele combinatorii ”, în Miller, RE; Thacher, JW (eds.), Complexity of Computer Computation , Plenum Press, pp. 85-103.
• Khot, Subhash ; Kindler, Guy; Mossel, Elchanan; O'Donnell, Ryan (2007), "Rezultate optime de inapproximabilitate pentru MAX-CUT și alte CSP cu 2 variabile?" , SIAM Journal on Computing , 37 (1): 319–357, doi : 10.1137 / S0097539705447372.
• Khuller, Samir; Raghavachari, Balaji; Young, Neal E. (2007), „Metode lacome”, în Gonzalez, Teofilo F. (ed.), Handbook of Approximation Algorithms and Metaheuristics , Chapman & Hall / CRC.
• Mitzenmacher, Michael ; Upfal, Eli (2005), Probability and Computing: Randomized Algorithms and Probabilistic Analysis , Cambridge.
• Motwani, Rajeev ; Raghavan, Prabhakar (1995), Algoritmi aleatori , Cambridge.
• Newman, Alantha (2008), „Max cut”, în Kao, Ming-Yang (ed.), Encyclopedia of Algorithms , Springer, pp. 489–492, doi : 10.1007 / 978-0-387-30162-4_219 , ISBN 978-0-387-30770-1.
• Papadimitriou, Christos H .; Yannakakis, Mihalis (1991), „Optimizare, aproximare și clase de complexitate”, Journal of Computer and System Sciences , 43 (3): 425–440, doi : 10.1016 / 0022-0000 (91) 90023-X.
• Trevisan, Luca ; Sorkin, Gregory; Sudan, Madhu; Williamson, David (2000), „Gadgets, Aproximare și Programare Liniară”, Lucrările celui de-al 37-lea Simpozion IEEE pe Fundamentele Informaticii : 617–626.
• Dunning, Iain ; Gupta, Swati; Silberholz, John (2018), „Ce funcționează cel mai bine când? O evaluare sistematică a euristicii pentru Max-Cut și QUBO”, INFORMS Journal on Computing , 30 (3): 608-624, doi : 10.1287 / ijoc.2017.0798.

linkuri externe

• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger (2000), „Maximum Cut” , în „Un compendiu de probleme de optimizare NP” .
• Andrea Casini, Nicola Rebagliati (2012), „O bibliotecă Python pentru rezolvarea lui Max Cut”