# 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 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

-
It closely resembles the NP-complete subgraph isomorphism problem. –  Emil Jeřábek Nov 8 '12 at 14:56
Indeed. If you could build such an algorithm you could use it on the following instances : "given any graph G, give the poset on $V(G) \cup E(G)$, where an element of $E(G)$ is larger than the two vertices to which it is incident. –  Nathann Cohen Nov 8 '12 at 15:06
Actually, the title is inconsistent with the wording of the question. If $f$ is required to be an isomorphic embedding (or at least injective), then the problem is NP-complete, as shown in Brendan’s answer. If it is only required to preserve the strict order as written, then the problem is solvable in polynomial time (or even NL): it is equivalent to asking whether the height of $G_1$ is at most the height of $G_2$. –  Emil Jeřábek Nov 8 '12 at 15:33
Oh, you are right, I forgot to specify the injectivity of the function, sorry; it is fixed now. –  user22579 Nov 8 '12 at 16:20
To emphasize Emil's point: he is asking whether the OP really meant $\Rightarrow$, or instead should have written $\leftrightarrow$. –  Joel David Hamkins Nov 8 '12 at 16:21

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.
There seems to be a problem with this answer. Consider the graph $G$ consisting of three points and no edges, and $H$ consisting of four points, with two parallel edges. So $G$ is not isomorphic to any subgraph of $H$, but if we do your procedure, no new points are added to $G$, but $H$ gains two points on the lower level, and there is a copy of $G$ inside the new $H$ poset. So in this instance, the subposet problem was not equivalent to the original subgraph isomorphism problem. –  Joel David Hamkins Nov 8 '12 at 16:41
Actually, in this case, G is isomorphic to the subgraph of any three points with no edge of H. We don't consider subgraph in the induced way, I think. That is to say : (E',V') is a subgraph of (E,V) if $E' \subset E$ and $V' \subset V$. –  user22579 Nov 8 '12 at 16:51
Ah, I was thinking induced subgraphs. This would be the same issue with $\Rightarrow$ and $\Leftrightarrow$ in your question. –  Joel David Hamkins Nov 8 '12 at 16:51