FKT algoritm

FKT -algoritmen , uppkallad efter Fisher , Kasteleyn och Temperley , räknar antalet perfekta matchningar i en plan graf i polynomtid. Samma uppgift är #P-komplett för allmänna grafer. För matchningar som inte krävs för att vara perfekta förblir räkningen #P-komplett även för plana grafer. Nyckelidén med FKT-algoritmen är att omvandla problemet till en Pfaffian - beräkning av en skevsymmetrisk matris härledd från en plan inbäddning av grafen. Pfaffian för denna matris beräknas sedan effektivt med standarddeterminantalgoritmer .

Historia

Problemet med att räkna plana perfekta matchningar har sina rötter i statistisk mekanik och kemi , där den ursprungliga frågan var: Om diatomiska molekyler adsorberas på en yta och bildar ett enda lager, hur många sätt kan de ordnas? Partitionsfunktionen i jämvikt och kan användas för att svara på föregående fråga. Det är dock inte praktiskt att försöka beräkna partitionsfunktionen från dess definition. Att exakt lösa ett fysiskt system är alltså att hitta en alternativ form av partitionsfunktionen för det specifika fysiska systemet som är tillräckligt enkel för att exakt beräkna. I början av 1960-talet var definitionen av exakt lösbar inte rigorös. Datavetenskap gav en rigorös definition med införandet av polynomtid , som dateras till 1965. På samma sätt borde notationen av inte exakt lösbar , för ett räkneproblem som detta, motsvara #P-hårdhet , som definierades 1979.

En annan typ av fysiskt system att överväga är sammansatt av dimerer , som är en polymer med två atomer. Dimermodellen räknar antalet dimerbeläggningar i en graf. Ett annat fysiskt system att överväga är bindningen av H ₂ O -molekyler i form av is. Detta kan modelleras som en riktad, 3- regelbunden graf där orienteringen av kanterna vid varje vertex inte alla kan vara densamma. Hur många kantorienteringar har denna modell?

Motiverade av fysiska system som involverade dimerer, 1961, fann Kasteleyn och Temperley och Fisher oberoende antalet dominoplattor för m -by- n rektangeln. Detta motsvarar att räkna antalet perfekta matchningar för m -by- n gittergrafen . År 1967 hade Kasteleyn generaliserat detta resultat till alla plana grafer.

Algoritm

Förklaring

Huvudinsikten är att varje term som inte är noll i Pfaffian för närliggande matris i en graf G motsvarar en perfekt matchning. Således, om man kan hitta en orientering av G för att anpassa alla tecken för termerna i Pfaffian (oavsett + eller - ), så är det absoluta värdet av Pfaffian bara antalet perfekta matchningar i G . FKT-algoritmen gör en sådan uppgift för en plan graf G . Orienteringen den finner kallas en Pfaffian orientering .

Låt G = ( V , E ) vara en oriktad graf med närliggande matris A. Definiera PM ( n ) som uppsättningen av partitioner av n element i par, då är antalet perfektionsmatchningar i G

$\operatorname {PerfMatch} (G)=\sum _{M\in PM(|V|)}\prod _{(i,j)\in M}A_{ij}.$

Nära besläktad med detta är Pfaffian för en n gånger n matris A

$\operatorname {pf} (A)=\summa _{M\in PM(n)}\operatörsnamn {sgn} (M)\prod _{(i,j)\in M}A_{ij},$

där sgn( M ) är tecknet för permutationen M . En Pfaffisk orientering av G är en riktad graf H med närliggande matris B så att pf( B ) = PerfMatch( G ). 1967 bevisade Kasteleyn att plana grafer har en effektivt beräkningsbar Pfaffian-orientering. Närmare bestämt, för en plan graf G , låt H vara en riktad version av G där ett udda antal kanter är orienterade medurs för varje yta i en plan inbäddning av G. Då är H en Pfaffisk orientering av G .

Slutligen, för varje skevsymmetrisk matris A ,

$\operatorname {pf} (A)^{2}=\det(A),$

där det( A ) är determinanten för A . Detta resultat beror på Cayley . Eftersom determinanter är effektivt beräkningsbara, så är PerfMatch( G ).

Beskrivning på hög nivå

Ett exempel som visar hur FKT-algoritmen hittar en Pfaffian-orientering.

1. Beräkna en plan inbäddning av G .
2. Beräkna ett _{överspänningsträd} Ti i ingångsgrafen G .
3. Ge en godtycklig orientering till varje kant i G som också är i T ₁ .
4. Använd den plana inbäddningen för att skapa en (oriktad) graf T ₂ med samma vertexuppsättning som den dubbla grafen för G .
5. Skapa en kant i T ₂ mellan två hörn om deras motsvarande ytor i G delar en kant i G som inte är i T ₁ . (Observera att T ₂ är ett träd.)
6. För varje blad v i T ₂ (det är inte också roten):
   1. Låt e vara den ensamma kanten av G i ansiktet som motsvarar v som ännu inte har en orientering.
   2. Ge e en orientering så att antalet kanter som är orienterade medurs är udda.
   3. Ta bort v från T ₂ .
7. Returnera det absoluta värdet av Pfaffian för närliggande matris av G , som är kvadratroten av determinanten.

Generaliseringar

Summan av viktade perfekta matchningar kan också beräknas genom att använda Tutte-matrisen för närliggande matris i det sista steget.

Kuratowskis teorem säger det

en finit graf är plan om och endast om den inte innehåller någon subgraf som är homeomorf till K ₅ ( komplett graf på fem hörn) eller K _3,3 ( komplett tvådelad graf på två partitioner av storlek tre).

Vijay Vazirani generaliserade FKT-algoritmen till grafer som inte innehåller en subgraf som är homeomorf till K _3,3 . Eftersom att räkna antalet perfekta matchningar i en allmän graf är #P-komplett krävs en viss begränsning av inmatningsgrafen om inte FP , funktionsversionen av P , är lika med #P . Att räkna matchningar, som kallas Hosoya-index , är också #P-komplett även för plana grafer.

Ansökningar

FKT-algoritmen har sett omfattande användning i holografiska algoritmer på plana grafer via matchgates. Tänk till exempel på den plana versionen av ismodellen som nämns ovan, som har det tekniska namnet # PL -3-NAE- SAT (där NAE står för "inte alla lika"). Valiant hittade en polynomtidsalgoritm för detta problem som använder matchgates.

externa länkar

• Mer historia, information och exempel finns i kapitel 2 och avsnitt 5.3.2 i Dmitry Kamenetskys doktorsavhandling