Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
It closely resembles the NP-complete subgraph isomorphism problem. –  Emil Jeřábek Nov 8 '12 at 14:56
1  
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
2  
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. –  gLre Nov 8 '12 at 16:20
1  
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
show 2 more comments

1 Answer

up vote 8 down vote accepted

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.

share|improve this answer
    
Thank you a lot for this answer ! –  gLre Nov 8 '12 at 16:21
    
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$. –  gLre 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
1  
I guess they don't need to be connected, but rather only to have no isolated points, since that would ensure that in the poset version, the levels are respected. So I guess you could just add another point connected to everybody before you start, and then apply the transformation. –  Joel David Hamkins Nov 8 '12 at 17:38
show 5 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.