Maksimal grafsnit

Det maksimale snit i en graf er et snit , hvis størrelse ikke er mindre end størrelsen af ​​ethvert andet snit. Problemet med at bestemme det maksimale snit for en graf er kendt som det maksimale snitproblem .

Problemstillingen kan formuleres som følger. En delmængde af toppunkter S bør findes således, at antallet af kanter mellem S og dets komplement er så stort som muligt.

Der er en udvidet version, det vægtede maksimale snitproblem . I denne version er hver kant tildelt et reelt tal, dens vægt er , og målet er ikke at maksimere antallet af kanter, men den samlede kantvægt mellem S og dens komplement. Det vægtede maksimale snitproblem er ofte, men ikke altid, begrænset til ikke-negative vægte, fordi negative vægte kan ændre problemets karakter.

Beregningsmæssig kompleksitet

Følgende løselighedsproblem , relateret til det maksimale snit, er blevet undersøgt bredt i teoretisk datalogi :

Givet en graf G og et heltal k , afgør, om der er et snit i G , der er mindst k .

Dette problem er kendt for at være NP-komplet . NP-fuldstændigheden af ​​et problem kan for eksempel vises ved at reducere fra det maksimale 2-tilfredshedsproblem ( maksimalt tilfredshedsproblem med restriktioner) [1] . En vægtet version af løselighedsproblemet er inkluderet i de 21 NP-komplette Karp- opgaver [2] . Karp viste NP-fuldstændighed ved reduktion fra partitionsproblemet .

Den kanoniske optimeringsvariant af ovenstående løselighedsproblem er kendt som " maximum cut-problemet " og er defineret som følger:

Lad grafen G være givet , det er nødvendigt at finde det maksimale snit.

Polynomiske tidsalgoritmer

Da det maksimale cut-problem er NP-hårdt, er der ingen polynomielle tidsalgoritmer for det maksimale cut-problem for generelle grafer.

For plane grafer er det maksimale snitproblem dog dobbelt med det kinesiske postmandsproblem (problemet med at finde den korteste vej, der går rundt om alle kanter mindst én gang), i den forstand at kanter, der ikke hører til maksimum snit af G er dobbelte til kanter, som gennemløbes mange gange i den optimale gennemløb af den dobbelte graf for grafen G . Den optimale gang danner en selvskærende kurve, der opdeler planet i to delmængder, en delmængde af punkter, hvor rækkefølgen i forhold til kurven er lige, og en delmængde af punkter, hvor rækkefølgen er ulige. Disse to delmængder danner et snit, der inkluderer alle kanter, der er dobbelte med kanter, der vises et ulige antal gange i gennemgangen. Det kinesiske postbudsproblem kan løses i polynomiel tid, og denne dualitet gør det muligt at løse det maksimale snitproblem for plane grafer i polynomisk tid [3] . Det er dog kendt, at det maksimale halveringsproblem er NP-hårdt [4] .

Approksimationsalgoritmer

Det maksimale cut-problem er APX-hårdt (Papadimitrou og Yannakakis viste sig at være MaxSNP-komplet for dette problem [5] ), hvilket betyder, at der ikke er et polynomial time approximation scheme (PTAS) vilkårligt tæt på den optimale løsning, medmindre P = NP. Enhver tilnærmelsesalgoritme for polynomisk tid giver således en tilnærmelseskoefficient , strengt taget mindre end én.

Der er en simpel probabilistisk 0,5 -tilnærmelsesalgoritme - for ethvert toppunkt kaster vi en mønt for at afgøre, hvilken del af snittet der skal tilskrives dette toppunkt [6] [7] . Halvdelen af ​​kanterne forventes at være skærende. Denne algoritme kan derandomiseres ved hjælp af metoden med betingede sandsynligheder . Der er således en simpel deterministisk polynomisk tidsalgoritme med 0,5-approksimation [8] [9] . En sådan algoritme starter med en vilkårlig opdeling af hjørnerne af en given graf og flytter et toppunkt i et trin fra en del af snittet til en anden, hvilket forbedrer løsningen ved hvert trin, så længe forbedring er mulig. Antallet af iterationer af algoritmen overstiger ikke , da algoritmen forbedrer skæringen med mindst én kant. Når algoritmen stopper, hører mindst halvdelen af ​​de kanter, der falder ind på et hvilket som helst toppunkt, til snittet, ellers ville en flytning af spidsen forbedre snittet (øge størrelsen af ​​snittet). Snittet omfatter således i det mindste kanter.

Polynomial-tidstilnærmelsesalgoritmen for det maksimale cut-problem med den bedst kendte tilnærmelseskoefficient er Gemans og Williamson-metoden, der anvender semi-bestemt programmering og probabilistisk afrunding . Metoden giver en tilnærmelseskoefficient , hvor [10] [11] . Hvis den unikke spilhypotese er sand, er dette den bedst mulige tilnærmelsesfaktor for det maksimale cut [12] . Bortset fra sådanne ubeviste antagelser, er det blevet bevist, at det er NP-svært at tilnærme værdien af ​​den maksimale cut med en faktor bedre end [13] [14] .

Se også

Noter

  1. ↑ Garey, Johnson, 1979 .
  2. ↑ Karp, 1972 .
  3. ↑ Hadlock, 1975 .
  4. ↑ Jansen, Karpinski, Lingas, Seidel, 2005 .
  5. ↑ Papadimitriou & Yannakakis, 1991 .
  6. ↑ Mitzenmacher, Upfal, 2005 , s. Sekt. 6.2.
  7. ↑ Motwani, Raghavan, 1995 , s. Sekt. 5.1.
  8. ↑ Mitzenmacher, Upfal, 2005 , s. 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 maksimale skæreproblem (optimeret version) er ND14-problemet i appendiks B (s. 399). Det maksimale snitproblem (opløselighedsproblem) er ND16-problemet i appendiks A2.2. Maksimal todelt undergraf (opløselighedsproblem) er GT25-problemet i appendiks A1.2.

Yderligere læsning

Links