Lattice problems

Question

There has been a fair amount of work on computational problems for partial orders (e.g., recognition, jump number, comparability graph recognition, etc...).

I am curious what work specific to lattices has been done. I have searched around and not found much similar work for lattices.

In particular, I am interested in whether the following lattice problems have been investigated:

1. Lattice recognition: given a DAG or a partial order is it in fact a lattice?

2. Lattice comparability graph recognition: given a undirected graph G, can the edges of G be oriented such that the resulting orientation is a lattice?

3. Determining/counting the join irreducible elements of a lattice

4. Determining if a given lattice is distributed/modular

Answer 1

Re your questions (2+4): an undirected graph G is the covering graph (not the comparability graph!) of a distributed lattice iff it is a median graph and it has two vertices that are complementary (on opposite sides of each Djokovic equivalence class of edges); see Duffus, Dwight; Rival, Ivan (1983), "Graphs orientable as distributive lattices", Proc. AMS 88 (2): 197–200. This can be turned into an efficient algorithm by combining a median graph recognition algorithm (see the Wikipedia article) with an algorithm for finding complementary pairs of vertices (see theorem 3 of arxiv:cs.DS/0206033).

Answer 2

Here is a link, may be it can help you. http://fc.isima.fr/~nourine/publications.php M. Habib and L. Nourine : A Linear Time Algorithm to Recognize Distributive Lattices, RR LIRMM, No 92-012, 1992.