Skip to main content
1 of 2
user avatar
user avatar

Is it possible to decide in polynomial time if a poset is a subposet of another which is given ?

I am reading some theory on partial orders and I wonder something which perhaps has a simple answer : Given two partial orders $G_1,G_2$ (by their hasse diagrams), is it possible to know in polynomial-time if it exists a order-preserving map from $G_1$ to $G_2$ ? (that is to say a function $f : G_1 \rightarrow G_2$ such that $\forall x,y, x< y \Rightarrow f(x) < f(y)$)

We can easily solve the problem in exponential-time (and it is in NP, of course) but I don't find neither a better algorithm neither literature about this. Is this an already-know problem and do we have something about this ?

Thanks

user22579