Dedekind–MacNeille completion

Then (↓x)u is the set of elements greater than or equal to x, and ((↓x)u)l = ↓x, showing that ↓x is indeed a member of the completion.

[19] In the category of partially ordered sets and monotonic functions between partially ordered sets, the complete lattices form the injective objects for order-embeddings, and the Dedekind–MacNeille completion of S is the injective hull of S.[20] Several researchers have investigated algorithms for constructing the Dedekind–MacNeille completion of a finite partially ordered set.

The Dedekind–MacNeille completion may be exponentially larger than the partial order it comes from,[12] and the time bounds for such algorithms are generally stated in an output-sensitive way, depending both on the number n of elements of the input partial order, and on the number c of elements of its completion.

The time for using their method to add a single element to the completion of a partial order is O(cnw) where w is the width of the partial order, that is, the size of its largest antichain.

[12] As Jourdan, Rampon & Jard (1994) observe, the problem of listing all cuts in a partially ordered set can be formulated as a special case of a simpler problem, of listing all maximal antichains in a different partially ordered set.

Jourdan et al. describe an algorithm for finding maximal antichains that, when applied to the problem of listing all cuts in P, takes time O(c(nw + w3)), an improvement on the algorithm of Ganter & Kuznetsov (1998) when the width w is small.

[21] Alternatively, a maximal antichain in Q is the same as a maximal independent set in the comparability graph of Q, or a maximal clique in the complement of the comparability graph, so algorithms for the clique problem or the independent set problem can also be applied to this version of the Dedekind–MacNeille completion problem.

[22] The transitive reduction or covering graph of the Dedekind–MacNeille completion describes the order relation between its elements in a concise way: each neighbor of a cut must remove an element of the original partial order from either the upper or lower set of the cut, so each vertex has at most n neighbors.

Thus, the covering graph has c vertices and at most cn/2 neighbors, a number that may be much smaller than the c2 entries in a matrix that specifies all pairwise comparisons between elements.

Nourine & Raynaud (1999) show how to compute this covering graph efficiently; more generally, if B is any family of sets, they show how to compute the covering graph of the lattice of unions of subsets of B.

The main idea for their algorithm is to generate unions of subsets of B incrementally (for each set in B, forming its union with all previously generated unions), represent the resulting family of sets in a trie, and use the trie representation to test certain candidate pairs of sets for adjacency in the covering relation; it takes time O(cn2).

In later work, the same authors showed that the algorithm could be made fully incremental (capable of adding elements to the partial order one at a time) with the same total time bound.