Original title:
Výpočetní složitost v teorii grafů
Translated title:
Computational complexity in graph theory
Authors:
Melka, Jakub ; Kratochvíl, Jan (advisor) ; Fiala, Jiří (referee) Document type: Master’s theses
Year:
2011
Language:
cze Abstract:
[cze][eng] V předložené práci studujeme problém rekonstrukce grafu ze seznamu uzavřených okolí vrcholů tohoto grafu. Tento problém, původně zformulovaný V. Sósovou, budeme zkoumat z hlediska teorie parametrizované složitosti a zobecníme jej na problém rekonstruovatelnosti vzhledem ke třídám grafů. V této práci dokážeme, že tento problém leží ve třídě složitosti FPT vzhledem k parametru omezené stromové šířky a omezeného maximálního stupně nebo ke 2-degenerovaných grafům s omezeným počtem jistých indukovaných podgrafů, kde parametr je počet těchto podgrafů. Dále dokážeme, že problém rekonstruovatelnosti vzhledem ke třídě grafů s omezeným vrcholovým pokrytím leží ve třídě složitosti XP. Na závěr dokážeme vzájemnou nezávislost získaných výsledků.In the present work we study the problem of reconstructing a graph from its closed neighbourhood list. We will explore this problem, formulated by V. Sós, from the point of view of the fixed parameter complexity. We study the graph reconstruction problem in a more general setting, when the reconstructed graph is required to belong to some special graph class. In the present work we prove that this general problem lies in the complexity class FPT, when parametrized by the treewidth and maximum degree of the reconstructed graph, or by the number of certain special induced subgraphs if the reconstructed graph is 2-degenerate. Also, we prove that the graph reconstruction problem lies in the complexity class XP when parametrized by the vertex cover number. Finally, we prove mutual independence of the results
Keywords:
Fixed parameter complexity; graph reconstruction; hypergraph; star systems; treewidth; hvezdné systémy; hypergraf; parametrizovaná složitost; rekonstrukce grafu; stromová šírka
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/35421