Maximalt grafsnitt

Det maximala snittet för en graf är ett snitt vars storlek inte är mindre än storleken på något annat snitt. Problemet med att bestämma det maximala skäret för en graf är känt som det maximala skärningsproblemet .

Problemet kan formuleras på följande sätt. En delmängd av hörn S bör hittas så att antalet kanter mellan S och dess komplement är så stort som möjligt.

Det finns en utökad version, det viktade maximala skärproblemet . I den här versionen tilldelas varje kant ett reellt nummer, dess vikt är , och målet är inte att maximera antalet kanter, utan den totala kantvikten mellan S och dess komplement. Det viktade maximala skärproblemet är ofta, men inte alltid, begränsat till icke-negativa vikter eftersom negativa vikter kan förändra problemets karaktär.

Beräkningskomplexitet

Följande lösbarhetsproblem , relaterat till det maximala snittet, har studerats allmänt inom teoretisk datavetenskap :

Givet en graf G och ett heltal k , bestäm om det finns ett snitt i G som är minst k .

Detta problem är känt för att vara NP-komplett . Ett problems NP-fullständighet kan till exempel visas genom att reducera från det maximala 2-tillfredsställelseproblemet ( maximalt tillfredsställande problem med restriktioner) [1] . En viktad version av lösbarhetsproblemet ingår i de 21 NP-kompletta Karpproblemen [2] . Karp visade NP-fullständighet genom reduktion från partitionsproblemet .

Den kanoniska optimeringsvarianten av ovanstående lösbarhetsproblem är känt som " maximal cut-problemet " och definieras enligt följande:

Låt grafen G ges , det är nödvändigt att hitta den maximala skärningen.

Polynomtidsalgoritmer

Eftersom det maximala skärningsproblemet är NP-hårt, finns det inga polynomtidsalgoritmer för det maximala skärningsproblemet för allmänna grafer.

För plana grafer är dock det maximala skärproblemet dubbelt med det kinesiska brevbärarproblemet (problemet med att hitta den kortaste vägen som går runt alla kanter minst en gång), i den meningen att kanter som inte hör till det maximala snitt av G är dubbla kanter, som genomkorsas många gånger i den optimala genomgången av den dubbla grafen för grafen G . Den optimala promenaden bildar en självkorsande kurva som delar upp planet i två delmängder, en delmängd av punkter för vilka ordningen med avseende på kurvan är jämn, och en delmängd av punkter för vilka ordningen är udda. Dessa två delmängder bildar ett snitt som inkluderar alla kanter som är dubbla till kanter som visas ett udda antal gånger i traverseringen. Det kinesiska brevbärarproblemet kan lösas i polynomtid, och denna dualitet gör att det maximala skärningsproblemet kan lösas för plana grafer i polynomtid [3] . Det är dock känt att det maximala bisektionsproblemet är NP-hårt [4] .

Approximationsalgoritmer

Det maximala skärningsproblemet är APX-hårt (Papadimitrou och Yannakakis visade att MaxSNP är komplett för detta problem [5] ), vilket innebär att det inte finns något polynomiellt tidsapproximationsschema (PTAS) godtyckligt nära den optimala lösningen, såvida inte P = NP. Således ger varje approximationsalgoritm för polynomtid en approximationskoefficient , strikt mindre än en.

Det finns en enkel probabilistisk 0,5 -approximationsalgoritm - för vilken vertex som helst, vi kastar ett mynt för att bestämma vilken del av snittet som ska tillskrivas denna vertex [6] [7] . Hälften av kanterna förväntas vara skärande. Denna algoritm kan avrandomiseras med metoden för villkorade sannolikheter . Det finns alltså en enkel deterministisk polynomtidsalgoritm med 0,5-approximation [8] [9] . En sådan algoritm börjar med en godtycklig uppdelning av hörnen i en given graf och flyttar en vertex i ett steg från en del av snittet till en annan, vilket förbättrar lösningen vid varje steg så länge förbättring är möjlig. Antalet iterationer av algoritmen överstiger inte , eftersom algoritmen förbättrar skärningen med minst en kant. När algoritmen stannar tillhör minst hälften av de kanter som faller på valfri vertex till snittet, annars skulle en flyttning av vertex förbättra snittet (öka storleken på snittet). Sålunda innefattar snittet åtminstone kanter.

Polynom-tidsapproximationsalgoritmen för det maximala skärningsproblemet med den mest kända approximationskoefficienten är Gemans och Williamson-metoden som använder semidefinitiv programmering och probabilistisk avrundning . Metoden ger en approximationskoefficient , där [10] [11] . Om den unika spelhypotesen är sann, är detta den bästa möjliga approximationsfaktorn för det maximala snittet [12] . Bortsett från sådana obevisade antaganden, har det bevisats att det är NP-svårt att approximera värdet av det maximala skäret med en faktor bättre än [13] [14] .

Se även

Anteckningar

  1. ↑ Garey, Johnson, 1979 .
  2. ↑ Karp, 1972 .
  3. ↑ Hadlock, 1975 .
  4. ↑ Jansen, Karpinski, Lingas, Seidel, 2005 .
  5. ↑ Papadimitriou & Yannakakis, 1991 .
  6. ↑ Mitzenmacher, Upfal, 2005 , sid. Sekt. 6.2.
  7. ↑ Motwani, Raghavan, 1995 , sid. Sekt. 5.1.
  8. ↑ Mitzenmacher, Upfal, 2005 , sid. Sekt. 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 .

Litteratur

Det maximala skärningsproblemet (optimerad version) är ND14-problemet i Appendix B (sid. 399). Det maximala skärningsproblemet (lösbarhetsproblemet) är ND16-problemet i Appendix A2.2. Maximal tvådelad subgraf (upplösningsproblem) är GT25-problemet i Appendix A1.2.

Ytterligare läsning

Länkar