FKT algoritam

FKT algoritam, nazvan po [Fisher], [Kasteleyn] i [Temperley], racuna broj [savrsenih uparivanja] [planarnog grafa] u polinomijalnom vremenu. Ovaj isti zadatak je [#P-kompletan] i za ostale grafove. Racunanjem broja [uredjenjih parova], cak i za planarne grafove takodje je #P-kompletno. Kljucna ideja je da konvertuje problem u [Pfaffian] racunanje [koc-simetricne matrice] izvedene od planarnog ugradjivanja grafa. Pfafian matrica je onda kompjuterizovana efikasno standardnim [algoritmima determinante]

Istorija

Problem brojanja planarnih savrsenih uparivanja ima svoje korene u [statistickoj mehanici] i [hemiji], gde je originalno pitanje: Ako se [dijatomicki molekuli] absorbuju na povrsini, formirajuci jedan sloj, na koliko nacina se oni mogu organizovati? [Funkcija particionisanja] je vazan kvantitet koji kodira statisticke osobine sistema u ravnotezi i moze se koristiti kao odgovor na prethodno pitanje. Medjutim pokusavajuci da izracuna funkciju particije njenom definicijom nije prakticno. Tako da tacno resiti fizicki sistem jeste pronaci alternativnu formu funkcije particionisanja za taj pojedinacni fizicki sistem koji je prilicno jednostavan da se tacno izracuna. Ranih 1960-tih, definicija tacno resiv nije bila rigorozna. In the early 1960s, the definition of exactly solvable was not rigorous. Informatika je obezbedila rigoroznu definiciju sa uvodjenjem [polinomijalnog vremena], koja datira od 1965. Slicno tome, notacija ne bas tacno resivog treba da odgovara [#P-teskoci], koja je definisana 1979.

Druga vrsta fizickog sistema za razmatranje je sastavljena od dimeradimers sto je polimer sa dva atoma. Dimer model racuna broj dimer obloga grafa. Drugi fizicki system za razmatranje je vezivanje [H2O] molekula u obliku leda. Ovo moze biti modelovano kao rezija, 3-[regularna grafa] kod kojih je orijentacija ivica na svakom cvoru ne mogu biti ista. Koliko ivica orijentacije ima ovaj model?

Motivisani fizickim sistemima koji ukljucuju [dimere], 1961, Kasteleyn i Temperley-Fisher samostalno nalaze broj [domino] poplocavanja za m-od-n pravougaonika. Ovo je ekvivalentno broju savrsenih uparivanja za m-od-n [resetka grafa]. 1967. Kasteleyn je generalizovao ovaj rezultat za sve planarne grafove.

Algoritam

Objasnjenje

Glavni uvid je da svaki ne-nula rok u [Pfaffian]u od [matrice susedstva] grafa G odgovara savrsenom uparivanju. Dakle, ako neko moze da pronadje polozaj G da uskladi sve znake termina u [Pfaffian](bez obzira na + ili -), onda apsolutna vrednost [Pfaffian]a je samo broj savrsenih uparivanja u G. FKT algoritam radi takav zadatak za planaran graf G.

Neka G=(V,E) bude neusmeren graf sa [matricom susedstva] A. Definisi PM(n) da bude skup particija od n elemenata u parove, zatim broj savrsenih uparivanja u G je

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

U tesnoj vezi sa ovim je [Pfaffian] za n x n matricu A

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

Gde je sgn(M) [znak permutacije] od M. Pfaffian orijentacija od G je usmeren graf H sa [(1,-1,0) matricom susedstva] B takvom da je pf(b)= PerfMatch(G). 1967. Kasteleyn je dokazao da su planarni grafovi efikasno podlozni racunanju pfafian orijentacije. Konkretno, za planaran graf G, neka H bude usmerena verzija G gde je neparan broj ivica orijentisano u smeru kazaljke na satu za svako lice u planarnom ugradjivanju G. Onda je H pfafian orijentacija od G.

Na kraju, za bilo koju [koc-simetricnu matricu] A,

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

gde det(A) je [determinanta] od A. Ovaj rezultat je zbog [Cayley]. Posto su determinante efektivno podlozne racunanju, onda je i PerfMatch(G).

Opis visokog nivoa

An example showing how the FKT algorithm finds a Pfaffian orientation.

1. Izracuna planarnu [ugradnju] od G
2. Izracuna [spanning stablo] T₁ ulaznog grafa G
3. Daje proizvoljnu orijentaciju svakoj ivici u G koja je takodje u T₁.
4. Koristi planarna ugradjivanja da stvori (neusmeren)graf T₂ sa istim skupom cvorova kao [dvojni graf] od G
5. Napravi ivicu u T₂ izmedju dva cvora ako su odgovarajuca
6. Za svaki list v u T₁(to nije i koren)
   1. Neka je e usamljena ivica od G u lice odgovara v koji jos nema orijentaciju
   2. Daj e orijentaciju takvu da je broj ivica orijentisanih u smeru kazaljke na satu neparan.
   3. Ukloni v od T₂.
7. Vrati apsolutnu vrednost Pfaffian od (1,-1,0) matrice susedstva G, koja je apsolutna vrednost kvadratnog korena determinante.

Generalizacija

Zbir opterecenih savrsenih uparivanja se moze izracunati pomocu [Tutte matrice] za matricu susedstva u poslednjem koraku.

[Kuratovski teorema] navodi da [konacni graf] je planaran [ako i samo ako] ne sadrzi [podgraf homeomorfan] K₅ ( [potpun graf] od pet cvorova) ili K_3,3 ( [potpun bipartidan graf] na dve particije velicine tri). [Vijay Vazirani] generalizovao je FKT algoritam za grafove koji ne sadrze homeomorfan podgraf za K_3,3. Od prebrojavanja savrsenih uparivanja u opstem grafu je #P-kompletan (#P-complete), neka ogranicenja ulaznog grafa su potrebna, osim ako FP , funkcijska verzija P , jednaka je #P . Prebrojavanje parova, koja su poznata као Hosoja indeks (Hosoya index), su takodje #P-kompletna cak i za planarne grafove.

Aplikacije

FKT algoritam je video siroku primenu u holografskim algoritmima(holographic algorithm) za planarne grafove preko uparivanja(matchgates). Na primer, razmotrite planaranu verziju ledenog modela gore navedenog, koja ima tehnicko ime #PL-3-NAE-SAT(gde NAE znaci "" nisu svi isti""). Valiant je nasao polinomijalno vremenski algoritam za ovaj problem, koji koristi uparivanja.

External links

• Presentation by Ashley Montanaro about the FKT algorithm
• More history, information, and examples can be found in chapter 2 and section 5.3.2 of Dmitry Kamenetsky's PhD thesis