The graph sandwich problem for 1-join composition is NP-complete

✍ Scribed by Celina M.H. de Figueiredo; Sulamita Klein; Kristina Vušković

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 280 KB
• Volume: 5
• Category: Article
• ISSN: 1571-0653
• DOI: 10.1016/s1571-0653(05)80133-7

✦ Synopsis

A graph is a 1-join composition if its vertex set can be partitioned into four nonempty sets (A_{L}, A_{R}, S_{L}) and (S_{R}) such that: every vertex of (A_{L}) is adjacent to every vertex of (A_{R} ;) no vertex of (S_{L}) is adjacent to a vertex of (A_{R} \cup S_{R} ;) no vertex of (S_{R}) is adjacent to a vertex of (A_{L} \cup S_{L}). The graph sandwich problem for 1-join composition is defined as follows: Given a vertex set (V), a forced edge set (E^{1}), and a forbidden edge set (E^{3}), is there a graph (G=(V, E)) such that (E^{1} \subseteq E) and (E \cap E^{3}=\emptyset), which is a 1-join composition graph? We prove that the graph sandwich problem for 1-join composition is (N P)-complete. This result stands in contrast to the case where (S_{L}=\emptyset) (\left(S_{R}=\emptyset\right)), namely, the graph sandwich problem for homogeneous set, which has a polynomial-time solution.