Polynomial space polynomial delay algorithms for listing families of graphs.

摘要

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.