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

  • 1
    $\begingroup$ a related question: suppose the lattice is not presented explicitly, but via (say) a neighborhood oracle (in and out) $\endgroup$ – Suresh Venkat May 23 '11 at 7:02

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).


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.