Maximális grafikonvágás

A gráf maximális vágása olyan vágás , amelynek mérete nem kisebb, mint bármely más vágás mérete. A gráf maximális vágási értékének meghatározásának problémáját maximális vágási problémaként ismerjük .

A probléma a következőképpen fogalmazható meg. Meg kell találni az S csúcsok egy részhalmazát , hogy az S és a komplementere közötti élek száma a lehető legnagyobb legyen.

Van egy kiterjesztett változat, a súlyozott maximális vágási probléma . Ebben a változatban minden élhez valós szám van hozzárendelve, súlya , és nem az élek számának maximalizálása a cél, hanem az S és a komplementere közötti teljes élsúly. A súlyozott maximális vágási probléma gyakran, de nem mindig, nem negatív súlyokra korlátozódik, mivel a negatív súlyok megváltoztathatják a probléma természetét.

Számítási összetettség

A következő , a maximális vágással kapcsolatos megoldhatósági problémát széles körben tanulmányozták az elméleti számítástechnikában :

Adott egy G gráf és egy k egész szám, határozzuk meg, hogy van-e G -ben olyan vágás, amely legalább k .

Ez a probléma köztudottan NP-teljes . Egy probléma NP-teljessége megmutatható például úgy, hogy a maximum 2-es kielégíthetőségi problémából ( maximális kielégítési probléma korlátozásokkal) [1] csökkentjük . A megoldhatósági probléma súlyozott változatát tartalmazza a 21 NP-teljes Karp probléma [2] . Karp NP-teljességet mutatott ki a partíciós probléma redukálásával .

A fenti megoldhatósági probléma kanonikus optimalizálási változata „ maximális vágási probléma ” néven ismert, és a következőképpen definiálható:

Legyen adott a G gráf , meg kell találni a maximális vágást.

Polinom idő algoritmusok

Mivel a maximális vágási probléma NP-nehéz, az általános gráfok maximális vágási problémájához nincsenek polinomiális idő algoritmusok.

Síkgráfok esetében azonban a maximális vágási probléma kettős a kínai postás problémával (a legrövidebb út megtalálásának problémája, amely legalább egyszer megkerül minden élt), abban az értelemben, hogy azok az élek, amelyek nem tartoznak a maximumhoz G metszéspontja kettős élek, amelyek a G gráf duális gráfjának optimális bejárása során sokszorosan bejárnak . Az optimális séta egy önmetsző görbét képez, amely a síkot két részhalmazra osztja, egy részhalmazra, ahol a görbe szerinti sorrend páros, és egy részhalmazra, amelynél a sorrend páratlan. Ez a két részhalmaz egy vágást alkot, amely magában foglalja az összes olyan élt, amely kettős a bejárás során páratlan számú élekkel. A kínai postás probléma megoldható polinomidőben, és ez a kettősség lehetővé teszi a síkgráfok maximális vágási feladatának polinomiális időben történő megoldását [3] . Ismeretes azonban, hogy a maximális felezési probléma NP-nehéz [4] .

Közelítő algoritmusok

A maximális vágási probléma APX-nehéz (Papadimitrou és Yannakakis MaxSNP-teljesnek bizonyult erre a problémára [5] ), ami azt jelenti, hogy nincs polinomiális időközelítési séma (PTAS) tetszőlegesen közel az optimális megoldáshoz, hacsak nem P = NP. Így a polinomidő bármely közelítő algoritmusa közelítési együtthatót ad , amely szigorúan kisebb, mint egy.

Létezik egy egyszerű valószínűségi 0,5 -közelítési algoritmus - bármely csúcsra dobunk egy érmét, hogy eldöntsük, a vágás melyik részének tulajdonítsuk ezt a csúcsot [6] [7] . A szélek fele várhatóan le lesz vágva. Ez az algoritmus derandomizálható a feltételes valószínűségek módszerével . Így van egy egyszerű determinisztikus polinomiális idő algoritmus 0,5-es közelítéssel [8] [9] . Az egyik ilyen algoritmus egy adott gráf csúcsainak tetszőleges felosztásával indul, és az egyik csúcsot egy lépésben a vágás egyik részéből a másikba mozgatja, minden lépésben javítva a megoldást, ameddig csak lehetséges. Az algoritmus iterációinak száma nem haladja meg a -t, mivel az algoritmus legalább egy éllel javítja a vágást. Amikor az algoritmus leáll, a bármely csúcsra beeső élek legalább fele a vágáshoz tartozik, különben a csúcs mozgatása javítaná a vágást (megnövelné a vágás méretét). Így a vágás legalább éleket tartalmaz.

A maximális vágási probléma polinomiális idejű közelítő algoritmusa a legismertebb közelítési együtthatóval a Gemans és Williamson módszer, amely félig határozott programozást és valószínűségi kerekítést alkalmaz . A módszer egy közelítési együtthatót ad , ahol [10] [11] . Ha az egyedi játékhipotézis igaz, ez a lehető legjobb közelítési tényező a maximális vágáshoz [12] . Az ilyen nem bizonyított feltevések nélkül bebizonyosodott, hogy NP-nehéz közelíteni a maximális vágás értékét [13] [14] -nél jobb tényezővel .

Lásd még

Jegyzetek

  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. Szekta. 6.2.
  7. ↑ Motwani, Raghavan, 1995 , p. Szekta. 5.1.
  8. ↑ Mitzenmacher, Upfal, 2005 , p. Szekta. 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, Szudán, Williamson, 2000 .

Irodalom

A maximális vágási probléma (optimalizált változat) az ND14 probléma a B függelékben (399. oldal). A maximális vágási probléma (megoldhatósági probléma) az ND16 probléma az A2.2. függelékben. A maximális bipartit részgráf (feloldhatósági probléma) a GT25 probléma az A1.2. függelékben.

További olvasnivalók

Linkek