REGULARITY AND LOCALITY IN KAPPA-TERMINAL GRAPHS

In a 1985 paper, Bern, Lawler, and Wong described a general method for constructing algorithms to find an optimal subgraph in a given graph. When the given graph is a member of a k-terminal recursive family of graphs and is presented in the form of a parse tree, and when the opti mal subgraph satisfies a property that is regular with respect to the family of graphs, then the method produces a linear-time algorithm. Th e algorithms assume the existence of multiplication tables that are sp ecific to the regular property and to the family of graphs. In this pa per we show that the general problem of computing these multiplication tables is unsolvable and provide a ''pumping'' lemma for proving that particular properties are not regular for particular k-terminal famil ies. In contrast with these negative results, we show that all local p roperties, that can be verified by examining a bounded neighbourhood o f each vertex in a graph, are regular with respect to all k-terminal r ecursive families of graphs, and we show how to automate the construct ion of the multiplication tables for any local property.