The graph sandwich problem for 1-join composition is NP-complete
type: Item
instance of: scholarly article
title: The graph sandwich problem for 1-join composition is NP-complete
zbMATH Open document ID: 0995.05133
DOI: 10.1016/S0166-218X(01)00246-3
author: Sulamita Klein
author: Kristina Vušković
author: Celina M. H. de Figueiredo
published in: Discrete Applied Mathematics
publication date: 2002-08-29T00:00:00Z
review text: A graph \(G=(V,E)\) is a 1-join (or split) composition if there is a partition \((A,B,C,D)\) of \(V\) such that \(\{uv : uv \in E, u \in A \cup B, v \in C \cup D\} = \{uv : u \in B, v \in C\}\). Given two graphs \((V,E_1)\) and \((V,E_2)\), is there a 1-join composition \((V,E)\) such that \(E_1 \subseteq E \subseteq E_2\)? This is the graph sandwich problem for 1-join composition, which is proved to be NP-complete. In contrast, the graph sandwich problem for modular composition (\(A=\emptyset\) or \(D=\emptyset\)) is solvable in polynomial time [\textit{M. R. Cerioli, H. Everett, C. M. H. de Figueiredo} and \textit{S. Klein}, The homogeneous set sandwich problem, Inf. Process. Lett. 67, 31-35 (1998)] just like the recognition problem for 1-join compositions (\(E_1=E_2\)); see \textit{T.-H. Ma} and \textit{J. Spinrad} [J. Algorithms 16, 145-160 (1994; Zbl 0803.68092)].
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C17
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1792334
zbMATH Keywords: computational complexity
zbMATH Keywords: graph algorithm
zbMATH Keywords: sandwich problem
zbMATH Keywords: perfect graph
zbMATH Keywords: join decomposition
zbMATH Keywords: split decomposition
Wikidata QID: Q59904349
MaRDI profile type: Publication
cites work: Q3286847
cites work: Q5668821
cites work: Q3222223
cites work: The homogeneous set sandwich problem
cites work: Decomposition of Directed Graphs
cites work: A Combinatorial Decomposition Theory
cites work: Matrix sandwich problems
cites work: On the complexity of DNA physical mapping
cites work: Graph Sandwich Problems
cites work: Complexity and algorithms for reasoning about time
cites work: Complexity and algorithms for graph and hypergraph sandwich problems
cites work: Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
cites work: Bounded degree interval sandwich problems
cites work: The NP-completeness column: An ongoing guide
cites work: Normal hypergraphs and the perfect graph conjecture
cites work: Q3128916
cites work: Incremental modular decomposition
cites work: A semi-strong perfect graph theorem
cites work: \(P_ 4\)-trees and substitution decomposition
Recommended article: The graph sandwich problem for 1-join composition is NP-complete
Recommended article: Q4414488
Recommended article: Complexity and algorithms for graph and hypergraph sandwich problems
Recommended article: Algorithms and complexity of sandwich problems in graphs (extended abstract)
Recommended article: On (k,ℓ)-Graph Sandwich Problems
Recommended article: On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
Recommended article: The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
Recommended article: A general method for forbidden induced subgraph sandwich problem NP-completeness
Recommended article: The graph sandwich problem for \(P_4\)-sparse graphs
Recommended article: The chain graph sandwich problem
description: scientific article; zbMATH DE number 1792334