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. –  user22579 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

1 Answer 1

up vote 7 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 ! –  user22579 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$. –  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
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

Your Answer

 
discard

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