Edge subdivision and dimension (Q1108295)

M. Habib conjectured that the dimension problem for the so-called \(N\)-free partial orders could be solved in polynomial time. Kierstead asked whether the conversion of a partial order by edge subdivision can multiply the dimension by more than a constant; if not, then a polynomial time algorithm for determining the dimension of an \(N\)-free partial order would yield a polynomial time algorithm for this problem for an arbitrary partial order. It is proved that the dimension can be multiplied by an arbitrary large factor. However, there is a remark that R. Kimble gives a polynomial transformation from a partial order \(P\) of arbitrary height to a partial order \(P'\) of height 1 such that \(\dim P\leq \dim P'\leq 1+\dim P\). Hence, a polynomial algorithm for the dimension of \(N\)-free partial orders does imply a polynomial time constant ratio approximation algorithm for the general dimension problem.