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
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 9, 2012 at 18:20 | comment | added | Spice the Bird | @joel One ought to really be thinking of Graded posets in this context. This type of problem comes up when you look at the face poset of a polyhedron (really a regular cell complex). One question that you could ask is what conditions on poset maps between face posets do you need to ensure that these poset maps are induced by maps of polyhedra. One trivial remark is that if the polyhedron maps are injective, then the grading on the posets must be preserved. | |
| Nov 9, 2012 at 15:25 | history | edited | Brendan McKay | CC BY-SA 3.0 |
added 290 characters in body
|
| Nov 9, 2012 at 11:45 | comment | added | Emil Jeřábek | Joel’s comment provides a reduction of the subgraph isomorphism problem to its special case for connected graphs, so yes, it is also NP-complete. (Another way to fix the original construction is to add a self-loop to each vertex.) | |
| Nov 8, 2012 at 17:38 | comment | added | user22579 | Hum, I see... But this problem seems to be avoided if we considered only connected graphs (and the isomophism subgraphs problem for connected graphs is also NP-complete, isn't it ?) | |
| Nov 8, 2012 at 17:38 | comment | added | Joel David Hamkins | 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. | |
| Nov 8, 2012 at 17:08 | comment | added | Joel David Hamkins | A simpler counterexample: let $G$ have three points and no edges, and let $H$ have two points and one edge. So $G$ is not a subgraph, but as a poset, it maps (vacuously) into any poset with at least three points. | |
| Nov 8, 2012 at 17:05 | comment | added | Joel David Hamkins | 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. | |
| Nov 8, 2012 at 16:51 | comment | added | Joel David Hamkins | Ah, I was thinking induced subgraphs. This would be the same issue with $\Rightarrow$ and $\Leftrightarrow$ in your question. | |
| Nov 8, 2012 at 16:51 | comment | added | user22579 | 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$. | |
| Nov 8, 2012 at 16:41 | comment | added | Joel David Hamkins | 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. | |
| Nov 8, 2012 at 16:16 | vote | accept | CommunityBot | ||
| Nov 8, 2012 at 16:10 | vote | accept | CommunityBot | ||
| Nov 8, 2012 at 16:13 | |||||
| Nov 8, 2012 at 15:04 | history | answered | Brendan McKay | CC BY-SA 3.0 |