Title: Computing Excluded Minors

Abstract:

One of the most stunning results in recent mathematics is Robertson
and Seymour's proof of the graph minor theorem saying that every class
of graphs closed under taking minors can be characterised by a finite
family of excluded minors. Besides its enormous impact on graph
structure theory, this result also has interesting implications for
computation. Combined with a cubic time algorithm for testing if a
fixed graph H is a minor of another graph G, also proved as part of
the graph minor series, it implies that every minor closed class of
graphs can be decided in polynomial time. A well known example is the
class of knotlessly embeddable graphs, which is minor closed and hence
decidable in cubic time.

However, the proof of the graph minor theorem is non-constructive in
the sense that the existence of a finite set of minimal excluded
minors is proved, but no way to compute these is given. And in fact,
no such method can exist, as in general computing the set of minimal
excluded minors is undecidable. In particular, while it follows from
the graph minor theorem that it is decidable in cubic time whether a
graph is knotlessly embeddable, no such algorithm is known to date,
not even an algorithm with any (finite) running time.

On the other hand, for many natural minor closed classes of graphs,
the set of excluded minors has been shown to be computable or is even
known. In this talk, we study algorithms for computing excluded minor
characterisations of minor closed classes. We propose a general method
for obtaining such algorithms, which is based on definability in
monadic second-order logic and the decidability of the monadic
second-order theory of trees.

In this talk, tailored towards an audience with a background in logic
rather than graph theory, I will first give a brief introduction to
the theory of graph minors and the problem of computing minor
characterisations, followed by the logical aspects of a method to
compute excluded minors.

A straightforward application of our method yields algorithms that,
for a given k, compute excluded minor characterisations for the class
T_k of all graphs of tree width at most k and similar minor closed
classes. Our main results are concerned with constructions of new
minor ideals from given ones. Answering a question that goes back to
Fellows and Langston, we prove that there is an algorithm that, given
excluded minor characterisations of two minor closed classes C and D,
computes such a characterisation for the class C \cup D (this is also
known as the intertwine problem). We will also briefly discuss other
application, e.g. the class of apex graphs.

===================================================================