}w !"#$%&'()+,-./012345
M ASARYKOVA UNIVERZITA FAKULTA INFORMATIKY
Srovnání Vertex cover, Twin-cover a Neighborhood diversity na grafech ˇ B AKALÁ RSKÁ PRÁCE
Vladimír Lambert
Brno, jaro 2012
Prohlášení Prohlašuji, že tato bakaláˇrská práce je mým puvodním ˚ autorským dílem, které jsem vypracoval samostatnˇe. Všechny zdroje, prameny a literaturu, které jsem pˇri vypracování používal nebo z nich cˇ erpal, v práci rˇ ádnˇe cituji s uvedením úplného odkazu na pˇríslušný zdroj.
Vedoucí práce: RNDr. Robert Ganian ii
Podˇekování Rád bych podˇekoval vedoucímu své práce RNDr. Robertu Ganianovi za cenné rady a pˇripomínky k této práci.
iii
Shrnutí Tato práce srovnává hodnoty vrcholového pokrytí, twin-cover a neighborhood diversity na grafech. Po pˇredstavení pojmu˚ z teorie grafu˚ vztahujících se k zadanému tématu jsou popsány algoritmy ke spoˇctení tˇechto parametru. ˚ V závˇeru je porovnána velikost tˇechto parametru˚ pro ruzné ˚ grafy.
iv
Klíˇcová slova teorie grafu, ˚ vrcholové pokrytí, twin-cover, neighborhood diversity, parametrizovaná složitost
v
Obsah Úvod . . . . . . . . . . . . . . . . . . . . . . . . 1 Vybrané kapitoly z teorie grafu˚ . . . . . . . 1.1 Graf . . . . . . . . . . . . . . . . . . . . 1.2 Parametrizovaná složitost . . . . . . . 1.3 Vrcholové pokrytí . . . . . . . . . . . . 1.4 Neighborhood diversity . . . . . . . . 1.5 Twin-cover . . . . . . . . . . . . . . . . 2 Použité rˇešení . . . . . . . . . . . . . . . . . 2.1 Reprezentace grafu . . . . . . . . . . . 2.2 Neighborhood diversity . . . . . . . . 2.3 Odstranˇení twin-edges . . . . . . . . . 2.4 Vrcholové pokrytí . . . . . . . . . . . . 3 Konkrétní implementace . . . . . . . . . . 3.1 Zadání . . . . . . . . . . . . . . . . . . 3.2 Graf . . . . . . . . . . . . . . . . . . . . 3.3 Naˇcítání grafu . . . . . . . . . . . . . . 3.4 Redukce grafu . . . . . . . . . . . . . . 3.5 Tˇrídy s algoritmy . . . . . . . . . . . . 3.6 Ovládání programu . . . . . . . . . . . 4 Porovnání parametru˚ na zadaných grafech 4.1 Tabulka s porovnávanými parametry . 4.2 Srovnání parametru˚ . . . . . . . . . . . Závˇer . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
1 3 3 6 7 8 9 11 11 11 14 16 19 19 19 20 21 21 21 23 23 25 27
vi
Úvod Teorie grafu˚ je oblast matematiky, která používá struktury zvané grafy. Tyto slouží pˇreˇ devším k zachycení relací (hrany grafu) mezi objekty (vrcholy grafu). Rešení vˇetšiny zajímavých, v praktickém životˇe využitelných problému˚ na tˇechto grafech je NP-složité, tedy neˇrešitelné deterministickým algoritmem v polynomiálním cˇ ase v závislosti na velikosti vstupu. S touto pˇrekážkou se lze vypoˇrádat pomocí takzvaných parametrizovaných algoritmu, ˚ které v tˇechto pˇrípadech bˇeží v cˇ ase závislém na urˇcitém parametru grafu a saˇ motná velikost grafu pak zvyšuje potˇrebný cˇ as pouze polynomiálnˇe. Cím nižší tento parametr je, tím rychleji dospˇeje algoritmus k rˇ ešení a protože grafy s praktickým využitím mají cˇ asto urˇcitou vnitˇrní strukturu je velká pravdˇepodobnost, že existuje parametr, který je pro rˇ ešení problému na tomto grafu vhodný. Cílem práce bylo implementovat algoritmy, která pro dané grafy zjistí jejich minimální vrcholové pokrytí, poˇcet tˇríd ekvivalence neighborhood diversity a minimální twin-cover. Pokud by byl graf pˇríliš velký, bylo úkolem spoˇcítat tyto parametry na jeho indukovaném podgrafu. Dále pak mˇely být tyto tˇri hodnoty pro každý graf porovnány. Duvodem ˚ pro tento úkol je, že bylo zjištˇeno, že místo parametru minimálního vrcholového pokrytí je v urˇcitých pˇrípadech možno použít neighborhood diversity, pˇrípadnˇe twin-cover. Tyto dva parametry by mˇely být potom na urˇcitých grafech nižší než vrcholové pokrytí a provádˇení parametrizovaných algoritmu˚ s nimi by tak mˇelo být rychlejší. Cílem práce bylo ovˇerˇ it, zda tomu tak skuteˇcnˇe je a pˇrípadnˇe o kolik jsou tyto parametry menší. V první kapitole této práce jsou popsány pojmy z teorie grafu, ˚ které jsou nutné pro porozumˇení dalšímu textu. Jedná se o vysvˇetlení základní terminologie a jevu, ˚ jejichž pochopení je potˇrebné pˇri cˇ tení popisu jednotlivých algoritmu. ˚ Následuje krátký úvod do základních pojmu˚ teorie parametrizované složitosti, nebot’ tato je duvodem, ˚ proˇc mají v této práci zjišt’ované parametry grafu˚ takový význam. Poté se seznámíme s jednotlivými parametry. Vrcholové pokrytí je pomˇernˇe dobrˇe známé, ovšem další dva, zvláštˇe pak twin-cover, jsou relativnˇe nové a nejsou tedy tak dobˇre prostudované. Proto je jistˇe na místˇe tyto parametry blíže pˇredstavit. V kapitole druhé jsou ukázány zpusoby, ˚ jak se k hledaným parametrum ˚ dopracovat. Jsou vysvˇetleny konkrétní algoritmy použité v této práci, které jsou v nˇekterých pˇrípadech doplnˇeny o dukazy ˚ jejich správnosti. Ve tˇretí kapitole je popsána konkrétnˇejší implementace použitého rˇ ešení, je zde uveden seznam metod poskytovaných jednotlivými tˇrídami, postup použitý pˇri redukci pˇríliš velkého grafu na jeho indukovaný podgraf a požadavky na vstupní soubor, ze 1
kterého se naˇcítá graf, jehož parametry mají být zjištˇeny. Také je zde vysvˇetleno, jak používat program, který je výstupem této práce. Hlavním obsahem cˇ tvrté kapitoly je pak tabulka, které porovnává spoˇctené parametry na zadaných grafech. Následuje diskuze o hodnotách tˇechto parametru˚ na jednotlivých grafech pˇredevším s ohledem na pomˇer mezi poˇctem vrcholu˚ a hran grafu. V Závˇeru je pak možné se doˇcíst, jak dopadlo srovnání jednotlivých parametru˚ na grafech a kdy je tedy pro parametrizované algoritmy vhodné používat jiný vstupní parametr než velikost vrcholového pokrytí.
2
Kapitola 1
Vybrané kapitoly z teorie grafu˚ V této kapitole jsou vysvˇetleny základní termíny z teorie grafu, ˚ které jsou duležité ˚ pro porozumˇení dalšímu textu, a pojmy použité v popisu algoritmu. ˚
1.1 Graf Graf je uspoˇrádaná dvojice G = (V, E), kde V je množina vrcholu˚ grafu a E je množina jeho hran. Platí E ⊆ |V |2 , tedy množina E je tvoˇrena dvouprvkovými podmnožinami množiny V. Množinu vrcholu˚ grafu G oznaˇcujeme jako V(G) a množinu jeho hran jako E(G). O dvou vrcholech U, T grafu G mužeme ˚ prohlásit, že jsou sousední, pokud existuje hrana e ∈ E(G) taková, že T ∈ e ∧ U ∈ e, tedy pokud existuje hrana, která tyto vrcholy spojuje. Hrana e ∈ E(G) se oznaˇcuje za hranu incidentní k vrcholu U ∈ V (G), pokud hrana v tomto vrcholu konˇcí, tedy pokud U ∈ e. Takto popsaný graf nazýváme neorientovaný. U grafu˚ orientovaných platí, že E(G) je tvoˇrena uspoˇrádanými dvojicemi, pro jejichž prvky platí stejné podmínky jako pro dvouprvkové množiny popsané výše. Hrany orientovaných grafu˚ tedy vždy vedou smˇerem od jednoho vrcholu k druhému, u grafu˚ neorientovaných jsou oba koncové vrcholy hrany rovnocenné. Tato práce se dále zabývá pouze grafy neorientovanými. Podgraf Graf H je podgrafem grafu G (H ⊆ G) právˇe tehdy, když platí, že V (H) ⊆ V (G) a E(H) ⊆ E(G), pro všechny hrany grafu H musí platit, že oba jejich koncové vrcholy patˇrí do V(H). Graf H je indukovaným podgrafem grafu G, pokud pro všechny dvojice vrcholu˚ grafu H platí, že tyto vrcholy jsou spojeny hranou právˇe tehdy, když hrana mezi tˇemito dvˇema vrcholi patˇrí do E(G). Doplnkový ˇ graf Mužeme ˚ prohlásit, že G’ je doplnkovým ˇ grafem ke grafu G právˇe tehdy, když platí že 0 V (G) = V (G ) a pro všechny hrany uv ∈ E(G) platí uv ∈ / E(G0 ) a pro všechny uv ∈ / E(G) platí uv ∈ E(G0 ). Tedy doplnkový ˇ graf G’ vznikne tak, že z grafu G odstraníme všechny 3
1. V YBRANÉ KAPITOLY Z TEORIE GRAF U˚ hrany a dva vrcholy spojíme hranou právˇe tehdy, když mezi tˇemito vrcholy v puvodním ˚ grafu hrana nebyla. Úplný graf Úplný graf je takový graf, pro který platí, že každé dva vrcholy patˇrící do tohoto grafu jsou spojeny hranou. Úplný graf s n vrcholy bývá oznaˇcován jako Kn . Nezávislá množina Jako nezávislou množinu oznaˇcujeme množinu vrcholu˚ grafu takovou, pro kterou platí, že žádné dva z nich nejsou sousední. Tedy žádné z vrcholu˚ této množiny nejsou spojeny hranou. Maximální nezávislá množina je nezávislá množina s nejvˇetším poˇctem vrcholu˚ zkoumaného grafu G. Problém urˇcení této množiny je NP-složitý, jak bude zmínˇeno dále. Klika Pojmem klika oznaˇcujeme množinu vrcholu˚ grafu takovou, že pro každé dva vrcholy v této množinˇe platí, že jsou spojeny hranou. Stupenˇ vrcholu U každého vrcholu v grafu mužeme ˚ urˇcit jeho stupenˇ deg(v). Jedná se o cˇ íslo, které oznaˇcuje poˇcet hran incidentních k tomuto vrcholu. Kreslení grafu˚ Vzhledem k tomu, že zápis grafu pomocí množin není pro cˇ lovˇeka názorný, používá se obvykle k zobrazení grafu zpusob, ˚ kdy se za každý vrchol grafu nakreslí teˇcka. Spojení dvou tˇechto teˇcek znamená, že je mezi tˇemito dvˇema vrcholy hrana. To, jak se hrany navzájem kˇríží a jak jsou umístˇeny jednotlivé vrcholy, není duležité. ˚ Jediná informace nesetá tímto zobrazením je, které vrcholy jsou sousední. Tento zpusob ˚ je také používán u ilustraˇcních obrázku˚ v této práci.[1] Reprezentace grafu˚ v poˇcítaˇci1 Pro reprezentaci grafu˚ v pamˇeti poˇcítaˇce samozˇrejmˇe není použití obrázku vhodné, a tak lze využít nˇekolika jiných zpusob ˚ u, ˚ z nichž každý má urˇcité pˇrednosti. 1. Všechny pˇríklady v této sekci popisují graf z obrázku 1.1.
4
1. V YBRANÉ KAPITOLY Z TEORIE GRAF U˚
Obrázek 1.1: Pˇríklad reprezentace grafu pomocí obrázku. Matice sousednosti První zpusob ˚ je reprezentace pomocí matice sousednosti. Jedná se o matitici n × n, kde n je poˇcet vrcholu˚ grafu. ˚ Prvek Gi,j této matice G je potom roven nule, pokud z vrcholu i do vrcholu j nevede hrana, pokud tato hrana existuje, je u grafu, ˚ které se používají v této práci roven jedné. Existuje i možnost reprezentace, kdy se tento prvek rovná délce hrany, kterou zastupuje nebo poˇctu hran vedoucích z vrcholu i do vrcholu j. 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 1 0 0 0 1 0 Je vidˇet, že v pˇrípadˇe neorientovaných grafu˚ platí Gi,j = Gj,i , a tak k reprezentaci tohoto grafu postaˇcí pouze horní trojúhelníková matice. Pokud graf nepovoluje hranu z vrcholu do sebe sama, není tˇreba si pamatovat ani cˇ ísla na hlavní diagonále. Výhodou tohoto zpusobu ˚ reprezentece grafu je, že lze v konstantím cˇ ase do grafu pˇridat, pˇrípadnˇe odebrat hranu. Mezi nevýhody pak patˇrí, že pˇri pˇridání nebo odebrání vrcholu je tˇreba celou matici zmˇenit a pro reprezentaci grafu˚ s hodnˇe vrcholy a málo hranami není tento zpusob ˚ vhodný, protože místo, které graf v pamˇeti zabírá, roste kvadraticky s poˇctem jeho vrcholu˚ a bez ohledu na poˇcet hran. Matice incidence Další zpusob ˚ používá matici incidence, tato má rozmˇer n × m, kde n je poˇcet vrcholu˚ a m poˇcet hran. Prvek Gi,j pak znaˇcí, zda je hrana j incidentní k vrcholu i. 1 0 0 0 0 1 1 0 1 0 0 1 1 0 0 0 0 1 1 1 0 0 0 0 1 Z tohoto zápisu lze snadno vyˇcíst, že tento zpusob ˚ reprezentace je výhodnˇejší než pˇredchozí, pouze pokud má graf výraznˇe více vrcholu˚ než hran. V takovém pˇrípadˇe by došlo k úspoˇre místa nutného k zapamatování grafu. Zustaly ˚ však všechny nevýhody použití matice sousednosti spojené s pˇridáváním a odebíráním vrcholu˚ a navíc jsou ted’ stejné 5
1. V YBRANÉ KAPITOLY Z TEORIE GRAF U˚ problémy i s pˇridáváním a odebíráním hran. Navíc nejde ani v konstantním cˇ ase zjistit, zda jsou dva vrcholy sousedními. Seznam sousedu˚ Kromˇe matic lze k reprezentaci grafu˚ použít také pole a to opˇet nˇekolika zpusoby. ˚ Prvním z nich je takzvaný seznam sousedu, ˚ kdy se pro každý vrchol grafu uchovává v poli seznam jeho sousedu. ˚ Toho je v podstatˇe možno dosáhnou tak, že pro každý vrchol existuje samostatné pole s jeho sousedy a tato jsou pak uložena napˇríklad v poli, kdy na každém indexu je odkaz na pole sousedu˚ pˇríslušného vrcholu. Pokud jsou jednotlivá pole uložena v objektech, které reprezentují vrcholy, je takto jednoduše možné ukládat ruzná ˚ další data o tˇechto vrcholech. Je také možné použít pole pouze dvˇe, kde v jednom poli jsou uloženi sousedi vrcholu˚ grafu a v poli druhém indexy, na kterých zaˇcínají sousedi pˇríslušného vrcholu. 0 0 0 2
1 1
2 3
1 1 3 4
2 4 4 2
3 6 5 4
4 9 6 2
7 3
8 5
9 4
Pokud se použije tato reprezentace, staˇcí obvykle na uložení grafu ménˇe pamˇeti, nebot’ pamˇet’ová nároˇcnost této struktury roste lineárnˇe s poˇctem vrcholu˚ a poˇctem hran. Pˇridání hrany a vrcholu je možné v konstantním cˇ ase. Problém je s jejich odebráním, na které je tˇreba cˇ as pro projití seznamu a nalezení požadovaného prvku. Stejný cˇ as je také potˇrebný na to, aby bylo zjištˇeno, zda se v grafu mezi dvˇema vrcholy nachází hrana. Seznam incidence Poslední zpusob ˚ uchovávání grafu v pamˇeti poˇcítaˇce, který zde bude zmínˇen, je seznam incidence. V tomto pˇrípadˇe existuje samostatný objekt pro každý vrchol a každou hranu grafu. Hrana si pak ve svém vnitˇrním stavu pamatuje, které vrcholy jsou k ní incidentní a vrchol, které hrany z nˇej vedou. Oproti pˇredchozímu zpusobu ˚ je tento výhodnˇejší v tom, že je možné ukládat informace nejen o vrcholech, ale i o jednotlivých hranách. Nevýhodou je pak vˇetší pamˇet’ová nároˇcnost.
1.2 Parametrizovaná složitost Klasicky se složitost algoritmu, ˚ at’ již prostorová nebo cˇ asová, uvádí v závislosti na velikosti vstupu. To ovšem znamená, že jsou ignorovány jakékoli informace o struktuˇre vstupu. Pˇritom pro vstup v urˇcitém formátu muže ˚ být nalezení rˇ ešení problému snažší než pro vstup obecný. Teorie parametrizované složitosti tak nebere v úvahu pouze velikost vstupu, ale také další podmínku, která je vyjádˇrena takzvaným parametrem. Parametr je cˇ íselná hodnota, která urˇcitým zpusobem ˚ závisí na vstupu. Zámˇerem je poté snížení celkové složitosti rˇ ešení problému, a to zejména pokud je tento parametr malý. 6
1. V YBRANÉ KAPITOLY Z TEORIE GRAF U˚ Existuje nˇekolik tˇríd problému˚ definovaných podle toho, jakým zpusobem ˚ závisí cˇ as potˇrebný na jejich vyˇrešení na parametru. Tˇrída s nejnižsí cˇ asovou složitostí se nazývá Fixed-Parameter Tractability (FPT). Problémy patˇrící do této tˇrídy je možné rˇ ešit pomocí fpt-algoritmu (fixed-parameter tractable). Takto se nazývá algoritmus, který má cˇ asovou složitost O(f (k) ∗ nc )), kde n je velikost vstupu, k je parametr, c je konstanta a f je funkce aplikovaná na parametr. Pokud tedy máme urˇcitou tˇrídu grafu, ˚ která má parametr pevnˇe daný, je problém pro grafy z této tˇrídy rˇ ešitelný v polynomiálním cˇ ase. 222
k
Funkce f(k) muže ˚ být jakákoli funkce závislá na k, napˇríklad 22 . Problém je sice stále rˇ ešitelný v polynomiálním cˇ ase, ale konstanta je tak vysoká, že rˇ ešení v cˇ ase exponenciálním muže ˚ být ve vˇetšinˇe pˇrípadu˚ výhodnˇejší. To, že je hodnota urˇcitého parametru grafu nižší než hodnoty parametru˚ jiných, tedy nemusí znamenat, že s použitím tohoto parametru dospˇeje algoritmus k rˇ ešení nejrychleji. Parametry vrcholové pokrytí a twin-cover, zjišt’ované v této práci, je možné porovnávat pomˇernˇe pˇrímo. Pˇri srovnání jejich velikosti s neighborhood diversity je ovšem tˇreba vzít v úvahu konkrétní algoritmus. Hlavním úkolem teorie parametrizované složitosti je dokázat, že urˇcité problémy nepatˇrí do tˇrídy FPT. Existuje mnoho tˇríd problému, ˚ které se zdají být rozdílné a zˇrejmˇe nepatˇrí do tˇridy FPT. Jako tˇrída s nejvˇetší cˇ asovou složitostí se uvádí tˇrída XP. Platí F P T ⊂ XP , XP je jediná tˇrída, pro kterou je známo, že XP 6= F P T . Problémy patˇrící do této tˇrídy jsou rˇ ešitelné pomocí algoritmu˚ s cˇ asovou složitostí O(nf (k) ).[2] Z tˇechto definic vyplývá, že pro rychlejší bˇeh grafových algoritmu˚ je duležitá ˚ pˇredevším tˇrída FPT. Fpt-algoritmy existují pro velké množství NP-složitých problému[3], ˚ které je díky nim možné vyˇrešit v polynomiálním cˇ ase. Za jeden z nejzákladnˇejších a nejúspˇešnˇejších parametru˚ používaných pro rˇ ešení problému˚ patˇrících do tˇrídy FPT je považován treewidth[4] (zjednodušenˇe lze rˇ íci, že udává, jak moc se graf podobá stromu). Na uˇrité problémy lze také použít jako parametr napˇríklad pathwidth, branchwidth nebo cliquewidth.[5]
1.3 Vrcholové pokrytí Velikost minimálního vrcholového pokrytí lze použít jako parametr pro rˇ ešení problému˚ patˇrících do tˇrídy FPT. Platí, že graf s vrcholovým pokrytím k má pathwidth nejvýše k [6]. Z toho plyne, že vrcholové pokrytí grafu mužeme ˚ pokládat pro úˇcely fptalgoritmu˚ za silnˇejší parametr než pathwidth. Vrcholové pokrytí2 grafu G je množina vrcholu˚ C(G) ⊆ V (G) taková, že pro všechny hrany {u, v} ∈ E(G) platí, že bud’ u ∈ C(G) nebo v ∈ C(G). Protože tuto podmínku splnuje ˇ i C(G) = V (G), není cílem najít jakékoli vrcholové pokrytí grafu, ale takové, pro které platí, že velikost C(G) je minimální. 2. anglicky oznaˇcované jako vertex cover
7
1. V YBRANÉ KAPITOLY Z TEORIE GRAF U˚
Obrázek 1.2: Vrcholové pokrytí a minimální vrcholové pokrytí grafu. Pˇresnˇeji rˇ eˇceno cílem je obvykle najít takové k = |C(G)|, které bude co nejmenší. Je dokázáno, že problém zjistit, zda pro dané k existuje vrcholové pokrytí grafu G takové, že k ≥ |C(G)| je NP-úplný[7], to zjednodušenˇe rˇ eˇceno znamená, že najít vrcholové pokrytí, které splnuje ˇ zadanou podmínku, za všeobecnˇe ustálených složitostních pˇredpokladu, ˚ není možné pomocí deterministickýho algoritmu v polynomiálnim cˇ ase. Ovˇerˇ it, zda urˇcitá množina vrcholu˚ velikosti k, která je výdávána za vrcholové pokrytí tímto je, lze pak v cˇ ase polynomiálním, kdy pouze staˇcí ovˇerˇ it, že alesponˇ jeden koncový vrchol, každé hrany grafu patˇrí do této množiny. Problém urˇcení vrcholového pokrytí lze použít i k rˇ ešení ostatních parametru˚ grafu. ˚ Kupˇríkladu lze snadno dokázat, že po operaci V (G) − C(G) dostaneme množinu vrcholu, ˚ která je nezávislou množinou. Pokud bylo vrcholové pokrytí minimální, je pak tato nezávislá množina maximální. Hlavní význam vrholového pokrytí grafu spoˇcívá právˇe v tom, že jako pomˇernˇe obecný parametr je možné ho použít k rˇ ešení velké skupiny NP-tˇežkých problému˚ v polynomiálním cˇ ase. Takto je možné zjistit tˇreba cutwidth, bandwidth, imbalance nebo distortion3 .[8] Pokud jde o jeho praktické využití, toto lze spatˇrit napˇríklad v bioinformatice, kde ho lze použít napˇríklad ke konstrukci fylogenetických stromu˚ pˇri identifikaci fenotypu.[9] ˚
1.4 Neighborhood diversity Vrcholové pokrytí je tedy pomˇernˇe silným parametrem. Problém je, že existuje málo tˇríd grafu, ˚ pro které nabývá nízkých hodnot[10]. V cˇ lánku Michaela Lampise je ukázáno, že v urˇcitých pˇrípadech je místo vrcholového pokrytí možné použít neighborhood diversity, jehož velikost je omezena na více tˇrídách grafu˚ než velikost vrcholového pokrytí.[11] Neighborhood diversity jako parametr pro fpt-algoritmy je pomˇernˇe nový, a 3. Názvy ponechány v angliˇctinˇe.
8
1. V YBRANÉ KAPITOLY Z TEORIE GRAF U˚ tak zatím není známo mnoho pˇrípadu˚ jeho použití. Na urˇcitých tˇrídách grafu˚ slouží pˇredevším jako lepší varianta k vrcholovému pokrytí. Tento parametr grafu je definován jako poˇcet tˇríd ekvivalence, do kterých jsou vrcholy rozˇrazeny. Pro každé dva vrcholy patˇrící do téže tˇrídy musí platit, že množiny jejich sousedu˚ jsou shodné. Pokud jsou tyto vrcholy spojeny hranou, pak patˇrí do stejné tˇrídy ekvivalence právˇe tehdy, když by tyto dva byly cˇ leny jedné tˇrídy po odebrání hrany, která je spojuje.
Obrázek 1.3: Tˇrídy ekvivalence neighborhood diversity.
1.5 Twin-cover Jako vstupní parametr ftp-algoritmy je možné použít i twin-cover, který je vždy nejvýše tak velký jako vrcholové pokrytí grafu. Pro tento parametr také platí, že je jeho velikost omezena na více tˇrídách grafu˚ než velikost vrcholového pokrytí.[12] Protože tento parametr byl pˇredstaven teprve nedávno, není známo mnoho pˇrípadu˚ jeho použití jako parametru pro fpt-algoritmy. Na tˇrídách grafu, ˚ kde ho lze použít místo vrcholového pokrytí, slouží jako jeho efektivnˇejší varianta. Protože obecnˇe platí, že jeho velikost je menší než velikost minimálního vrcholového pokrytí grafu ,parametrizované algoritmy využívající tento parametr tak bˇeží podstatnˇe rychleji, než pˇri použití vrcholového pokrytí. K definování toho, co je twin-cover, je tˇreba nejprve definovat takzvanou twin-edge, kterou tento algoritmus používá. Twin-edge je hrana v grafu taková, pro kterou platí, že oba koncové vrcholy této hrany mají stejné sousední vrcholy. Samozˇrejmˇe s pˇrihlédnutím k tomu, že tyto vrcholy jsou spojeny hranou, a tak je nutno z porovnávaných množin sousedu˚ tyto vrcholy odstranit. Poté, co najdeme všechny twin-edges ve zkoumaném grafu, tyto odstraníme a na takto zmenšeném grafu hledáme vrcholové pokrytí. Protože však platí, že nový graf bude mít stejnˇe nebo ménˇe hran než graf puvodní, ˚ platí také pro twin-cover tohoto grafu X(G), že |X(G)| ≤ |C(G)|.
9
1. V YBRANÉ KAPITOLY Z TEORIE GRAF U˚
Obrázek 1.4: Twin-edge a twin cover na grafu.
10
Kapitola 2
Použité rˇešení V této cˇ ásti je popsané zvolené rˇ ešení jednotlivých problému˚ a jeho implementace, popˇrípadˇe dukazy, ˚ že jsou použitá rˇ ešení správná.
2.1 Reprezentace grafu Z možností, jak reprezentovat graf v pamˇeti poˇcítaˇce popsaných v pˇredchozí kapitole, byla vybrána možnost tˇretí, tedy uložení pomocí seznamu sousedu. ˚ Vzhledem k tomu, že grafy, na kterých se mají zkoumat jednotlivé charakteristiky, nemají v pomˇeru k pocˇ tu vrcholu˚ zásadnˇe mnoho hran, je tento zpusob ˚ lepší než využití matic. Dalším du˚ vodem je to, že v prubˇ ˚ ehu algoritmu pro zjištˇení vrcholového pokrytí, je tˇreba odebírat jednotlivé vrcholy a to, jak bylo ukázáno, je pˇri reprezentaci maticí cˇ asovˇe nároˇcné. Jednotlivé seznamy sousedu˚ jsou uloženy v ekvivalentu hashovací tabulky. Toto rˇ ešení je zvoleno pˇredevším proto, že umožnuje ˇ pˇrístup v konstantním cˇ ase a v použitých algoritmech je tˇreba cˇ asto pˇristupovat právˇe k množinˇe sousedu˚ jednotlivých vrcholu. ˚
2.2 Neighborhood diversity Teoretické základy Tento problém je rˇ ešitelný v polynomiálním cˇ ase. Je zˇrejmé že pokud G0 = (V 0 , E 0 ) je indukovaným podgrafem grafu G = (V, E), pak nd(G0 ) ≤ nd(G), protože je vidˇet, že rozdˇelení vrcholu˚ grafu G do tˇríd ekvivalence bude platné i pro jeho indukovaný podgraf G’. V opaˇcném smˇeru toto tvrzení samozˇrejmˇe neplatí. Pokud tedy budeme tˇrídy ekvivalence postupnˇe konstruovat s pˇrihlédnutím k celému grafu G mˇeli bychom dojít ke správnému výsledku. Celý algoritmus pracuje tak, že seˇradí (jakkoli) vrcholy vstupního grafu G. Z pˇredchozího odstavce vyplývá, že pokud máme indukovaný podgraf s k vrcholy, ve kterém jsou tyto rozdˇeleny do w tˇríd ekvivalence, tak pro podgraf s k+1 vrcholy bude tˇreba alesponˇ w tˇríd ekvivalence a nejvýše w+1. Pˇri zpracovávání vrcholu tedy mohou nastat dvˇe situace. Bud’ mužeme ˚ vrchol zaˇradit do nˇekteré z w tˇríd ekvivalence nebo to možné není. Toto je možné ovˇerˇ it v polynomiálním cˇ ase. Pokud nastane druhý pˇrípad, znamená to, že v každé z tˇríd ekvivalence existuje vrchol, který má odlišné sousedy než 11
ˇ 2. P OUŽITÉ REŠENÍ
vrchol zpracovávaný, to znamená k souˇcasným tˇrídám ekvivalence musí pˇribýt další, která prozatím obsahuje pouze zpracovávaný vrchol.[11] Konkrétní rˇešení Problémem bylo, jak popsat tˇrídy ekvivalence. Z definice neighborhood diversity by se mohlo zdát, že si staˇcí pro každou tuto tˇrídu pamatovat množinu sousedních vrcholu, ˚ která je všem jejím cˇ lenum ˚ spoleˇcná. Je ovšem tˇreba mít na pamˇeti, že spoleˇcnou tˇrídu ekvivalence mohou tvoˇrit i vrcholy, které jsou spojeny hranou. V tomto pˇrípadˇe zjevnˇe nejsou množiny jejich sousedu˚ stejné. Tvrzení. Pokud se na tento problém podíváme blíže mužeme ˚ vidˇet, že existují dva typy tˇríd ekvivalence. V prvním z nich tvoˇrí všechny vrcholy v této tˇrídˇe nezávislou množinu a seznam sousedu˚ všech vrcholu˚ ve tˇrídˇe je tedy opravdu stejný. V pˇrípadˇe druhém tvoˇrí všechny vrcholy v této tˇrídˇe kliku, to znamená, že žádné dva vrcholy v této tˇrídˇe nemají stejný seznam sousedu. ˚ Shodnou množinu vrcholu˚ dostaneme, pokud u každého vrcholu v této tˇrídˇe pˇridáme do seznamu jeho sousedu˚ i vrchol samotný. Ted’ je tˇreba dokázat, že neexistuje žádná tˇrída ekvivalence, která nesplnuje ˇ právˇe jednu z pˇredchozích dvou podmínek. Dukaz. ˚ Mˇejme tˇrídu ekvivalence Vk a právˇe zpracovávaný vrchol v, který má být do této tˇrídy pˇridán. Tento vrchol musí mít bezesporu v množinˇe svých sousedu˚ právˇe ty vrcholy, které sousedí s vrcholy v množinˇe Vk a zárovenˇ do Vk nepatˇrí. Pokud by vrcholu v nˇekterý z tˇechto vrcholu˚ mezi jeho sousedy chybˇel nebo pokud by existoval takový vrchol w sousední s v, pro který platí w ∈ / Vk a zárovenˇ w nepatˇrí ani mezi sousedy vrcholu˚ z Vk , pak zˇrejmˇe vrchol v nemuže ˚ patˇrit do tˇrídy ekvivalence neighborhood diversity Vk . Pokud do množiny sousedu˚ vrcholu v nepatˇrí žádný vrchol z tˇrídy Vk , tak tento vrchol patˇrí do Vk právˇe tehdy, když žádné dva vrcholy Vk nejsou spojeny hranou. Je totiž vidˇet, že kdyby toto neplatilo, nemˇel by vrchol v stejnou množinu sousedu˚ jako vrcholy ve tˇrídˇe Vk , pˇriˇcemž by ani neexistovala žádná hrana mezi v a jakýmkoli vrcholem z Vk . A pˇri neexistenci hrany mezi vrcholy je pro jejich zaˇrazení do stejné tˇrídy ekvivalence nutnou podmínkou, aby množiny jejich sousedu˚ byly shodné. To by v tomto pˇrípadˇe neplatilo. Je tedy vidˇet, že pokud vrchol v nemá spoleˇcnou hranu s žádným z vrcholu˚ z tˇrídy Vk potom, aby vrchol v mohl patˇrit do tˇrídy Vk , musí vrcholy této tˇrídy pˇred jeho pˇridáním tvoˇrit nezávislou množinu. Protože vrchol v nemá spoleˇcnou hranu s žádným vrcholem z této tˇrídy budou vrcholy z Vk tvoˇrit nezávislou množinu i po jeho pˇridání. Pokud do množiny sousedu˚ vrcholu v patˇrí nˇejaké vrcholy z tˇrídy Vk , tak tento vrchol patˇrí do Vk právˇe tehdy, když všechny vrcholy Vk jsou spojeny hranou a zárovenˇ vˇcechny vrcholy z Vk patˇrí mezi sousedy vrcholu v. Nejprve tedy dokažme, že vrcholy Vk musí v tomto pˇrípadˇe tvoˇrit kliku. Pokud má vrchol v spoleˇcnou hranu s vrcholem w z Vk a tento vrchol v má patˇrit do této tˇrídy ekvivalence, znamená to, že musí mít stejné sousedy jako vrcholy z Vk . 12
ˇ 2. P OUŽITÉ REŠENÍ
To znamená, že i ostatní vrcholy z Vk musí být spojeny hranou s w. Ted’ ovšem mezi sousedy vrcholu w patˇrí všechny vrcholy z Vk . Protože se jedná o tˇrídu ekvivalence neighborhood diversity, musí tedy platit, že každý z tˇechto ostatních vrcholu˚ z Vk má mezi sousedy všechny ostatní vrcholy patˇrící do této tˇrídy. To tedy znamená, že pokud v má spoleˇcnou hranu s jakýmkoli vrcholem z Vk a má-li patˇrit do stejné tˇrídy ekvivalence musí vrcholy z Vk tvoˇrit kliku. Pokud má vrchol v spoleˇcnou hranu s jedním nebo více vrcholy z Vk a tento vrchol v má patˇrit do této tˇrídy ekvivalence, bylo již ukázáno, že vrcholy v množinˇe Vk musí tvoˇrit kliku. To znamená, že mezi sousedy jakéhokoliv vrholu z Vk patˇrí ostatní vrcholy z této množiny, to znamená, že aby vrchol v patˇril do stejné tˇrídy ekvivalence musí mezi jeho sousedy patˇrit všechny vrcholy z tˇrídy Vk . Vzhledem k tomu, že neexistuje jiná možnost, jak muže ˚ být zpracovávaný vrchol, který má být pˇridán do tˇrídy ekvivalence, s touto spojen, bylo ukázáno že pro tˇrídy ekvivalence neighborhood diversity musí platit, že všechny cˇ lenské vrcholy jedné tˇrídy tvoˇri bud’ nezávislou množinu nebo kliku. Samotná implementace tohoto algoritmu je pak rˇ ešena tak, že je vytvoˇrena množina množin sousedu˚ cˇ lenu˚ tˇríd, kde jednotlivé množiny reprezentují tˇrídy ekvivalence, tato je na zaˇcátku prubˇ ˚ ehu algoritmu prázdná. Následnˇe jsou procházeny všechny vrcholy grafu, pro které se kontroluje, zda patˇrí do nˇekteré z tˇríd ekvivalence. Pokud ano, algoritmus pˇrejde ke zpracovávání dalšího vrcholu. Pokud ne, je množina sousedu˚ tohoto vrcholu pˇridána mezi tˇrídy ekvivalence a cˇ ítaˇc poˇctu tˇríd je zvednut o jedna. Poslední krok je nutno lépe vysvˇetlit. Pˇri tvorbˇe nové tˇrídy ekvivalence, kdy má tato pouze jeden vrchol není jasné, zda se bude jednat o tˇrídu, kde všechny vrcholy tvoˇrí nezávislou množinu, nebo o tˇrídu, kde tyto tvoˇrí kliku. V grafu s jedním vrcholem totiž z definice plyne, že tento vrchol tvoˇrí jak nezávislou množinu tak kliku. Když tedy vytváˇríme novou tˇrídu ekvivalence je tˇreba do množiny množin sousedu˚ cˇ lenu˚ tˇríd vložit jak pouze sousedy právˇe zpracovávaného vrcholu pro pˇrípad, že by se tato tˇrída ukázala být tou, ve které tvoˇrí všichni její cˇ lenové nezávislou množinu, tak sousedy tohoto vrcholu sjednoceny s tímto vrcholem pro pˇrípad, že by se jednalo o tˇrídu jejíž cˇ lenové tvoˇrí kliku, cˇ ítaˇc se samozˇrejmˇe zvýší pouze o jedniˇcku. Že je tento postup korektní plyne z dukaz ˚ u˚ uvedených výše. Pokud se totiž bude jednat o tˇrídu ekvivalence, ve které všechny prvky tvoˇrí nezávislou množinu, neexistuje v grafu žádný vrchol, který patˇrí do této tˇrídy a souˇcasnˇe je sousedem zpracovávaného vrcholu. Množina sousedu˚ zpracovávaného vrcholu sjednocena s tímto vrcholem tak zustane ˚ nevyužita. Pokud by v grafu existoval vrchol, který by tuto množinu nˇejak využil, musel by tento být sousedem právˇe zpracovávaného vrcholu a mít s ním stejné ostatní sousedy. To by ovšem bylo možné pouze tehdy, pokud by tyto dva vrcholy byly oba cˇ leny tˇrídy ekvivalence, ve které její cˇ lenové tvoˇrí kliku. To ovšem není v rozporu s puvodním ˚ pˇredpokladem a koreknost této možnosti bude ukázána dále. Pokud se bude jednat o tˇrídu ekvivalence, ve které všechny prvky tvoˇrí kliku, neexistuje v grafu vrchol, který by pˇri svém zpracování využil množinu sousedu˚ zpracovávaného vrcholu. Pokud by existoval vrchol, který by mˇel stejnou množinu sousedu˚ se 13
ˇ 2. P OUŽITÉ REŠENÍ
zpracovávaným vrcholem, tak by tyto dva tvoˇrily tˇridu ekvivalence, ve které všechny prvky tvoˇrí nezávislou množinu. Naproti tomu žádný ze sousedu˚ zpracovávaného vrcholu by s ním nemohl tvoˇrit tˇrídu ekvivalence, protože by každý z nich mˇel souseda, kterého zpracovávaný vrchol nemá. To že by existoval vrchol, jehož množina sousedu˚ sjednocená s ním samým by byla stejná jako množina sousedu˚ zpracovávaného vrcholu není možné, protože tento vrchol by pak musel patˇrit mezi sousedy zpracovávaného vrcholu a zárovenˇ s ním nebýt spojen hranou, což odporuje základním definicím tˇechto pojmu. ˚ V použité implementaci tohoto algoritmu se tedy nejprve zkoumá, zda množina sousedu˚ zpracovávaného vrcholu sama nebo sjednocena s tímto vrcholem patˇrí do množiny množin sousedu. ˚ Pokud ano, pˇrejde se ke zpracovávání dalšího vrcholu, pokud ne, obˇe tyto množiny se vloží do množiny množin sousedu˚ a cˇ ítaˇc je zvýšen o jedniˇcku. Korektnost tohoto postupu byla ukázána výše. Tento algoritmus by jistˇe šel implementovat tak, aby nebyly tˇreba tyto dodateˇcné dukazy. ˚ Napˇríklad by bylo možné opravdu budovat tˇrídy ekvivalence neighborhood diversity. Zde by ovšem bylo nutné pamatovat si jednotlivé vrcholy, které do tˇechto tˇríd patˇrí a k následnému porovnání použít množiny jejich sousedu. ˚ Pokud by mˇelo být rozhodnuto, jestli se jedná o tˇrídu ekvivalence, ve které všechny prvky tvoˇrí kliku nebo o tu, kde všechny prvky tvoˇrí nezávislou množinu, aby mohla tato tˇrída být reprezentována pouze jednou množinou vrcholu˚ (v prvním pˇrípadˇe všechny vrcholy této tˇrídy a jejich sousedi mimo tˇrídu, ve druhém sousedi vrcholu˚ patˇrících do této tˇrídy), bylo by nutné, aby obsahovala alesponˇ dva prvky, aby bylo možné urˇcit o jaký druh se jedná. Toto rˇ ešení sice vypadá jednodušeji na pochopení, ale je složitˇejší na implementaci.
2.3 Odstranˇení twin-edges Teoretické základy Tento problém je rˇ ešitelný v polynomiálním cˇ ase. Jako nejzˇrejmˇejší pˇrístup k jeho rešení se jeví projít všechny dvojice vrcholu˚ grafu a porovnat jejich sousedy. Pokud množinu sousedu˚ vrcholu v oznaˇcíme jako N(v), tak aby hrana mezi zkoumanými vrcholy u a v mohla být oznaˇcena jako twin-edge, musí platit (N (v) ∩ v) = (N (u) ∩ u). Je zˇrejmé, že pokud by platilo pouze N (v) = N (u), tak zkoumané vrcholy mají sice stejné sousedy, ale nejsou spojeny hranou. To znamená, že mezi zkoumanými vrcholy není hrana, kterou by bylo možné oznaˇcit jako twin-edge. Konkrétní rˇešení Pokud v prubˇ ˚ ehu zkoumání dvojic vrcholu˚ zpracovávaného grafu narazíme na twinedge, není možno tuto okamžitˇe z grafu odebrat. Na obrázku Pˇredˇcasné odebrání twinedge z grafu je znázornˇena situace, kdy dva zpracovávané vrcholy jsou spojeny pomocí twin-edge a tato je odebrána. Pˇred touto akcí byly i ostatní hrany v grafu twin-edges, ale po ní to pˇrestalo platit. Je tedy tˇreba si v prubˇ ˚ ehu algoritmu pro odstranˇení twin-edges 14
ˇ 2. P OUŽITÉ REŠENÍ
Obrázek 2.1: Pˇredˇcasné odebrání twin-edge z grafu. bud’ pamatovat, které hrany je možné odstranit a tuto akci provést až po prozkoumání všech dvojic vrcholu, ˚ nebo zkoumat jeden graf a zmˇeny okamžitˇe provádˇet v grafu druhém, který byl se zkoumaným grafem, pˇred odebráním první hrany, shodný. V implementaci tohoto algoritmu mužeme ˚ využít tvrzení prokázaná v pˇredchozí kapitole, týkající se algoritmu pro výpoˇcet neighborhood diversity. Pˇresnˇeji týkající se tˇrídy ekvivalence neighborhood diversity, pro kterou platí, že všechny její prvky tvoˇrí kliku. Tuto tˇrídu je možné reprezentovat, jak bylo ukázáno, pomocí množiny vrcholu˚ do ní patˇrících sjednocené s množinou sousedu˚ tˇechto vrcholu˚ mimo tuto tˇrídu. Zbývá pouze dokázat, že: Tvrzení. Pokud ve vrcholu konˇcí více twin-edges, tak všechny vrcholy, do kterých tyto vedou sjednoceny s tímto vrcholem, tvoˇrí kliku. Pˇritom platí, že veškeré hrany, které spojují jednotlivé vrcholy této kliky, jsou také twin-edges. Nebo ještˇe lépe, dokázat že pro všechny kliky v grafu platí, že pokud mají vrcholy je tvoˇrící stejné sousedy mimo tuto kliku, vždy jsou všechny hrany mezi vrcholy v této klice twin-edges. Dále pak, že neexistují v grafu žádné twin-edges, které by do takovéto kliky nepatˇrily. Dukaz. ˚ Pravdivost prvního tvrzení lze ukázat snadno. Pro všechny kliky v grafu, které zárovˇenˇ splnují ˇ podmínky, aby mohly být považovány za tˇrídy ekvivalence eighborhood diversity, platí pro každé dva vrcholy u, v, které ji tvoˇrí (N (v) ∩ v) = (N (u) ∩ u). To znamená, že veškeré hrany v této klice je možné považovat za twin-edges. Druhé tvrzení platí také. Uvažujme vrchol v, ze kterého vede nenuluvý poˇcet twinedges. Pak pro každý vrchol u do kterého twin-edges z v vedou, musí platit už známé pravidlo (N (v) ∩ v) = (N (u) ∩ u). Tedy každý vrchol u, do kterého z v vede twin-edge má množinu svých sousedu˚ rovnu (N (v) − u) ∩ v. To ovšem také znamená, že každé dva vrcholy u,w, do kterých z v vedou twin-edges splnují ˇ podmínku (N (u) ∩ u) = (N (w) ∩ w). Musí být spojeny hranou, protože jsou oba spojeny pomocí twin-edge s v a tato hrana, která je spojuje je také twin-edge. Bylo tedy ukázáno, že hrana splnuje ˇ požadavky na twin-edge právˇe tehdy, když tato spojuje vrcholy kliky, pro jejíž všechny vrcholy platí, že množiny jejich sousedu˚ mimo tuto kliku jsou shodné. 15
ˇ 2. P OUŽITÉ REŠENÍ
Z provedených dukaz ˚ u˚ tedy vyplývá, že není nutné zkoumat pˇrítomnost twin-edge mezi všemi dvojicemi vrcholu, ˚ ale pouze budovat množinu klik, jejichž cˇ lenské vrcholy mají navzájem shodné množiny sousedních vrcholu˚ nacházejících se mimo tuto kliku. Každá takováto klika je, jak již bylo ukázano, charakterizovatelná množinou vrcholu˚ této kliky sjednocenou s množinou sousedních vrcholu˚ libovolného cˇ lenského vrcholu této kliky. V algoritmu odstranujícím ˇ twin-edges tak staˇcí každý vrchol navštívit pouze jednou. Následnˇe pˇredpokládáme, že je tento vrchol cˇ lenem výše popsané kliky. Pro právˇe zpracovávaný vrchol v pak ovˇerˇ íme, zda už existuje klika reprezentovaná množinou N (v) ∩ v. Pokud ano, vrchol v pˇridáme do množiny cˇ lenských vrcholu˚ této kliky, pokud ne, pˇridáme do seznamu klik novou reprezentovanou množinou N (v) ∩ v. Poté, co takto zpracujeme všechny vrcholy grafu, je každý z nich pˇriˇrazen k nˇejaké klice. Pokud z tohoto vrcholu nevede twin-edge, je tato klika tvoˇrena pouze tímto jedním vrcholem. Následnˇe procházíme všechny kliky vytvoˇrené v pˇredchozím bˇehu algoritmu. Víme, že všechny hrany mezi vrcholy patˇrícími do této kliky jsou twin-edges. Pro každou takovouto kliku tedy odebereme všechny hrany mezi vrcholy, které ji tvoˇrí. Jak bylo ukázáno výše tímto postupem odebereme z grafu všechny twin-edges.
2.4 Vrcholové pokrytí Teoretické základy Tento problém není rˇ ešitelný v polynomiálním cˇ ase. Jedná se o NP-úplný problém[7], jehož cˇ asová složitost je exponenciální a pˇri použití nejhoršího algoritmu O(2k ), kde k je nejvˇetší velikost množiny vrcholu˚ vrcholového pokrytí. Pokud si chceme být tedy jistí, že pro daný graf nalezneme velikost jeho minimálního vrcholového pokrytí, je tato složitostO(2n−1 ), kde n je poˇcet vrcholu˚ zkoumaného grafu. Puvodním ˚ cílem bylo, aby v této práci byl implementován algoritmus s parametrickou cˇ asovou složitostí O(1, 2738k + kn)[13]. I když je parametrizovaná složitost tohoto algoritmu takto nízká, v praxi se doba jeho bˇehu velmi prodlužuje kvuli ˚ cˇ asovˇe nároˇcným operacím, které je nutno provádˇet bˇehem jeho vykonávání. Protože hlavním cílem této práce nebylo implementovat co nejrychlejší algoritmus pro zjištˇení vrcholového pokrytí grafu, ale porovnat na urˇcitých grafech jejich vrcholové pokrytí s ostatními parametry, bylo po dohodˇe s vedoucím práce rozhodnuto, že staˇcí implementovat algoritmus s cˇ asovou složitostí O(2k ) a tento se pˇrípadnˇe pokusit zrychlit. Konkrétní rˇešení Základní algoritmus pro nalezení vrcholového pokrytí grafu pracuje rekurzivnˇe. Vybere vrchol zpracovávaného grafu. Pro ten existují dvˇe možnosti. Bud’ patˇrí do minimálního vrcholového pokrytí grafu nebo do nˇej nepatˇrí. Algoritmus tak spustí pro tyto dva pˇrípady dvˇe nové vˇetve programu. První z nich, kde zpracovávaný vrchol patˇril do mini16
ˇ 2. P OUŽITÉ REŠENÍ
málního vrcholového pokrytí, hledá vrcholové pokrytí na grafu, ze kterého byl tento vrchol odebrán a k je v tomto pˇrípadˇe sníženo o jedna. V druhém pˇrípadˇe zpracovávaný vrchol do minimálního vrcholového pokrytí nepatˇril, to ovšem znamená, že do nˇeho museli patˇrit všichni jeho sousedi, protože alesponˇ jeden koncový vrchol každé hrany grafu musí patˇrit do jeho vrcholového pokrytí. Tato vˇetev algoritmu následnˇe hledá vrcholové pokrytí na grafu, ze kterého byl odebrán zpracovávaný vrchol a všichni jeho sousedi. k je v tomto pˇrípadˇe sníženo o poˇcet sousedu˚ zpracovávaného vrcholu. Jednoduchým prostˇredkem, jak tento algoritmus urychlit, je najít takové vrcholy grafu, na kterých se nemusí vˇetvit, nebot’ je jisté, že patˇrí nebo nepatˇrí do minimálního vrcholového pokrytí. Tvrzení. Algoritmus pro nalezení nejmenšího vrcholového pokrytí nemusí vˇetvit na vrcholu stupnˇe jedna. Pokud se ve zpracovávaném grafu takový vrchol nachází, mu˚ žeme rˇ íct, že tento do minimálního vrcholového pokrytí nepatˇrí a jeho soused ano. Dukaz. ˚ Je zˇrejmé, že pro minimální vrcholové pokrytí grafu G VC(G) a jeho indukovaný podgraf G’ platí V C(G0 ) ⊆ V C(G). Pokud by vrchol v stupnˇe jedna patˇril do minimálního vrcholového pokrytí, bylo by následnˇe tˇreba hledat VC(G-{v}) s tím, že mimální vrcholové pokrytí celého grafu je |VC(G-{v})|+1. Pokud by ovšem tento vrchol do minimálního vrcholového pokrytí nepatˇril, patˇril by do nˇeho jeho soused a mimální vrcholové pokrytí celého grafu by tak bylo |VC(G-{v}-N(v))|+1, kde N(v) je jednoprvková množina sousedu˚ vrcholu v. Pˇritom platí, že V C(G − {v} − N (v)) ⊆ V C(G − {v}) a tedy |V C(G − {v} − N (v))| ≤ |V C(G − {v})|. Pokud tedy hledáme minimální vrcholové pokrytí grafu, který obsahuje vrchol stupnˇe jedna, tento nebude jeho souˇcástí. Vrcholy stupnˇe jedna je tˇreba z grafu odstranovat ˇ postupnˇe, jinak by mohlo dojít k tomu, že dva sousední vrcholy stupnˇe jedna budou oba odstranˇeny a zárovenˇ oba pˇridány do minimálního vrcholového pokrytí grafu. Rekurzivní algoritmus pro hledání minimálního vrcholového pokrytí grafu, který jako vstup bere graf a nezáporné celé cˇ íslo k, tak funguje následovnˇe: • Pokud vstupní graf obsahuje vrcholy stupnˇe jedna, postupnˇe tyto i jejich sousedy z grafu odstraní a za každou takovou dvojici sníží k o jedniˇcku. • Pokud je k záporné vrátí chybovou hodnotu. • Pokud je graf prázdný vrátí k • Vybere zpracovávaný vrchol v a pro tento – Spustí algoritmus pro graf G-{v} a cˇ íslo k-1. – Spustí algoritmus pro graf G-{v}-N(v) a cˇ íslo k-|N(v)| • Vrátí vˇetší z hodnot vrácených jím spuštˇenými algoritmy. 17
ˇ 2. P OUŽITÉ REŠENÍ
Pro další urychlení bˇehu tohoto algoritmu zavedeme další opatˇrení. Je zˇrejmé, že poté, co ze vstupního grafu odstraníme všechny vrcholy stupnˇe jedna, další takovéto mohou vzniknout pouze odebráním dalších vrcholu˚ tohoto grafu. Do rekurzivnˇe spouštˇených algoritnu˚ tedy kromˇe grafu a cˇ ísla k pˇredáme další parametr. Množinu vrcholu, ˚ které byly sousedy vrcholu˚ odebraných pˇred spuštˇením této vˇetve. Tím nemusíme hledat vrcholy stupnˇe jedna v celém grafu, ale pouze v této množinˇe. Také jistˇe nemá cenu pokraˇcovat v bˇehu algoritmu, pokud již není šance na nalezení menšího vrcholového pokrytí, než bylo dosud tímto algoritmem v nˇejaké vˇetvi pru˚ chodu zjištˇeno. Proto pokaždé, když algoritmus vrací parametr k, tento uloží, pokud je maximální zatím nalezený. Když se spouští rekurzivní volání algorimu, zjistí se, zda k do nˇeho pˇredané není menší než uložená hodnota. Pokud ano, v dalším provádˇení se nepokraˇcuje a je vrácena chybová hodnota nebot’ je jasné, že tato vˇetev již nemuže ˚ nalézt lepší výsledek než doposud objevený. Tyto provedené úpravy mnohonásobnˇe zrychlí bˇech algoritmu. Na urˇcitých grafech i o nˇekolik rˇ ádu˚ více než tisíckrát.
18
Kapitola 3
Konkrétní implementace V této kapitole je popsána konkrétní implementace a veˇrejné metody algoritmu˚ a ostatních tˇríd použitých ve vytvoˇreném programu. Veškerý kód je psán v programovacím jazyce Java verze 6.
3.1 Zadání Cílem této práce bylo vytvoˇrit program, který spoˇcítá urˇcité parametry na grafech a tyto následnˇe porovnat. Konkrétnˇe bylo tˇreba, aby tento program zvládal následující operace: • Naˇctení grafu ze vstupního souboru. • Spoˇctení vrcholového pokrytí grafu. • Spoˇctení neighborhood diversity grafu. • Spoˇctení twin-cover grafu. • Nalezení vhodného indukovaného podgrafu pro pˇrípad, že je vstupní graf pˇríliš velký a výše popsané operace není možné dokonˇcit v rozumném cˇ ase.
3.2 Graf Vzhledem k tomu, že v Javˇe není bez použití rozšiˇrujících knihoven pˇrítomný žádný vhodný objekt pro reprezentaci grafu a tyto knihovny obsahují mnohem více metod, než je pro rˇ ešení zadaného problému potˇrebné, ale stejnˇe neimplementují algoritmy potˇrebné v této práci (napˇríklad JGraphT), rozhodl jsem se definovat vlastní rozhraní Graph. Toto poskytuje medoty potˇrebné k prubˇ ˚ ehu zadaných algoritmu˚ a pˇritom nejsou kladeny vysoké nároky na jeho implementaci. Jakákoli tˇrída reprezentující graf, která by chtˇela využít algoritmy na zjištˇení parametru˚ grafu vytvoˇrené v rámci této práce, musí implementovat toto rozhraní. Metody tohoto rozhraní nevrací žádné speciální objekty, které by mˇely reprezentovat jednotlivé vrcholy nebo hrany, ale pouze celá cˇ ísla. Každý vrchol grafu je tedy reprezentován jedním cˇ íslem. S hranami pak toto rozhraní nepracuje vubec. ˚ Konkrétnˇe jsou poskytovány následující metody: 19
3. K ONKRÉTNÍ IMPLEMENTACE Graph copy() Vrátí kopii tˇrídy. Tato metoda je potˇreba pˇredevším kvuli ˚ vˇetvení pˇri hledání vrcholového pokrytí. Každá vˇetev tak muže ˚ dostat vlastní graf a nemˇenit data vˇetvím ostatním. void addEdge(int x,int y) Pˇridávat hrany je tˇreba hlavnˇe bˇehem naˇcítání grafu ze souˇ boru. Císla pˇredávaná této metodˇe reprezentují vrcholy, které mají být hranou spojeny. Pokud vrchol s daným cˇ íslem v grafu neexisluje, vytvoˇrí se. void addVertex(int x) Tato metoda pˇridá do grafu nový vrchol reprezentovaný cˇ íslem. Pokud tento už v grafu existuje, neprovede žádnou akci. int getNumberOfEdges() Vrátí poˇcet hran v grafu. Slouží pouze k získání informací o zpracovávaném grafu, v prubˇ ˚ ehu implementovaných algoritmu˚ není použita. Set
getNeighbours(int x) Tato metoda vrátí množinu cˇ ísel reprezentující vrcholy sousední s vrcholem zadaným. List getVertices() Vrátí seznam cˇ ísel reprezentujících všechny vrcholy grafu. boolean removeEdge(int x,int y) Odebere z grafu hranu spojující zadané dva vrcholy. Pokud tato není souˇcástí grafu, neprovede žádnou akci a vrátí false, pokud ano true. boolean isEdge(int x,int y) Zjistí, zda jsou zadané dva vrcholy spojeny hranou. boolean removeVertex(int x) Odebere z grafu zadaný vrchol a vrátí výsledek akce.
3.3 Naˇcítání grafu Grafy se kterými program pracuje jsou uloženy v souborech konˇcících pˇríponou .dgf. Tento typ vstupních souboru˚ je použit k uložení grafu˚ dostupných na internetových stránkách TreewidthLIB (dostupné z http://www.staff.science.uu.nl/ bodla101/treewidthlib/). Jedná se o textový soubor, ve kterém jsou uloženy hrany reprezentovaného grafu. V tˇechto souborech jsou o grafech uloženy i další informace. Napˇríklad, zda se jedná o graf orientovaný, charakteristiky jednotlivých vrcholu˚ a další popis. Protože však pracujeme s neorientovanými grafy, jsou všechny hrany uložené ve vstupních souborech interpretovány jako neorientované. K jiným informacím, než tˇem o pˇrítomnosti hrany, se pˇri naˇcítání grafu nepˇrihlíží. Každý rˇ ádek ve vstupním souboru zaˇcíná urˇcitým symbolem (písmenem), který ˇ oznaˇcuje, co je na tomto uloženo. Rádky nesoucí informaci o pˇrítomnosti hrany jsou uvozeny písmenem e, které je následováno dvˇema celými cˇ ísly oznaˇcujícími vrcholy hranou spojené. Pˇri cˇ tení vstupního souboru se tedy zpracovávají pouze rˇ ádky, které zaˇcínají písmenem e následovaným mezerou. Poté se kontroluje, jestli je toto následováno dvˇema argumenty a jestli jsou oba celá cˇ ísla. Pˇri splnˇení tˇechto dvou podmínek je do grafu 20
3. K ONKRÉTNÍ IMPLEMENTACE pˇridána hrana spojující zadané dva vrcholy. Pˇri jejich nespnˇení je naˇcítání ze souboru ukonˇceno výjimkou. Ze zvoleného zpusobu ˚ zápisu je vidˇet, že není možné mít uloženy vrcholy grafu, které nemají žádné sousedy. Tyto však nijak nemˇení vrcholové pokrytí ani twin-cover grafu a poˇcet tˇríd neighborhood diversity zvyšují o jedna. Tyto vrcholy tedy nejsou pro zadané problémy duležité. ˚ Pokud je ve vstupním souboru nˇekterá hrana uvedena vícekrát, napˇríklad z duvodu ˚ chyby nebo kvuli ˚ tomu, že záznam mˇel puvodnˇ ˚ e reprezentovat orientovaný graf, další výskyt této hrany výsledný graf nijak neovlivní.
3.4 Redukce grafu Vzhledem k tomu, že hledání vrcholového pokrytí na vˇetších grafech je cˇ asovˇe nároˇcné, u tˇechto je algoritmu pˇredáván jejich indukovaný podgraf. Ten je tˇreba nejprve vytvoˇrit. Pˇri budování podgrafu se zadaný graf prochází do šíˇrky a postupnˇe se pˇridávají vrcholy, dokud jejich poˇcet nedosáhne zadané meze. Následnˇe je pro každé dva z tˇechto pˇridaných vrcholu˚ zkontrolováno, zda jsou v puvodním ˚ grafu spojeny hranou. Pokud ano, je hrana pˇridána i v grafu novém.
3.5 Tˇrídy s algoritmy Všechny tˇrídy, které slouží ke zjištˇení parametru grafu popsaných výše implementují metodu spoleˇcného rozhraní int solve(Graph graph). graph je zde instance tˇrídy reprezentjící graf, která implementuje výše popsané rozhraní Graph. Tato metoda vrací cˇ íslo, které je výsledkem algoritmu, který tˇrída provádí. U tˇrídy implementující algoritmus pro zjištˇení minimálního vrcholového pokrytí je to tedy poˇcet vrcholu, ˚ které do množiny tohoto pokrytí patˇrí. U neighborhood diversity poˇcet tˇríd ekvivalence, ve kterých vrcholy splnují ˇ podmínky, aby mohly být vzájemnˇe v relaci. Twin-cover pak vrací poˇcet hran, které byly v prubˇ ˚ ehu algoritmu z grafu odstranˇeny, tedy poˇcet twin-edges puvodního ˚ grafu.
3.6 Ovládání programu Samotný program se pak spouští z pˇríkazové rˇ ádky. Aby bylo možné zjistit pouze nˇekteré parametry zkoumaného grafu, napˇriklad u grafu, který je pˇríliš velký a vrcholové pokrytí ani twin-cover na nˇem nelze tímto programem zjistit v rozumném cˇ ase, je možné zjistit poˇcet jeho twin-edges a poˇcet tˇríd ekvivalence neighborhood diversity. K tomuto úˇcelu slouží pˇrepínaˇce, které je možné tomuto programu pˇredat a které mˇení parametry tímto programem zjišt’ované. Je možné zadat následující argumenty: jméno vstupního souboru Tento parametr je povinný a musí být vždy uveden na prvním místˇe. Pokud tomu tak není, program neprovede žádnou akci. Aby byl z pˇre21
3. K ONKRÉTNÍ IMPLEMENTACE dávaného vstupního souboru naˇcten graf, je tˇreba, aby tento splnoval ˇ podmínky popsané v podkapitole Naˇcítání grafu. Tedy pˇredevším podmínky na vnitˇrní usporˇ ádání souboru, konkrétní pˇrípona není duležitá. ˚ -vc
Program spuštˇený s tímto pˇrepínaˇcem vypíše velikost minimálního vrcholového pokrytí grafu uloženého ve vstupním souboru.
-nd Program spuštˇený s tímto pˇrepínaˇcem vypíše poˇcet tˇríd ekvivalence neighborhood diversity grafu uloženého ve vstupním souboru. -te
Program spuštˇený s tímto pˇrepínaˇcem vypíše poˇcet twin-edges grafu uloženého ve vstupním souboru.
-tc
Program spuštˇený s tímto pˇrepínaˇcem vypíše velikost minimálního twin-cover grafu uloženého ve vstupním souboru.
-n
Program spuštˇený s tímto pˇrepínaˇcem vypíše pouze cˇ ísla, které nejsou doplnˇena textem vysvˇestlujícím jejich význam.
-s Program spuštˇený s tímto pˇrepínaˇcem nehledá parametry pro celý graf, ale pouze pro jeho indukovaný podgraf s poˇctem vrcholu˚ uvedeným za výrazem -s. Poukud je programu pˇredáno pouze jméno vstupního souboru, vypíše všechny parametry a tyto budou doprovázeny vysvˇetlujícím textem. Také jsou vypsány informace o zpracovávaném grafu, konkrétnˇe poˇcet hran, poˇcet vrcholu˚ a jméno souboru, ze kterého byl graf naˇcten. Parametry jsou vypsány v poˇradí: poˇcet tˇríd ekvivalence neighborhood diversity, poˇcet vrcholu˚ minimálního vrcholového pokrytí, poˇcet twin-edges, pocˇ et vrcholu˚ minimálního twin-cover. Stejné poˇradí výpisu parametru˚ grafu je zachováno, i pokud je program spuštˇen s nˇejakými pˇrepínaˇci. V tomto pˇrípadˇe pouze urˇcitá cˇ ísla ve výpisu chybí.
22
Kapitola 4
Porovnání parametru˚ na zadaných grafech V této kapitole jsou uvedeny prametry zadaných grafu˚ spoˇctené výše uvedemi algoritmy. Tyto parametry jsou následnˇe pˇrehlednˇe porovnány jejich zápisem do tabulky. Jako zdroj grafu˚ posloužila internetová stránka TreewidthLIB. Grafy dostupné na této stránce by mˇely být cˇ erpány z praxe. Jde zejména o grafy, na kterých je pˇri praktických aplikacích tˇreba zjistit jejich treewidth.
4.1 Tabulka s porovnávanými parametry V jednotlivých sloupcích tabulky jsou postupnˇe uvedeny následující hodnoty: graf Jméno souboru, ve kterém je graf uložen. Není uvedena pˇrípona. |V(G)| Poˇcet vrcholu˚ grafu. |E(G)| Poˇcet hran grafu. ND Poˇcet tˇríd ekvivalence neighborhood diversity. VC Velikost minimálního vrcholového pokrytí grafu. T-E Poˇcet twin-edges grafu. TC Velikost minimálního twin-cover grafu. Pokud je v urˇcitém políˇcku tabulky uveden symbol -, znamená to, že tento parametr nebylo možné pro daný graf s použitím implementovaných algoritmu˚ zjistit v rozumném cˇ ase. V tomto pˇrípadˇe jsou v dalším rˇ ádku tabulky uvedeny parametry jeho indukovaného podgrafu s poˇctem vrcholu˚ uvedeným v pˇríslušném sloupci tabulky. graf anna anna-pp david david-pp fpsol2.i.1 fpsol2.i.1
|V(G)| |E(g)| ND VC 138 493 108 58 22 148 21 17 87 406 65 51 29 191 28 23 269 11654 175 170 4993 108 129
T-E 14 1 23 1 142 155
TC 45 17 41 22 115 23
4. P OROVNÁNÍ PARAMETR U˚ NA ZADANÝCH GRAFECH fpsol2.i.1-pp fpsol2.i.1-pp fpsol2.i.2 fpsol2.i.2 fpsol2.i.2-pp fpsol2.i.2-pp fpsol2.i.3 fpsol2.i.3 fpsol2.i.3-pp fpsol2.i.3-pp games120 games120 games120-pp games120-pp homer homer homer-pp huck inithx.i.1 inithx.i.1 jean le450_15a le450_15a le450_15a-pp le450_15a-pp le450_15b le450_15b le450_15b-pp le450_15b-pp le450_15c le450_15a miles250 miles500 miles750 miles1000 miles1500 musol.i.1 musol.i.1-pp musol.i.2 musol.i.2-pp
233 162 363 210 333 190 363 238 333 280 120 90 118 100 556 280 95 74 519 170 77 450 111 446 111 450 111 448 111 450 148 125 128 128 128 125 138 73 173 116
10783 5190 8691 2263 7910 1965 8688 2535 7907 2917 638 427 636 523 1628 1166 759 301 18707 4020 254 8168 982 8164 982 8169 1025 8167 1025 16680 2479 387 1170 2113 3216 5198 3925 2188 3885 2468
148 93 242 146 227 132 244 163 228 190 119 90 117 100 355 193 91 47 329 93 52 450 110 446 110 450 111 448 111 450 148 110 114 122 123 102 90 32 118 78
122 115 104 125 140 69 79 133 70 47 109 42 90 90 93 93 126 84 110 116 120 123 97 59 98 72
156 175 77 83 70 63 76 88 69 76 1 0 1 1 97 77 5 60 287 165 30 0 1 0 1 0 0 0 0 0 0 15 26 7 7 49 55 250 52 75
103 95 79 103 107 69 95 79 161 98 67 23 77 29 89 89 93 93 126 74 100 113 118 116 89 52 80 59
24
4. P OROVNÁNÍ PARAMETR U˚ NA ZADANÝCH GRAFECH musol.i.3 musol.i.3-pp musol.i.4 musol.i.4-pp musol.i.5 musol.i.5-pp myciel2 myciel3 myciel4 myciel5 myciel6 myciel7 queen5_5 queen6_6 queen7_7 queen8_8 queen9_9 queen10_10 queen11_11 queen12_12 queen13_13
174 117 175 118 176 119 5 11 23 47 95 191 25 36 49 64 81 100 121 144 169
3916 2499 3946 2529 3973 2556 5 20 71 236 755 2360 160 290 476 728 1056 1470 1980 2596 3328
120 80 120 80 121 81 5 11 23 47 95 191 25 36 49 64 81 100 121 144 169
98 72 99 73 98 72 3 6 12 24 48 96 20 30 42 56 72 90 110 132 156
48 71 50 73 48 71 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
82 61 81 60 81 60 3 6 12 24 48 96 20 30 42 56 72 90 110 132 156
4.2 Srovnání parametru˚ Z pˇrehledu parametru˚ grafu˚ uvedených v tabulce je vidˇet že hodnota minimálního twin-cover je pro naprostou vˇetšina grafu˚ nižší než poˇcet tˇríd ekvivalence neighborhood diversity. Ve vˇetšinˇe pˇrípadu˚ má stejnou vlastnost také velikost minimálního vrcholového pokrytí. Z tohoto srovnání na první pohled vychází neighborhood diversity jako nejhorší ze zkoumaných parametru. ˚ Nesmíme ovšem zapomenout, že tento parametr nelze pˇrímo porovnávat s dalšími dvˇema, nebot’ fpt-algoritmy, které tento využívají jsou odlišné od tˇech, které využívají velikost twin-cover a vrcholového pokrytí. Funkce použité na parametr tak mohou být naprosto rozdílné, což zmˇení cˇ asovou složitost algoritmu. Srovnání velikosti vrcholového pokrytí a twin-cover žádné pˇrekvapení nepˇrineslo. Ve vetšinˇe pˇrípadu˚ je hodnota twin-cover nižší. U tˇechto dvou parametru˚ je již jejich pˇrímé srovnání možné. Pokud tedy lze v dané situaci použít twin-cover, toto bude ve vˇetšinˇe pˇrípadu˚ výhodnˇejší. Navíc díky tomu, že twin-cover se poˇcítá na grafu, ze kterého mohou být odebrány hrany, je jeho výpoˇcet ve vˇetšinˇe pˇrípadu˚ rychlejší. 25
4. P OROVNÁNÍ PARAMETR U˚ NA ZADANÝCH GRAFECH Na grafech miles, kde ve verzi s vyšším cˇ íslem jsou pˇridány hrany do grafu verze pˇredchozí, lze vidˇet, že pˇridáním hran do grafu se vylepšuje pomˇer mezi neighborhood diversity a dalšími dvˇema parametry ve prospˇech neighborhood diversity. Z toho by šlo usuzovat, že u grafu, ˚ které mají vyšší hustotu je použití neighborhood diversity jako parametru výhodnˇejší. Žádná podobná skupina grafu˚ však ve zkoumané množinˇe není, a tak nelze zjistit, zda je toto pozorování relevantní. Pokud se zamˇerˇ íme na grafy s pˇribližnˇe stejným poˇctem vrcholu, ˚ lze vidˇet, že cˇ ím více mají tyto hran, tím lépe se jeví neighborhood diversity v porovnání s vrcholovým pokrytím. Toto pozorování lze podložit i tím, že zatímco minimální vrcholové pokrytí musí s rostoucím poˇctem hran grafu rust ˚ nebo zustat ˚ stejné, neighborhood diversity muže ˚ za této situace i klesat. Tuto nevýhodu vrcholového pokrytí dokáže kompenzovat twin-cover, které muže ˚ s rostoucím poˇctem hran také klesat. Mohou totiž vzniknout kliky, ve kterých mají všechny cˇ lenské vrcholy stejné sousedy mimo tuto kliku. Odstranˇením hran mezi vrcholy této kliky tak muže ˚ hodnota twin-cover klesnout. O tom, který parametr má být v konkrétní situaci použit, je tedy tˇreba rozhodnout s pˇrihlédnutím ke konkrétnímu grafu a rˇ ešenému problému. Je tˇreba vzít v úvahu, zda je znám fpt-algoritmus využívající konkrétní parametr pro daný problém. Také je tˇreba pˇrihlédnout k tomu, jakou funkci tento algoritmus na parametr aplikuje.
26
Závˇer Výsledkem práce jsou algoritmy poˇcítající minimální vrcholové pokrytí, poˇcet tˇríd ekvivalence neighborhood diversity a minimální twin cover grafu. Poslední dva jmenované pracují dostateˇcnˇe rychle, aby je bylo možné použít i na vˇetších grafech. Byl také vytvoˇren program který vrátí tyto parametry pro daný graf. Ten muže ˚ být využit k urˇcení vhodného fpt-algoritmu, který má být použit k rˇ ešení problému˚ na tomto grafu. Pˇri porovnání zkoumaných parametru˚ na zadaných grafech bylo zjištˇeno, že nejnižší je zpravisla hodnota minimálního twin-cover, následována velikostí nejmenšího vrcholového pokrytí a nejvˇetší je pak poˇcet tˇríd ekvivalence neighborhod diversity. V urˇcitých pˇrípadech se pak postavení neighborhood diversity zlepšuje, pravdˇepodobnˇe s rostoucí hustotou grafu. Program umí naˇcítat grafy pouze ze vstupu formátovaného jedním konkrétním zpu˚ sobem, bylo by ho tedy možné rozšíˇrit o možnost naˇcítání grafu˚ reprezentovaných jiným zpusobem. ˚ Také by mohla být pˇridána možnost uložení grafu do souboru, toho by bylo možné využít pˇredevším pokud pracujeceme s indukovaným podgrafem. Program zatím neposkytuje zpusob ˚ jak tento uložit. Pˇri tvorbˇe podgrafu by také mohlo být možné urˇcit vrchol, ze kterého se bude tento vytváˇret. Do budoucna by bylo jistˇe zajímavé zjistit, na jakých konkrétních charakteristikách závisí pomˇer mezi zkoumanými parametry, pˇredevším pak mezi twin-cover a neighborhood diversity.
27
Použité zdroje [1] DIESTEL, R. Graph Theory. Berlin: Springer, 2006. [2] FLUM, J., GROHE, M. Parameterized Complexity Theory. Berlin: Springer, 2006. [3] CESATI, M. Compendium of Parameterized Problems[online]. Roma, 2006 [cit. 15. kvˇetna 2012]. Dostupné na:. [4] LAMPIS, M. Fixed-Parameter Algorithms and Parameterized Complexity[online]. 2009 [cit. 15. kvˇetna 2012]. Dostupné na:. [5] NIEDERMEIER, R. Invitation to Fixed-Parameter Algorithms[online]. 2002 [cit. 15. kvˇetna 2012]. Habilitaˇcní práce. Universität Tübingen. Dostupné na: . [6] FELLOWS, M. R. Blow-Ups, Win/Win’s, and Crown Rules: Some New Directions in FPT [online]. Newcastle, [cit. 15. kvˇetna 2012]. Dostupné na: . [7] GAREY, M. R., JOHNSON, D. G. COMPUTERS AND INTRACTABILITY A Guide to the Theory of NP-Completeness[online]. New York : W.H. Freeman and Company, 1997 [cit. 10. kvˇetna 2012]. Dostupné na:
