Description
Az ELTE Alkalmazott Diszkrét Matematika szeminárium előadása.
Jól ismert Dalmau és Jonsson eredménye, miszerint egy tetszőleges G gráf F
előre adott gráffal izomorf részgráfjai számának (sub(F,G)) meghatározása
pontosan akkor nem #P-nehéz leszámlálási probléma, ha F korlátos favastagságú
(kivéve, ha FPT = #W[1]). A cikk szerzőinek célja, hogy egzakt, paraméteres
algoritmust adjanak sub(F,G) kiszámítására (mely tehát G csúcsszámában
várhatóan nem polinomiális). Ehhez mutatnak egy új, szita-formulaszerű
képletet, mely algoritmikus szempontból is hatékony: segítségével O(2^n t(n))
időben meghatározható sub(F,G), ahol t(n) jelöli azt az időt, amennyiben az n
csúcsú G bármely W részgráfjára meg tudjuk számolni az F-ről a W-re menő
homomorfizmusokat.
A formulát és annak algoritmikus következményét használva az előadás során
könnyen bebizonyítunk néhány klasszikus (Hamilton-körök száma, kromatikus
polinom kiszámítása, teljes párosítások száma páros gráfban), illetve több új
eredményt is (n jelöli G csúcsszámát):
-- tetszőleges l méretű független halmaz esetén 2^(n-l) * n^3 időben
meghatározható a G gráf teljes párosításainak a száma (ez a Ryser-formula
általánosítása);
-- adott fokszámsorozatú feszítőfák leszámlálása G-ben megy 2^O(n) időben
(ennek speciális esete a Hamilton-utak megszámolása);
-- tetszőleges rögzített M gráf esetén a G egy maximális méretű M-minormentes
élhalmaza megtalálható 2^O(n) időben;
-- G-nek egy k csúcsú, t favastagságú F gráffal izomorf részgráfja (ha létezik
ilyen) megtalálható O(4,32^k * k * t * n^(t+1)) várható időben.
For Teams access please contact Zoltán Király (kiraly[at]cs.elte.hu).