On the recognition of neighborhood inclusion posets

Abstract

Let G be a simple graph. When we order the different closed neighborhoods of G by inclusion, the resulting poset is called the neighborhood inclusion poset. In this paper, we show that the problem of determining whether a poset is a neighborhood inclusion poset is NP-complete. We also apply this result to prove the NP-completeness of another problem about clique trees of chordal graphs and compatible trees of dually chordal graphs.