Main Research Interests

  • Cops and Robber games and digraph decompositions

    This is the topic of my diploma and PhD thesis. The general idea is to utilise the dynamic and intuitive characterisations of tree decompositions of graphs via Cops and Robber games. The decompositions of moderate "width" can be often be used to support efficient algorithms for problems that are intractable otherwise.

    On undirected graphs, the notions are well studied, especially treewidth. For more general and more difficult to explore digraphs, the situation is more complex and there exist several concurring notions of games and decompositions: DAG-width, Kelly-width, directed treewidth etc. In my work, I proved or disproved some previously known conjectures and gave an almost complete picture of the relations between relevant notions.

    In (Amiri et al. 2016) (see here for a preprint) we prove the inherent difficulty of the conceptually promising DAG-width, a quite unexpected result. The construction is based on a deep understanding of the decompositions that we developed in (Amiri et al. 2015). Here, we also give an almost complete picture of the widths, filling several gaps in knowledge. In (Puchala and Rabinovich 2016) (preprint) we highlight the inherent difficulty of digraphs in general by giving a technically demanding proof of our result. It overcomes many problems which are trivially solvable for undirected graphs.

  • Structural and algorithmic properties of sparse structures

    Since 2015 my second basic topic. This is a rapidly emerging and thus promising research area with a lot of publications and thus much competition. Here, many well-known notions for classes of sparse graphs as planar graphs or graphs of bounded degree of treewidth are generalised and the limits are studied at which those generalisations still let one utilise the sparseness.

    An appealing property of such graph classes is that they can be characterised in many ways by means of boundedness of parameters coming from different areas of research. In (Heuvel et al. 2015) and in (Kreutzer et al. 2016), which is currently submitted for publication, we provide new upper bounds for several such parameters for important subclasses (for planar graphs and classes defined by excluded minors).

  • Efficient algorithms

    This topic has a tight connection to the previous one. The goal is to implement algorithms that are efficient in theory in a possibly efficient way to discover the limits of their practical applicability. In particular, implementations that are efficient for important special cases of otherwise impractical algorithms are of great interest. An significant part of the work is here the supervision of student's thesis.