Structural graph theory, computational complexity and parameterized algorithmics
Many practical algorithmic tasks have a core based on discrete structures such as graphs, digraphs, strings, or matroids. Hence it is not surprising that efficient solutions of these tasks require deep knowledge of the underlying theory of discrete mathematics. For instance, the following interesting practical problems have nice solutions provided by discrete mathematics:
- Finding a shortest path in a graph (used e.g. in car GPS navigations) is solved not only using Dijkstra's algorithm or its A* modification, but applies many new concepts such as those of reach or contraction hierarchies.
- Network flows give nice solutions to practical transportation and connectivity problems, and have other rather unexpected applications as well, such as in image segmentation.
- Finding a shortest superstring of a collection of strings is another problem with important real-life applications (e.g. in DNA sequencing and compression). Algorithms for the problem use interesting results from graph theory.
- Various problems in combinatorial optimization, such as the minimum spanning tree or maximum matching problems, are solved by mathematically very elegant algorithms, too.
Our young and growing group follows the newest trends and focuses on using popular structural approaches in discrete mathematics / graph theory and in their algorithmic applications. Our aim is to contribute new findings both on the theory side and in computing applications.
Information for students
For interested students (already since the bachelor level), our research group can offer
- an opportunity to join scientific research on a top international level (with publications in some of the leading scientific journals in discrete mathematics and theoretical CS), and to have a perspective of continuing study up to the Ph.D. level and starting an academic career afterwards,
and at the same time possibilities
- to work on specifics practically oriented projects applying graphs and discrete mathematics in computer science.
More detailed information can be obtained from the individual team members, or the interested students may directly get involved
- while solving bonus assignments in the standard courses IB000 and MA010,
- in the "young" Seminar on Discrete Mathematical Methods - IV119,
- in the seminar groups on advanced graph theory and on parameterized algorithmics within the Formela Lab seminar course - IV125.
Interested senior students are also encouraged to participate in the FMDSA: Working Seminar on Formal Methods, Discrete Structures, and Algorithms.
Sample research objectives
(Besides this rather brief list, interested students are encouraged to consult this detailed research page, the Formela Lab pages at FI, and personal pages of other team members below...)
- Width and depth parameters (of graphs)
In this area we study traditional as well as some new parameters describing the "width/depth" of combinatorial objects (in the sense of complexity, how much they "resemble" trivial input structures such as trees and stars) -- tree-width, branch-width, rank-width, DAG-width, and DAG-depth, shrub-depth, to mention just a few. The desired outcome is that on input objects of low width/depth, many otherwise hard algorithmic problems become tractable, as for instance various MSO-definable properties. The question of how to obtain such low width/degree/depth decompositions is also studied. - Logic (MSO/FO) in parameterized algorithms
This follows on the previous topic, focusing on ways of expressing algorithmic problems in logical language (of variuous power) in order to provide meta-algorithms efficiently solving all problems with such expressions on restricted classes of graphs. - Graph crossing number
The research direction copes with the problem to draw a graph with the least possible number of edge crossings, which appears to be an unusually difficult algorithmic task. Our primary interest is in finding good efficient approximations of the crossing number (some of which are even practically implementable, a quite rare case in this area). Besides that we deal with theoretical research of crossing-critical graphs, and with computational hardness questions of this problem. - Geometric and topological graphs
This topic includes some additional "small" research objectives, among which we mention the following two: First, a long term study of the planar cover and planar emulator problems (cf. Negami's planar cover conjecture). Second, an interest in applying some structural graph ideas to provide yet new concepts and algorithms for the practical route planning problem (e.g., for GPS navigation).
Team members
(as of Spring 2015)
Team head:
Petr Hliněný
Staff:
Jan Obdržálek
Sebastian Ordyniak (postdoc)
Michal Kotrbčík (postdoc)
PhD students:
Ondrej Moriš, Jakub Gajarský, Marek Derňár
Selected former students:
Robert Ganian (now at TU Wien), Martin Derka (now studying at Univ. Waterloo), Matěj Klusáček
Current research projects
(as of 2015)
- Parameterized algorithms and kernelization in the context of discrete mathematics and logic.
Grant project GAČR 14-03501S, 2014-2016.
- Institute for Theoretical Computer Science (CE-ITI).
Center of Excellence, GAČR P202/12/G061, 2012-2018.
- Graph Drawings and Representations GraDR.
Part of the EuroGIGA Programme (EUROCORES), 2011-2014.
Contact
Responsible contact: prof. RNDr. Petr Hliněný, Ph.D.