Contemporary Mathematics

Volume 89, 1989

THE ROBERTSON-SEYMOUR THEOREMS:

A SURVEY OF APPLICATIONS

Michael R. Fellows

Abstract

Applications of the Robertson-Seymour theorems to a variety of

problems in concrete computational complexity are surveyed. These results

suggest a broad program o:f research in computational complexity based on

partial orders of combinatorial objects defined by sequences of local opera-

tions. It is shown that the 2-induced connecting paths problem, relevant to

the problem of

order-testin1~

in the strong minor order, is NP-complete. Ap-

proaches to practical algorithms achieving the Robertson-Seymour complexity

bounds are described.

1. Introduction

It is almost

100

years since Hilbert's now famous, and then controversial, nonconstruc-

tive solution to Gordon's Problem of Invariants. Hilbert proved the following finite basis

theorem.

Theorem

(Hilbert) Any set of forms in

L

finite number of variables over Q(a) has a finite basis.

D

According to a recent historkal account by Beeson [Be] Hilbert corresponded with

Cayley for over a month to convince him that he had actually solved the problem. The

nonconstructive nature of HilberiG's argument elicited from Gordon the famous reaction

[Re],

"This is not Mathematics, this is Theology!"

Hilbert's proof was controversial because until that time mathematical argument had

been almost entirely computational in nature (and therefore constructive). He had proved

that a finite basis must exist, without giving any information on how to compute it, and

this ran against the grain of mathematical intuition in that day. The controversy led

©

1989 American Mathematical Society

0271-4132/89 $1.00

+

$.25 per page

http://dx.doi.org/10.1090/conm/089/1006472