Obtížné problémy vzhledem k parametru různorodost sousedství

• Název práce v češtině: Obtížné problémy vzhledem k parametru různorodost sousedství
• Název v anglickém jazyce: Hard problems on Neighborhood Diversity
• Klíčová slova: Parametrizovaná složitost, husté grafy, různorodost sousedství
• Klíčová slova anglicky: Parameterized complexity, dense graphs, neighborhood diversity
• Akademický rok vypsání: 2012/2013
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: doc. Mgr. Petr Kolman, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 21.03.2013
• Datum zadání: 21.03.2013
• Datum potvrzení stud. oddělením: 25.03.2013
• Datum a čas obhajoby: 29.05.2013 00:00
• Datum odevzdání elektronické podoby: 12.04.2013
• Datum odevzdání tištěné podoby: 12.04.2013
• Datum proběhlé obhajoby: 29.05.2013
• Oponenti: doc. RNDr. Jiří Fiala, Ph.D.

Zásady pro vypracování

Tématem této práce je složitost některých těžkých grafových problémů parametrizovaných pomocí "různorodosti sousedství" (neighborhood diversity), nedávno zavedeným
strukturálním grafovým parametrem, a případně i dalšími příbuznými parametry. Diplomant vypracuje přehled zajímavých problémů a výsledků
(např. problémy, které jsou těžké, je-li parametrem stromová šířka, či které spadají mezi nepříliš prozkoumané vzhledem ke zmíněným novým
parametrům), parametry (jako je "různorodost sousedství", konečný typ atd.) a užitečné techniky (např. Lenstrův algoritmus pro celočíselné lineární
programování v pevné dimenzi). Diplomant se následně pokusí některé otevřené problémy vyřešit.

The topic of this thesis is the complexity of some hard problems on graphs
when parametrized by neighborhood diversity, a recently introduced graph
parameter capturing some structural graph properties, and possibly by other
related parameters. The student will survey relevant interesting problems
and results (e.g., problems that are hard when parametrized by treewidth or
which fall into a cathegory not investigated yet with regards to the new
parameters), parameters (such as neighborhood diversity, finite type etc.)
and useful techniques (e.g., Lenstra's integer linear programming algorithm
in fixed dimension). The student will then try to tackle some of the open
problems.

Seznam odborné literatury

Downey, Rod G.; Fellows, Michael R. (1999). Parameterized Complexity.
Springer. ISBN 0-387-94883-X.
Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory.
Springer. ISBN 978-3-540-29952-3.

Odborný článek:
Michael Lampis: Algorithmic Meta-theorems for Restrictions of Treewidth.
ESA (1) 2010: 549-560
Robert Ganian: Using Neighborhood Diversity to Solve Hard Problems. CoRR
abs/1201.3091 (2012)