Given a poset $P$ of height $|P|-k$, and an element $x \in P$, what is the computational complexity of finding the largest chain in which $x$ lies?
It is easy to do the above in time quadratic with respect to the size of the poset. For all $y \geq x$, find all $z \geq y \geq x$. Rinse and repeat until no more can be found, and do the same for $y \leq x$. Something of this sort should be able to return the chain in $O(|P|^2)$.
Can we do any better? The height restriction should put restrictions on the structure and adjacency matrix that could help...