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
Previous Page Next Page