Maksimalno odsecanje
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Max-cut.svg/200px-Max-cut.svg.png)
Za graf, maksimalno odsecanje je odsecanje čija je veličina barem jednaka veličini bilo kog drugog odsecanja. Problem pronalaženja maksimalnog odsecanja u grafu poznat je kao Problem maksimalnog odsecanja.
Problem se može predstaviti na sledeći način. Želimo da pronađemo podskup S skupa čvorova grafa, takav da je broj ivica između čvorova iz S i komplementarnog podskupa što veći mogući.
Naprednija verzija ovog problema zove se težinsko maksimalno odsecanje. U ovoj verziji svakoj ivici pridružen je broj, tj. njena težina, a cilj je postići maksimalnu težinu ivica između S i njegovog komplementa, a ne njihov maksimalan broj. Ovaj problem je često, ali ne uvek, ograničen tako da su težine ivica samo pozitivne vrednosti, zato što negativne vrednosti težina mogu promeniti pripodu samog problema.
Složenost izračunavanja
Problem odlučivanja, koji sledi, vezan za maksimalna odsecanja proučava se u okviru teorijske informatike:
- Dat je graf G i prirodni broj k, odrediti da li u G postoji odsecanje čija je veličina barem k.
Za ovaj problem je poznato da je NP-kompletan. Lako je videti da je problem u NP: odgovor da je lako dokazati obezbeđivanjem dovoljno velikog odsecanja. NP kompletnost se može pokazati, na primer, transformacijom iz maksimum 2-zadovoljivosti ( koji je restrikcija problema maksimalne zadovoljivosti).[1] Verzija problema odlučivanja sa težinama bila je jedan od Karpovih 21 NP-kompletnih problema;[2] Karp je pokazao NP-kompletnost redukcijom sa problema particionisanja.
Kanonska optimizaciona varijanta gore navedenog problema odlučivanja poznata je kao Problem maksimalnog odsecanja ili Maksimalno odecanje i definisana je kao:
- Dat je graf G, pronaći maksimalno odsecanje.
Algoritmi polinomijalnog vremena
Pošto je Problem maksimalnog odsecanja NP-težak, nisu poznati uopšteni algoritmi polinomijalnog vremena za ovaj problem.
Međutim, kod planarnih grafova, Problem maksimalnog odsecanja je dual Problemu ispitivanja puta (problem nalaženja najkraće putanje, kojom se svaka ivica grafa posećuje barem jednom), u smislu da su ivice koje ne pripadaju maksimalnom odsecanju grafa G duali ivica koje se ponavljaju u optimalnom ispitivanju puta dualnog grafa grafa G. Optimalno ispitivanje puta formira samopresecajuću krivu koja deli ravan na dva podskupa, podskup tačaka za koje je winding broj krive paran i podskup za koje je taj broj neparan. Ova dva podskupa formiraju odsecanje koje uključuje sve ivice čiji duali imaju neparan broj pojavljivanja u putu. Problem ispitivanja puta se može rešiti u polinomijalnom vremenu, a ova dualnost daje mogućnost da se kod planarnih grafova i Problem maksimalnog odsecanja takođe može rešiti u polinomijalnom vremenu.[3]
Algoritmi aproksimizacije
Problem maksimalnog odsecanja je APX-težak,[4] što znači da ne postoji šema aproksimizacije u polinomijalnom vremenu, proizvoljno blizu optimalnom rešenju, za njega, osim u slučaju P = NP. Stoga, svaki algoritam aproksimizacije u polinomijalnom vremenu ima koeficijent aproksimizacije striktno manje od jedan.
Postoji jednostavan nasumični 0,5-algoritam aproksimizacije: za svaki čvor bacanjem novčića utvrditi kojoj ga particiji treba dodeliti.[5][6] Očekujemo da polovina ivica budu ivice odsecanja. Nasumičnost algoritma se može izbeći primenom metoda uslovnih verovatnoća; dakle postoji i jednostavan deterministički 0.5-algoritam aproksimizacije polinomijalnog vremena.[7][8] Jedan takav algoritam počinje sa proizvoljnom particijom čvorova datog grafa i pomera čvorove jedan po jedan, u više koraka, sa jedne strane particije na drugu, poboljšavajući rešenje svakim korakom, sve dok se mogu napraviti poboljšanja ovog tipa. Broj iteracija je najviše zato što algoritam poboljšava odsecanje barem za jednu ivicu svakim korakom. Po završetku algoritma, najmanje polovina ivica vezanih za sve čvorove pripada odsecanju, jer bi inače pomeranje čvorova poboljšalo odsecanje. Stoga odsecanje uključuje najmanje ivica.
Aproksimizacioni algoritam polinomijalnog vremena sa najboljim koeficijentom aproksimizacije je metod Goemans-a i Williamson-a koristeći semidefinitno programiranje i nasumično zaokruživanje koji daje koeficijent aproksimizacije , gde je .[9][10] Ako je unique games pretpostavka tačna, ovo je najbolji mogući koeficijent aproksimizacije za maksimalno odsecanje.[11] Bez takvih nedokazanih pretpostavki, dokazano je da je NP-teško aproksimizovati vrednost maksimalnog odsecanja sa koeficijentom aproksimizacije boljim od .[12][13]
Maksimalni bipartitivni podgraf
Odsecanje je bipartitivni graf. Problem maksimalnog odsecanja je u suštini isti kao problem pronalaženja bipartitivnog podgrafa sa najviše ivica.
Neka je graf i neka je bipartitivni podgraf od G. Onda postoji particija (S, T) V takva da svaka ivica u X ima jednu tačku u S a drugu u T. Drugim rečima, postoji odsecanje u H takvo da skup ivica odsecanja sadrži X. Dakle postoji odsecanje u grafu G takvo da je skup ivica odsecanja nadskup od X.
Obrnuto, neka je graf i neka je X skup ivica odsecanja. Onda je math>H=(V,X)</math> bipartitivni podgraf od H.
Ukratko, ako postoji bipartitivni graf sa k ivica, postoji odsecanje sa barem k ivica odsecanja, i ako postoji odsecanje sa k ivica, postoji i bipartitivni graf sa k ivica.
Stoga je problem pronalaženja maksimalnog bipartitivnog podgrafa suštinski isti kao problem pronalaženja maksimalnog odsecanja.[14]
Reference
- ^ Garey & Johnson 1979
- ^ Karp 1972
- ^ Hadlock 1975
- ^ Papadimitriou & Yannakakis 1991 prove MaxSNP-completeness.
- ^ Mitzenmacher & Upfal 2005, Sect. 6.2.
- ^ Motwani & Raghavan 1995, Sect. 5.1.
- ^ Mitzenmacher & Upfal 2005, Sect. 6.3.
- ^ Khuller, Raghavachari & Young 2007
- ^ Gaur & Krishnamurti 2007
- ^ Ausiello et al. 2003
- ^ Khot et al. 2007
- ^ Håstad 2001
- ^ Trevisan et al. 2000
- ^ Newman 2008
Literatura
- Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, Alberto; Protasi, Marco (2003), Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer .
- Maximum cut (optimisation version) is the problem ND14 in Appendix B (pp. 399).
- Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 978-0-7167-1045-5 .
- Maximum cut (decision version) is the problem ND16 in Appendix A2.2.
- Maximum bipartite subgraph (decision version) is the problem GT25 in Appendix A1.2.
- Gaur, Daya Ram; Krishnamurti, Ramesh (2007), „LP rounding and extensions”, Ур.: Gonzalez, Teofilo F., Handbook of Approximation Algorithms and Metaheuristics, Chapman & Hall/CRC .
- Goemans, Michel X.; Williamson, David P. (1995), „Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming”, Journal of the ACM, 42 (6): 1115—1145, doi:10.1145/227683.227684 .
- Hadlock, F. (1975), „Finding a Maximum Cut of a Planar Graph in Polynomial Time”, SIAM J. Comput., 4 (3): 221—225, doi:10.1137/0204019 .
- Håstad, Johan (2001), „Some optimal inapproximability results”, Journal of the ACM, 48 (4): 798—859, doi:10.1145/502090.502098 .
- Jansen, Klaus; Karpinski, Marek; Lingas, Andrzej; Seidel, Eike (2005), „Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs”, SIAM Journal on Computing, 35 (1), doi:10.1137/s009753970139567x .
- Karp, Richard M. (1972), „Reducibility among combinatorial problems”, Ур.: Miller, R. E.; Thacher, J. W., Complexity of Computer Computation, Plenum Press, стр. 85—103 .
- Khot, Subhash; Kindler, Guy; Mossel, Elchanan; O'Donnell, Ryan (2007), „Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?”, SIAM Journal on Computing, 37 (1): 319—357, doi:10.1137/S0097539705447372 .
- Khuller, Samir; Raghavachari, Balaji; Young, Neal E. (2007), „Greedy methods”, Ур.: Gonzalez, Teofilo F., 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), Randomized Algorithms, Cambridge .
- Newman, Alantha (2008), „Max cut”, Ур.: Kao, Ming-Yang, Encyclopedia of Algorithms, Springer, стр. 1, ISBN 978-0-387-30770-1, doi:10.1007/978-0-387-30162-4_219 .
- Papadimitriou, Christos H.; Yannakakis, Mihalis (1991), „Optimization, approximation, and complexity classes”, 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, Approximation, and Linear Programming”, Proceedings of the 37th IEEE Symposium on Foundations of Computer Science: 617—626 .
Spoljašnje veze
- Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger (2000), "Maximum Cut", in "A compendium of NP optimization problems".
- Andrea Casini, Nicola Rebagliati (2012), "A Python library for solving Max Cut"