Skip to main content
added 290 characters in body
Source Link
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

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.

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.

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.

Source Link
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

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.