Home
 

Listing Graphs that Satisfy First Order Sentences

Leslie Ann Goldberg

Abstract: For every sentence Theta in the first order language of graphs let G_{Theta}(\) denote the set of n-vertex graphs that satisfy Theta and let G_{Theta} denote the family of sets {G_{Theta}(\infty),G_{Theta}(\null),...}. In this work, we consider the following problem. Given a sentence Theta in the first order language of graphs, design a fast algorithm that takes as input a positive integer n and lists the members of G_{Theta}(\). The criterion for ``fast'' that we use is polynomial delay. We say that a listing algorithm for G_{Theta} has polynomial delay if and only if there is a polynomial such that when the algorithm is run with any input n it executes at most p(n) machine instructions before each successive member of G_{Theta}(\) is output. The results that we obtain are related to a theorem which was proved independently by Glebskii, Kogan, Liogon'kii, and Talanov and by Fagin. They showed that for every sentence Theta in the first order language of graphs the proportion of n-vertex graphs that satisfy Theta is either o(1) or 1 - o(1). In the latter case we call G_{Theta} an almost sure first order graph property. In this paper we describe a general method that can be used to obtain a polynomial delay listing algorithm for any almost sure first order graph property.

LFCS report ECS-LFCS-92-210

Previous | Index | Next