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 injective order-preserving map from $G\_1$ to $G\_2$ ? (that is to say a function $f : G\_1 \rightarrow G\_2$ wich is injective and 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



Is it possible to decide in polynomial time if a poset is a subposet of another which is given ?
Completing Emil's observation: Take any subgraph isomorphism problem (well known to be NP-complete). Add a new vertex in the middle of each edge and then orient the new edges outwards from the new vertex. That is, replace each undirected edge $x-y$ by $x\leftarrow z\rightarrow y$. I think you get two posets (with two levels) for which the subposet problem is equivalent to the original. So it is NP-complete.


ADDED: It makes no difference if we define "subgraph" and "subposet" as containing all relations within a given set of points (the "induced subgraph" interpretation). Just take the smaller graph to be a clique and reduce from the NP-complete CLIQUE problem using the same construction.


