Technical Report 295-1991

Title

On the Complexity of Partial Order Properties

Authors

Stefan Felsner and Dorothea Wagner

Publication

Lecture Notes in Computer Science 657, Proc. of 18th Workshop on Graph-Theoretic Concepts in Computer Science 92 (WG`92), ed. Ernst Mayr, 1992, pp. 225-235

Source

Download as [ps.gz]

Classification

not available

Keywords

not available

Abstract

The recognition complexity of ordered set properties is considered, i.e. how many questions have to be asked to decide if an unknown ordered set has a prescribed property. We prove a lower bound of Ω(n²) for properties that are characterized by forbidden substructures of fixed size. For the properties being connected, and having exactly k comparable pairs we s how that the recognition complexity is n choose 2; the complexity of interval orders is exactly nchoose 2 -1. Non-trivial upper bounds are given for being a lattice, containing a chain of length k geq 3 and having width k.