FKT algoritme

FKT (opkaldt efter Fisher , Castellain og Temperley ) er en algoritme, der tæller antallet af perfekte matchninger i en plan graf i polynomisk tid. Det samme problem er #P-complete for generelle grafer. At beregne antallet af matchninger selv for plane grafer er også et #P-komplet problem. Nøgleideen er at reducere problemet til at beregne Pfaffian for en skæv-symmetrisk matrix opnået fra en plan grafindlejring. Pfaffian af denne matrix beregnes derefter effektivt ved hjælp af standard determinantberegningsalgoritmer .

Historie

Problemet med at tælle plane perfekte matchninger har sine rødder i statistisk mekanik og kemi , hvor det oprindelige spørgsmål var: Hvis diatomiske molekyler absorberes på en overflade og danner et enkelt lag, på hvor mange måder kan de så arrangeres [1] ? Partitionsfunktionen er en vigtig størrelse, der koder for de statistiske egenskaber for et system i ligevægt, og den kunne bruges til at besvare det foregående spørgsmål. Det er dog ikke særlig praktisk at prøve at beregne partitionsfunktionen ud fra definitionen. Så er den nøjagtige løsning af et fysisk system at finde en alternativ form for partitionsfunktionen for et bestemt fysisk system, som ganske enkelt kan beregnes nøjagtigt [2] . I begyndelsen af ​​1960'erne var definitionen af ​​et nøjagtigt løseligt problem ikke streng [3] og datalogi gav en præcis definition med introduktionen af ​​begrebet polynomisk tid , som går tilbage til 1965. På samme måde burde forestillingen om et ikke helt løseligt problem svare til #P-hardness , som blev defineret i 1979.

En anden type fysisk system at overveje er kombinationer af dimerer , forbindelser af to atomer. Dimer-modellen overvejer antallet af grafdækning af dimerer [4] . Et andet system, der overvejes, er bindingen af ​​H 2 O- molekyler i form af is, som er modelleret som en rettet 3-regulær graf, hvor orienteringen af ​​kanterne ved hvert toppunkt ikke kan være den samme. Hvor mange kantretninger har denne model?

Interesseret i fysiske systemer af dimerer fandt Castellain [5] og også Temperley sammen med Fischer [6] uafhængigt i 1961 antallet af fliser af dominobrikker for et rektangel . Dette svarer til at tælle antallet af perfekte matchninger for gitteret . I 1967 generaliserede Castellain dette resultat til alle plane grafer [7] [8] .

Algoritme

Tilnærmelse

Hovedideen er, at enhver ikke-nul-led af Pfaffian af tilstødende matrix af grafen G svarer til en perfekt matchning. Så, hvis det er muligt at finde en orientering af grafen G , således at alle tegnene i vilkårene for Pfaffian er de samme (det er lige meget om de er + eller - ), så er den absolutte værdi af Pfaffian lig til antallet af perfekte matchninger af grafen G . FKT-algoritmen udfører denne opgave for en plan graf G . Den orientering, som algoritmen finder, kaldes den Pfaffianske orientering .

Lad G =( V , E ) være en urettet matrix med tilstødende matrix A . Lad os definere PM ( n ) som et sæt af partitioner af n elementer i par, så er antallet af perfekte matchninger i graf G lig med

Nært beslægtet med dette er Pfaffian for matrix A

hvor sgn( M ) er permutationstegnet for M . En Pfaffisk orientering af en graf G  er en rettet graf H med en (1, −1, 0) tilstødende matrix B , således at pf( B )=PerfMatch( G ) [9] . I 1967 beviste Castellain, at plane grafer har en effektivt beregnelig Pfaffian-orientering. For en plan graf G , lad nemlig H være en rettet version af G , hvor et ulige antal kanter er orienteret mod uret for en hvilken som helst flade af en plan indlejring af G. Så er H en Pfaffisk orientering af G .

Endelig, for enhver skæv-symmetrisk matrix A ,

hvor det( A ) er determinanten for matrix A . Dette resultat skyldes Cayley [10] . Da determinanterne beregnes effektivt, gælder det samme for PerfMatch( G ).

Beskrivelse af algoritmen

  1. Beregn den plane indlejring af grafen G .
  2. Beregn spændingstræet T 1 af inputtræet G .
  3. Vi giver en vilkårlig orientering til hver kant af grafen G , som også hører til træet T 1 .
  4. Vi bruger plan indlejring til at skabe en (urettet) graf T 2 , der har det samme sæt af hjørner som den dobbelte graf for G .
  5. Lav en kant i T 2 mellem to tilsvarende flader af G , der har en fælles kant i G , som ikke hører til T 1 . (Bemærk, at T 2  er et træ.)
  6. For hvert blad v i T 2 (som ikke også er en rod):
    1. Lad e  være en enkelt kant af grafen G i ansigtet svarende til v , som endnu ikke har fået en orientering.
    2. Vi giver e en orientering sådan, at antallet af kanter orienteret med uret er ulige.
    3. Fjern v fra T 2 .
  7. Vi returnerer den absolutte værdi af Pfaffian af (1, −1, 0) tilstødende matrix af grafen G , som er lig med kvadratroden af ​​determinanten.

Generaliseringer

Summen af ​​vægtede perfekte matchninger kan også beregnes ved hjælp af Tatta-matricer for tilstødende matricer i det sidste trin.

Pontryagin-Kuratovsky-sætningen siger det

en finit graf er plan, hvis og kun hvis den ikke indeholder en subgraf , der er homøomorf til K 5 ( en komplet graf med fem hjørner) eller K 3,3 ( en komplet todelt graf med to dele af størrelse tre).

Vijay Vazirani generaliserede FKT-algoritmen til grafer, der ikke indeholder en subgraf, der er homøomorf til K 3,3 [11] . Da optælling af antallet af perfekte matchninger i en generel graf er et #P-komplet problem, er nogle begrænsninger på inputgrafen påkrævet, medmindre kompleksiteten af ​​FP , den funktionelle version af P , er #P . Matchtælling, også kendt som Hosoya-indekset , er også #P-komplet selv for plane grafer [12] .

Ansøgninger

FKT-algoritmen er meget brugt i holografiske algoritmer på plane grafer via matchgates (Valiants to-qubit-elementer) [3] . Overvej for eksempel den flade version af ismodellen nævnt ovenfor, som har det tekniske navn #PL -3-NAESAT ( her står NAE for "Not All Equal"). Valiant fandt en polynomisk tidsalgoritme til dette problem, der bruger matchgates [13] .

Noter

  1. ↑ Hayes, 2008 .
  2. ↑ Baxter, 2008 , s. elleve.
  3. ↑ 12 Cai , Lu, Xia, 2010 .
  4. ↑ Kenyon, Okounkov, 2005 , s. 342-343.
  5. ↑ Kasteleyn, 1961 , s. 1209-1225
  6. ↑ Temperley og Fisher, 1961 , s. 1061-1063.
  7. ↑ Kasteleyn, 1963 , s. 287-293.
  8. ↑ Kasteleyn, 1967 , s. 43-110.
  9. ↑ Thomas, 2006 , s. 963-984.
  10. ↑ Cayley, 1847 , s. 93-96.
  11. ↑ Vazirani, 1989 , s. 152-164.
  12. ↑ Jerrum, 1987 , s. 121-134.
  13. ↑ Valiant, 2004 , s. 306-315.

Litteratur

Links