Polynomial-time computation of poset dimension from a linear extension graph

About 13 years old · traced to

Let PP be a poset and let GL(P)G_L(P) be its linear extension graph, whose vertices are the linear extensions of PP. The dimension dim⁡(P)\dim(P) is the minimum size of a realizer of PP, that is, a set of linear extensions whose intersection is PP.

Polynomial-time dimension conjecture. The dimension of a poset given its linear extension graph can be determined in polynomial time.

The proposition preceding this conjecture gives a quasi-polynomial-time algorithm, while the conjecture asks whether this can be improved to polynomial time. This would match the expected complexity suggested by the exponential size of a linear extension graph relative to the underlying poset.

References

Primary source

Marie Albenque and Kolja Knauer, “Convexity in partial cubes: the hull number”, arXiv:1309.5724 (2015).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.