Bounded combinatorial width and forbidden substructures
Michael R. Fellows, Michael J. Dinneen · 1996
A substantial part of the history of graph theory deals with the study and classification of sets of graphs that share common properties. One predominant trend is to characterize graph families by sets of minimal forbidden graphs (within some partial ordering on the graphs). For example, the famous Kuratowski Theorem classifies the planar graph family by two forbidden graphs (in the topological partial order). Most, if not all, of the current approaches for finding these forbidden substructure characterizations use extensive and specialized case analysis. Thus, until now, for a fixed graph family, this type of mathematical theorem proving often required months or even years of human effort. The main focus of this dissertation is to develop a practical theory for automating (with distributed computer programming) this classic part of graph theory. We extend and (more importantly) implement a variation of the seminal work done by Fellows and Langston regarding computing finite-basis characterizations. The recently celebrated Robertson-Seymour Graph Minor Theorem establishes that many natural graph families are characterizable by a finite set of graphs. In particular, if a graph family is closed under the three basic minor operations (i.e., isolated vertex deletions, edge deletions, and edge contractions) then there exists (by a nonconstructive argument) a finite set of forbidden graphs. Two examples are the well-known k-V scERTEX C scOVER and k-F scEEDBACK V scERTEX S scET graph families. In this dissertation, we characterize, for the first time, these parameterized families, among others, for small k. Our forbidden graph computations use a restricted search space consisting of graphs of bounded combinatorial width (where pathwidth and treewidth are two important metrics). Using an algebraic enumeration scheme for graphs, we have implemented a terminating algorithm that will find all minor-order forbidden graphs for each fixed pathwidth. For a targeted graph family, this algorithm requires a mathematical description given in one of many acceptable forms (or combinations thereof), such as a finite-index congruence or a set of automaton-generating tests. Our main assumption is that an upper bound on the pathwidth (or treewidth) of the largest forbidden graph of a particular graph family is more readily available than its order (or size). A byproduct of our bounded width approach is that we give practical linear time membership algorithms in the form of dynamic programs (over parsed graph structures of bounded width) for several graph families (e.g., k-M scAXIMUM P scATH L scENGTH and O scUTER P scLANAR).