6
$\begingroup$

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

Improve this question
$\endgroup$
7
  • $\begingroup$ It closely resembles the NP-complete subgraph isomorphism problem. $\endgroup$
    – Emil Jeřábek
    Commented Nov 8, 2012 at 14:56
  • 1
    $\begingroup$ 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. $\endgroup$
    – Nathann Cohen
    Commented Nov 8, 2012 at 15:06
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Emil Jeřábek
    Commented Nov 8, 2012 at 15:33
  • $\begingroup$ Oh, you are right, I forgot to specify the injectivity of the function, sorry; it is fixed now. $\endgroup$
    – user22579
    Commented Nov 8, 2012 at 16:20
  • 1
    $\begingroup$ To emphasize Emil's point: he is asking whether the OP really meant $\Rightarrow$, or instead should have written $\leftrightarrow$. $\endgroup$
    – Joel David Hamkins
    Commented Nov 8, 2012 at 16:21

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – Joel David Hamkins
    Commented Nov 8, 2012 at 16:41
  • $\begingroup$ 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$. $\endgroup$
    – user22579
    Commented Nov 8, 2012 at 16:51
  • $\begingroup$ Ah, I was thinking induced subgraphs. This would be the same issue with $\Rightarrow$ and $\Leftrightarrow$ in your question. $\endgroup$
    – Joel David Hamkins
    Commented Nov 8, 2012 at 16:51
  • $\begingroup$ But given your reply, how about this case: $G$ has five points a,b,c,d,e, with two edges ab and cd. And $H$ has four points, with three edges ab, bc, and cd. So $G$ is not a subgraph of $H$, since it has too many points. The poset of $G$ is two disjoint $V$s and a dot, and the poset of $H$ is like $VVV$. We can map the poset of $G$ into the poset of $H$, in the $\Rightarrow$ sense of your question, by mapping the $V$s to the outside, and using the middle bottom dot for the extra point. $\endgroup$
    – Joel David Hamkins
    Commented Nov 8, 2012 at 17:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – Joel David Hamkins
    Commented Nov 8, 2012 at 17:38

You must log in to answer this question.