Timeline for Is it possible to decide in polynomial time if a poset is a subposet of another which is given ?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 9, 2012 at 11:56 | comment | added | Emil Jeřábek | I was mainly worried about injectivity. Whether the mapping should reflect the order is in principle also relevant, but in the presence of injectivity it does not affect the answer (the subgraph isomorphism problem and the induced subraph isomorphism problem are both NP-complete, by a reduction from clique). | |
| Nov 8, 2012 at 17:02 | comment | added | user22579 | Hum, perhaps I am missing something but I am not sure it is what Emil wanted to say. I think he just wants to be sure that the mapping doesn't assign two different elements of the first poset to the same element of the second one because in that case, it is indeed possible to solve the problem just by looking the height, as he said. | |
| Nov 8, 2012 at 16:21 | comment | added | Joel David Hamkins | To emphasize Emil's point: he is asking whether the OP really meant $\Rightarrow$, or instead should have written $\leftrightarrow$. | |
| Nov 8, 2012 at 16:20 | comment | added | user22579 | Oh, you are right, I forgot to specify the injectivity of the function, sorry; it is fixed now. | |
| Nov 8, 2012 at 16:16 | vote | accept | CommunityBot | ||
| Nov 8, 2012 at 16:16 | history | edited | user22579 | CC BY-SA 3.0 |
added 22 characters in body; added 10 characters in body
|
| Nov 8, 2012 at 16:10 | vote | accept | CommunityBot | ||
| Nov 8, 2012 at 16:13 | |||||
| Nov 8, 2012 at 15:33 | comment | added | Emil Jeřábek | 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$. | |
| Nov 8, 2012 at 15:06 | comment | added | Nathann Cohen | 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. | |
| Nov 8, 2012 at 15:04 | answer | added | Brendan McKay | timeline score: 7 | |
| Nov 8, 2012 at 14:56 | comment | added | Emil Jeřábek | It closely resembles the NP-complete subgraph isomorphism problem. | |
| Nov 8, 2012 at 14:46 | history | asked | user22579 | CC BY-SA 3.0 |