Research Interests

Graph Minors

The theory of graph minors is arguably one of the deepest fields in graph theory. In particular, the graph minors series of Robertson and Seymour has created an extreme growth in the development of graph theory as a whole. It has found both algorithmic and structural applications and revealed a deep link between the theory of graph minors and topology.

Topics I am interested in include

width measures like treewidth which are related to graph minors
parameterized algorithms exploiting the structure of minor-closed graph classes
refinements of the Robertson & Seymour structure theory, and
universal obstructions and extensions of WQO (see Paul, Protopapas, Thilikos 2023 for a survey)

Beyond Graph Minors: Graph containment relations

Apart from minors many other containment relations for graphs (and similar structures) exhibit similar properties and behaviours. An underlying theme of my research is to develop an understading for using these similarities to provide a unified approach towards building structural theories for these relations.

Examples for such containment relations are:

Matching Minors

Matching minors are a tool for the structural study of graphs with perfect matchings.

Interesting open problems are:

perfect matching width and a grid theorem for non-bipartite matching covered graphs
counting perfect matchings and computing the permanent in (bipartite) matching covered graphs excluding some matching minor
characterising and recognising non-bipartite graphs that admit pfaffian orientations

Minors in group labelled graphs

Minors preserving the parities of cycles (so called odd minors) or, more generally, minors of graphs whose edges are labelled with the elements of some group make for a challenging generalisation of the concept of minors. In particular, graphs excluding some odd-minor usually exhibit interesting algorithmic properties.

Interesting open problems are:

does every graph have the half-integral Erdős-Pósa property for odd minors?
for which odd-minor closed graph classes is the maximum Independent Set Problem tractible?
find characterisations for interesting odd-minor free classes

Directed Minors

For digraphs, the most popular concept for minors are the so called 'butterfly minors' but other concepts have also received attention. The biggest challenge in the study of directed minors is to find appropriate generalisations of the tools for structural minor theory. This is, in particular, because there is no hope to find a directed version of the so called ``Two Paths Theorem''.

Interesting open problems are:

find a good substitute for the Two-Paths Theorem in the setting of butterfly minors
in which butterfly-minor-closed classes is the directed linkage problem tractible?