Skip to main content
MathOverflow

Return to Question

added 22 characters in body; added 10 characters in body
Source Link
user22579
user22579

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

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 order-preserving map from $G_1$ to $G_2$ ? (that is to say a function $f : G_1 \rightarrow G_2$ 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

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

Source Link
user22579
user22579

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 order-preserving map from $G_1$ to $G_2$ ? (that is to say a function $f : G_1 \rightarrow G_2$ 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