Interesting CS problem

[gchpaco]

I've come across a rather interesting CS problem during work that I thought I'd throw out there. The problem is this: given a finite lattice (L, ⊑) (our problem has a lattice that is also distributive, so you may presume that) and a node x in that lattice, efficiently compute the set S ⊆ L = { y ∈ L : x ⊏ y ∧ ∄ z x ⊏ z ⊏ y }. This is well defined, and starting from ⊥ it is possible to walk the entire lattice easily (which is why we care). If you precompute the lattice you can do this trivially. Is it possible to do so without considering every node in the lattice?

Failing that, can you give me an efficient algorithm for computing the structure of the lattice from a set L and a partial order ⊑ ?

Comments

[layah.livejournal.com]

42

[natetg.livejournal.com]

So you're looking for S_x which is the set of all the elements that are immediately larger than x. Seems like you can generate a directed acyclic graph representation of L in, at worst, order L^2.5 ish time by walking the partial lattice for each element and reconnecting the graph appropriately, I haven't thought too much, but I expect that, in practice this is usually going to be Order L log L -ish. The directed acyclic graph structure then encodes all of the L_x.

If we consider, for a moment, the possible example of a fully ordered set (which is a distributive lattice) then you're basically stuck sorting the entire set to find an immediate parent, so I don't think that there's a generic solution without considering every element in the worst case.

I was under the impression that you were generating the lattice, and making it distributive by construction. I'd be inclined to guess that you can get the L_x work done in construction.

[natetg.livejournal.com]

L_x should be S_x at the end of the first para.

[gchpaco.livejournal.com]

As it happens, there's a closely related problem in formal concept analysis concerning the Galois lattice, and there are techniques for reconstructing the Hasse diagram, which implicitly requires knowledge of the covering set, in time O(|L|); however, they are not incremental. I'm looking into alternatives but have been told to stop thinking about this and do something business related.