Tăiere maximă

O tăiere maximă

Într-un grafic , o tăiere maximă este o tăietură de cel puțin aceeași dimensiune ca toate celelalte tăieturi. Problema găsirii unei tăieturi maxime într-un grafic este cunoscută sub numele de problema tăierii maxime .

Problema poate fi afirmată pur și simplu după cum urmează. Vrem să obținem un subset S al setului de vârfuri astfel încât numărul de muchii dintre S și mulțimea complementară să aibă cea mai mare cardinalitate posibilă.

Există o versiune mai avansată a problemei, care se referă la grafice ponderate . În această versiune, fiecare arc este asociat cu un număr real, numit „greutate”, iar obiectivul problemei este de a maximiza nu numărul de arce, ci greutatea totală a arcelor între S și complementul său. Problema max-cut pe graficele ponderate este de obicei limitată la greutăți non-negative, deoarece greutățile negative pot provoca o problemă de altă natură.

Complexitatea computațională

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

Dat fiind un grafic G și un număr întreg k , determinați dacă există o tăietură de dimensiune cel puțin k în G.

Se știe că problema este NP-completă . Verificarea faptului că problema este cel mult NP este simplă: fiecare soluție poate fi verificată într-un timp scurt, adică timpul necesar pentru a calcula cardinalitatea setului de tăieturi specifice și a efectua comparația cu k . În schimb, completitudinea NP poate fi demonstrată, de exemplu, prin reducerea din MAX-2-SAT, cunoscută problemă NP-difficile . ^[1] Versiunea ponderată a acestei probleme de decizie a fost una dintre cele 21 de probleme NP-complete ale lui Karp ; ^[2] Karp a arătat completitudinea NP prin reducerea problemei partiției .

Varianta canonică, prezentată ca o problemă de optimizare , este definită ca:

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

Algoritmi polinomiali

Problema max-cut este NP-dificilă, deci nu se cunoaște nicio problemă care să o rezolve în timp polinomial pe un grafic generic.

Cu toate acestea, într-un grafic plan , problema este duală cu cea a poștașului chinez (problema găsirii celei mai scurte căi care vizitează fiecare arc al graficului cel puțin o dată), în sensul că arcurile care nu aparțin tăieturii -setul maxim al unui grafic G sunt corespondenții marginilor dublate în vizita optimă a graficului dual al lui G. Această corespondență permite rezolvarea problemei forfecării maxime pe grafele plane în timp polinomial. ^[3]

Algoritmi de aproximare

Problema max-cut este APX-hard, ^[4] adică nu există o schemă de aproximare timp polinomial pentru aceasta, cu excepția cazului în care P = NP . Astfel, fiecare algoritm de aproximare atinge un raport de aproximare strict mai mic decât unul.

Există un algoritm simplu randomizat cu aproximativ 0,5: pentru fiecare vârf întoarceți o monedă pentru a decide cărei partiții să o atribuiți. ^[5] ^[6] Valoarea așteptată a arcurilor aparținând setului de tăieturi este ${\frac {|E|}{2}}$ ${\ displaystyle {\ frac {| E |} {2}}}$ ${\ displaystyle {\ frac {| E |} {2}}}$ . Acest algoritm poate fi „derandomizat” cu metoda probabilității condiționale, devenind un algoritm determinist simplu care aproximează în timp polinomial soluția optimă a problemei cu indicele de aproximare 0,5. ^[7] ^[8]

Subgraf bipartit maxim

O tăietură este un grafic bipartit . Problema max-cut este echivalentă cu găsirea subgrafului bipartit cu mai multe arce.

Lasa-i sa fie $G=(V,E)$ ${\ displaystyle G = (V, E)}$ ${\ displaystyle G = (V, E)}$ un grafic și $H=(V,X)$ ${\ displaystyle H = (V, X)}$ ${\ displaystyle H = (V, X)}$ un subgraf bipartit al lui G. Apoi, există o partiție $(S,T)$ ${\ displaystyle (S, T)}$ ${\ displaystyle (S, T)}$ de V astfel încât fiecare arc din X are o extremă în S și cealaltă în T. Cu alte cuvinte, există o tăietură în H astfel încât setul de tăieturi să conțină X. Deci, există o tăietură în G astfel încât setul de tăieturi să fie un superset de X.

Dimpotrivă, sunt $G=(V,E)$ ${\ displaystyle G = (V, E)}$ ${\ displaystyle G = (V, E)}$ un grafic și X într-un set de margini. Atunci $H=(V,X)$ ${\ displaystyle H = (V, X)}$ ${\ displaystyle H = (V, X)}$ este un subgraf bipartit al lui G.

În rezumat, având în vedere un subgraf bipartit cu k arce, există o tăietură cu un set de tăieturi de cel puțin k arce și invers. În consecință, problema găsirii unui subgraf bipartit maxim este în esență aceeași problemă a găsirii unei limite maxime. ^[9] Aceleași concluzii se aplică problemei în cauză din punctul de vedere al complexității de calcul.

Note

^ Garey-Johnson, 1979 .
^ Karp, 1972
^ Hadlock, 1975 .
^ Papadimitriou-Yannakakis, 1991 , dovada completitudinii MaxSNP .
^ Mitzenmacher-Upfal, 2005 , secțiunea 6.2 .
^ Motwani-Raghavan, 1995 , sect. 5.1 .
^ Mitzenmacher-Upfal, 2005 , secțiunea 6.3 .
^ Khuller-Raghavachari-Young, 2007 .
^ Newman, 2008 .

Bibliografie

Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela și Marco Protasi, Complexitate și aproximare: probleme de optimizare combinatorie și proprietățile lor de aproximabilitate , Springer, 2003.
Michael R. Garey și David S. Johnson ,Computers and Intractability: A Guide to Theory of NP-Completeness , WH Freeman, 1979, ISBN 0-7167-1045-5 .
Daya Ram Gaur și Ramesh Krishnamurti, LP rotunjire și extensii , în Handbook of Approximation Algorithms and Metaheuristics , Chapman & Hall / CRC, 2007.
Michel X. Goemans și David P. Williamson , Algoritmi de aproximare îmbunătățiți pentru probleme maxime de tăiere și satisfacție folosind programarea semidefinită , în Jurnalul ACM , vol. 42, n. 6, 1995, pp. 1115–1145, DOI : 10.1145 / 227683.227684 .
F. Hadlock, Găsirea unei tăieturi maxime a unui grafic plan în timp polinomial , în SIAM J. Comput. , vol. 4, nr. 3, 1975, pp. 221-225, DOI : 10.1137 / 0204019 .
Johan Håstad , Unele rezultate de inapproximabilitate optimă , în Jurnalul ACM , vol. 48, nr. 4, 2001, pp. 798–859, DOI : 10.1145 / 502090.502098 .
Klaus Jansen, Marek Karpinski , Andrzej Lingas și Eike Seidel, Scheme de aproximare a timpului polinomial pentru MAX-BISECȚIE pe grafice plane și geometrice , în SIAM Journal on Computing , vol. 35, nr. 1, 2005, DOI : 10.1137 / s009753970139567x .
Richard M. Karp , Reducibilitatea printre problemele combinatorii , în Complexitatea calculelor computerizate , Plenum Press, 1972, pp. 85-103.
Subhash Khot , Guy Kindler, Elchanan Mossel și Ryan O'Donnell, Rezultate de inapproximabilitate optimă pentru MAX-CUT și alte CSP cu 2 variabile? , în SIAM Journal on Computing , vol. 37, n. 1, 2007, pp. 319–357, DOI : 10.1137 / S0097539705447372 .
Samir Khuller, Balaji Raghavachari și Neal E. Young, Metode lacome, în Manualul de algoritmi de aproximare și metaheuristică , Chapman & Hall / CRC, 2007.
Michael Mitzenmacher și Eli Upfal , Probabilitate și calcul: algoritmi aleatori și analiză probabilistică , Cambridge, 2005.
Rajeev Motwani și Prabhakar Raghavan, Algoritmi aleatori , Cambridge, 1995.
Alantha Newman, Max cut , în Encyclopedia of Algorithms , Springer, 2008, p. 1, DOI : 10.1007 / 978-0-387-30162-4_219 , ISBN 978-0-387-30770-1 .
Christos H. Papadimitriou și Mihalis Yannakakis , clase de optimizare, aproximare și complexitate , în Journal of Computer and System Sciences , vol. 43, nr. 3, 1991, pp. 425-440, DOI : 10.1016 / 0022-0000 (91) 90023-X .
Luca Trevisan , Gregory Sorkin, Madhu Sudan și David Williamson, Gadgets, Aproximare și programare liniară , în Proceedings of the 37th IEEE Symposium on Foundations of Computer Science , 2000, pp. 617-626.
Francisco Barahona, Martin Grötschel, Michael Jünger și Gerhard Reinelt, O aplicație de optimizare combinatorie la fizica statistică și proiectarea schemei de circuite , în Operations Research , vol. 36, n. 3, 1988, pp. 493-513, DOI : 10.1287 / opre . 36.3.493 , JSTOR 170992 .

linkuri externe

( EN ) Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard J. Woeginger, Maximum Cut , în Un compendiu de probleme de optimizare NP , Institutul Regal de Tehnologie KTH, 2000.
( RO ) Andrea Casini, Nicola Rebagliati, O bibliotecă Python pentru rezolvarea lui Max Cut , pe code.google.com , 2012.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] Garey-Johnson, 1979 .

[2] Karp, 1972

[3] Hadlock, 1975 .

[4] Papadimitriou-Yannakakis, 1991 , dovada completitudinii MaxSNP .

[5] Mitzenmacher-Upfal, 2005 , secțiunea 6.2 .

[6] Motwani-Raghavan, 1995 , sect. 5.1 .

[7] Mitzenmacher-Upfal, 2005 , secțiunea 6.3 .

[8] Khuller-Raghavachari-Young, 2007 .

[9] Newman, 2008 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]