My Research

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,
universal obstructions and extensions of WQO (see Paul, Protopapas, Thilikos 2023 for a survey), and
Handwiger's Conjecture and related structural properties of graphs excluding a clique minor

Beyond Graph Minors: (Graph) Containment relations and limits of tractability

A general theme in the theory of computational complexity is the search for the fine line between tractability and NP-hardness. On an abstract level, one may ask, given a fixed problem P, can we understand which subclasses of the class of all instances of P admit algorithms for solving P in polynomial time.

An effective way to approach this general question is through the use of structural methods. One well-established way to impose a notion of structure is to ask for a relation (typically a quasi order, say <) on the class of all instances of P. We may now call a class C of instances of P <-closed if for all instances J < I of P, membership of I in C implies that also J belongs to C. We may now rephrase the above question as follows:

What are the <-closed classes of instances where P can be solved in polynomial time?

A classic example for a complete answer to this question is given by the Maximum Independent Set (MIS) problem which is known to be NP-complete even on planar graphs. Instances of MIS are graphs and the minor-relation is a well-studied quasi order on graphs. Moreover, planar graphs are closed under graph minors. The celebrated Grid Theorem of Robertson and Seymour says that a minor-closed graph class C has bounded treewidth if and only if C does not contain all planar graphs.
Combining both results above yields that unless P=NP, MIS can be solved in polynomial time on a minor-closed class C of graphs if and only if C does not contain all planar graphs.
This is a very satisfying answer to our general question above. Not only does it fully delineate the tractability of MIS within the world of graph minors, it identifies a specific class of "essential" hard instances of MIS and shows that precisely the full presence of this class - namely the planar graphs - is what forces NP-hardness. It also highlights the crucial role played by structural methods as it is really the fact that graphs excluding a fixed planar graph as a minor admit a tree-like description whose exploitation facilitates the design of algorithms for otherwise hard problems.

How to get there: The structure of exclusion

The theory of graph minors by Robertson and Seymour provides a powerful template to approach the general strategy given above. Generally, it would be beneficial to understand the structure of the class C of all instances that exclude a fixed instance J with respect to the containment relation <. Those are called the J-free instances.
From the work of Robertson and Seymour, one may extract the following abstract steps:

i) Identify a fundamental of way decomposing instances into smaller once along interfaces of "low complexity" (in the setting of Graph Minors, these are separations of small order).

ii) Define a parameter p defined on the class of all instances that capture those instances which can be decomposed along interfaces of "low complexity" into pieces of "low complexity" (for Graph Minors, this parameter is treewidth and pieces of "low complexity" are simply small vertex sets).

iii) Identify a small - hopefully finite - number of "patterns" that obstruct p and show that in any instance where p is large, at least one of those patterns must emerge (for Graph Minors, the role of this step is played by the so-called Grid Theorem).

iv) Prove that, in the absence of a fixed instance J with respect to <, if one of the patterns Q from iii) emerges in an instance I, then "locally", the instance I behaves precisely like Q (in Graph Minors, this is the so-called "Flat Wall Theorem").

v) The next step could possibly be broken down into further steps, but for the purpose of this brief overview let us observe it in a more abstract way. We now want to show that the structure from iv) can be extended further. That is, in the absence of J, any "local" part of I where some pattern from Q emerges, induces a part X of I such that the entirety of X behaves like Q and can be separated from the rest of I by means of low order separations (in the setting of Graph Minors, this is known as the Graph Minor Structure Theorem).

vi) Finally, the remaining step is what has become known as a lift from "local to global" structure. This is where often concepts such as the general idea of tangles become important to show that every instance I can be decomposed along small order separations into pieces that are either trivial or whose structure follows the rules established in v).