Algoritmus FKT

FKT (pojmenovaný po Fisherovi , Castellainovi a Temperley ) je algoritmus, který počítá počet dokonalých shod v rovinném grafu v polynomiálním čase. Stejný problém je #P-complete pro obecné grafy. Výpočet počtu shod i pro rovinné grafy je také #P-úplný problém. Klíčovou myšlenkou je zredukovat problém na výpočet Pfaffianu šikmo symetrické matice získané z vložení rovinného grafu. Pfaffian této matice je pak efektivně vypočítán pomocí standardních algoritmů pro výpočet determinantů .

Historie

Problém počítání planárních dokonalých párování má své kořeny ve statistické mechanice a chemii , kde původní otázka zněla: Pokud jsou dvouatomové molekuly absorbovány na povrchu a tvoří jednu vrstvu, kolika způsoby mohou být uspořádány [1] ? Rozdělovací funkce je důležitou veličinou, která kóduje statistické vlastnosti systému v rovnováze, a mohla by být použita k zodpovězení předchozí otázky. Zkoušet vypočítat partiční funkci z definice však není příliš praktické. Přesným řešením fyzického systému je pak nalezení alternativní formy rozdělovací funkce pro konkrétní fyzický systém, která je zcela jednoduše přesně vyčíslitelná [2] . Na počátku šedesátých let nebyla definice přesně řešitelného problému rigorózní [3] a informatika dala přesnou definici zavedením konceptu polynomiálního času , který sahá až do roku 1965. Podobně by pojem ne zcela řešitelný problém měl odpovídat #P-tvrdosti , která byla definována v roce 1979.

Dalším typem fyzikálního systému , který je třeba zvážit, jsou kombinace dimerů , sloučenin dvou atomů. Dimerový model zohledňuje počet pokrytí grafu dimery [4] . Dalším uvažovaným systémem je vazba molekul H 2 O ve formě ledu, která je modelována jako směrovaný 3-pravidelný graf, ve kterém nemůže být orientace hran v každém vrcholu stejná. Kolik orientací hran má tento model?

Zajímající se o fyzikální systémy dimerů, v roce 1961 Castellain [5] a také Temperley spolu s Fischerem [6] nezávisle na sobě našli počet obkladů kostek domina pro obdélník . To je ekvivalentní počítání počtu dokonalých shod pro mřížku . V roce 1967 Castellain zobecnil tento výsledek na všechny rovinné grafy [7] [8] .

Algoritmus

Přístup

Hlavní myšlenkou je, že jakýkoli nenulový člen Pfaffianu matice sousednosti grafu G odpovídá dokonalé shodě. Pak, pokud je možné najít orientaci grafu G tak, aby všechna znaménka členů Pfaffova výrazu byla stejná (nezáleží na tom, zda jsou + nebo - ), pak je absolutní hodnota Pfaffova výrazu rovna k počtu dokonalých shod grafu G . Algoritmus FKT provádí tento úkol pro rovinný graf G . Orientace, kterou algoritmus najde, se nazývá Pfaffova orientace .

Nechť G =( V , E ) je neorientovaná matice s maticí sousedství A . Definujme PM ( n ) jako množinu rozdělení n prvků do dvojic, pak se počet dokonalých shod v grafu G rovná

S tím úzce souvisí Pfaffian pro matici A

kde sgn( M ) je permutační znaménko M. Pfaffova orientace grafu G  je orientovaný graf H s (1, −1, 0) maticí sousednosti B tak, že pf( B )=PerfMatch( G ) [9] . V roce 1967 Castellain dokázal, že rovinné grafy mají efektivně vypočítatelnou Pfaffovu orientaci. Konkrétně, pro rovinný graf G , nechť H je orientovaná verze G , ve které je lichý počet hran orientován proti směru hodinových ručiček pro jakoukoli plochu rovinného vnoření G . Pak H je Pfaffova orientace G .

Nakonec pro jakoukoli šikmo symetrickou matici A

kde det( A ) je determinant matice A . Tento výsledek je způsoben Cayley [10] . Protože se determinanty počítají efektivně, totéž platí pro PerfMatch( G ).

Popis algoritmu

  1. Vypočítejte rovinné vnoření grafu G .
  2. Vypočtěte kostru T 1 vstupního stromu G .
  3. Každé hraně grafu G , která také patří do stromu T 1 , dáváme libovolnou orientaci .
  4. Pomocí planárního vnoření vytvoříme (neorientovaný) graf T 2 , který má stejnou množinu vrcholů jako duální graf G .
  5. Vytvořte hranu v T 2 mezi dvěma odpovídajícími plochami G , které mají společnou hranu v G , která nepatří do T 1 . (Všimněte si, že T 2  je strom.)
  6. Pro každý list v v T 2 (což není také kořen):
    1. Nechť e  je jedna hrana grafu G v ploše odpovídající v , která ještě nedostala orientaci.
    2. Dáme e orientaci takovou, že počet hran orientovaných ve směru hodinových ručiček je lichý.
    3. Odstraňte v z T 2 .
  7. Vrátíme absolutní hodnotu Pfaffianu matice (1, −1, 0) sousednosti grafu G , která je rovna druhé odmocnině determinantu.

Zobecnění

Součet vážených dokonalých shod lze také vypočítat pomocí matic Tatta pro sousední matice v posledním kroku.

Tvrdí to Pontrjagin-Kuratovského teorém

konečný graf je rovinný právě tehdy, když neobsahuje podgraf , který je homeomorfní K 5 ( úplný graf s pěti vrcholy) nebo K 3,3 ( úplný bipartitní graf se dvěma částmi o velikosti tři).

Vijay Vazirani zobecnil algoritmus FKT na grafy, které neobsahují podgraf homeomorfní ke K 3,3 [11] . Protože počítání počtu dokonalých shod v obecném grafu je #P-úplný problém, jsou vyžadována některá omezení na vstupním grafu, pokud složitost FP , funkční verze P , není #P . Počítání zápasů, známé také jako Hosoyův index , je také #P-úplné i pro rovinné grafy [12] .

Aplikace

Algoritmus FKT se hojně používá v holografických algoritmech na rovinných grafech přes matchgates (Valiantovy dvou-qubitové prvky) [3] . Vezměme si například plochou verzi výše uvedeného modelu ledu, která má technický název #PL -3-NAESAT ( zde NAE znamená „Not All Equal“). Valiant našel polynomiální časový algoritmus pro tento problém, který používá matchgates [13] .

Poznámky

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

Literatura

Odkazy