Polynomial-time computation of poset dimension from a linear extension graph
Let be a poset and let be its linear extension graph, whose vertices are the linear extensions of . The dimension is the minimum size of a realizer of , that is, a set of linear extensions whose intersection is .
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
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.