Listing graphs that satisfy first-order sentences

摘要

The main result of this paper is a method that turns any almost-sure sentence in the first-order language of graphs into a deterministic polynomial space polynomial delay algorithm for listing the graphs that satisfy the sentence. (Our result is the first such method.) Our work builds upon earlier work of Fagin. In particular, Fagin defined an infinite collection of combinatorial axioms and showed that for any fixed integer k almost every graph satisfies the kth axiom in his collection. Suppose that ϑ is a sentence in the first-order language of graphs. (For example, ϑ might say “This graph does not have a triangle,” or “Every connected component of this graph is a clique.”) Fagin has shown that for each such ϑ there is an integer k such that either (1) Every graph that satisfies the kth axiom in his collection satisfies ϑ (in which case ϑ is an “almost-sure” sentence), or (2) Every graph that satisfies the kth axiom in his collection satisfiesϑ (henceϑ is an “almost-sure” sentence). If ϑ is an almost-sure sentence then Raghavan's method of pessimstic estimators can be used to construct an example of an n-vertex graph that satisfies ϑ (for every large enough integer n). However, the method of pessimistic estimators does not give us enough information to actually list all of the n-vertex graphs that satisfy ϑ. Prior to this work it was unknown whether or not every almost-sure first-order sentence could be associated with a polynomial delay algorithm for listing the graphs that satisfy the sentence. We show that this is the case and that, in fact, a single method can be used for every almost-sure first-order sentence. Furthermore, polynomial space can be achieved simultaneously with polynomial delay. We describe our method in the context of listing families of graphs that are defined by first-order sentences. However, our method can also be used to obtain polynomial space polynomial delay listing algorithms for certain other families of graphs—for example, the family of connected graphs. More generally our method can be viewed as an extension of the method of pessimistic estimators and as a general technique for using probabilistic arguments to produce deterministic polynomial space polynomial delay listing algorithms. We expect the method to be useful for listing a variety of combinatorial structures.