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

• Thesis title in Czech: Obtížné problémy vzhledem k parametru různorodost sousedství
• Thesis title in English: Hard problems on Neighborhood Diversity
• Key words: Parametrizovaná složitost, husté grafy, různorodost sousedství
• English key words: Parameterized complexity, dense graphs, neighborhood diversity
• Academic year of topic announcement: 2012/2013
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: doc. Mgr. Petr Kolman, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 21.03.2013
• Date of assignment: 21.03.2013
• Confirmed by Study dept. on: 25.03.2013
• Date and time of defence: 29.05.2013 00:00
• Date of electronic submission: 12.04.2013
• Date of submission of printed version: 12.04.2013
• Date of proceeded defence: 29.05.2013
• Opponents: doc. RNDr. Jiří Fiala, Ph.D.

Guidelines

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.

References

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)