Parametrizovaná složitost v teorii grafů

Abstract

Seidelovo přepnutí množiny vrcholu je operace, která z grafu odebere hrany vycházející z této množiny a přidá do něj hrany tam, kde mezi množinou a zbytkem grafu nebyly. Ostatní hrany nejsou touto operací dotčeny. Parametrizovaná složitost se ptá, zda lze exponenciální část algoritmu pro těžké problémy omezit nějakou funkcí pouze zvoleného parametru, u nejž lze očekávat malé hodnoty. Tato práce zkoumá složitost otázek, zda lze zadaný graf převést na graf s nějakou vlastností P pomocí Seidelova přepnutí, z parametrizovaného hlediska. Nejdříve krátce shrneme dosud známé výsledky. Pak předvedeme parametrizovanou dostupnost přepnutí na regulární grafy, grafy s omezeným stupněm vrcholu, s omezeným počtem hran a grafy prosté zakázaného podgrafu. Krátce podáme základní definice a postupy parametrizované složitosti.

Seidel's switching of a set of vertices of a graph is an operation which deletes the edges leaving this set from the graph and adds those edges between the set and the rest of graph that weren't in the original graph. Other edges remain untouched by this operation. Parameterized complexity asks if the exponential part of algorithms for hard problems can be bounded by some function only of selected parameters, which we assume small. In this thesis, we study the complexity of a question if the given graph can be turned into a graph with some property P using Seidel's switching, from the parameterized point of view. First we give an overview of known results. Then we show fixed-parameter tractability of switching to a regular graph, a graph with bounded degree of vertices, bounded number of edges and a graph without a forbidden subgraph. We briefly introduce basic definitions and techniques of parameterized complexity.