Name
Abstract | ||
|---|---|---|
We consider the sandwich problem, a generalization of the recognition problem introduced by Golumbic and Shamir (1993), with respect to classes of graphs defined by excluding induced subgraphs. The Π graph sandwich problem asks, for a pair of graphs G1 = (V, E1) and G2 = (V, E2) with E1 ⊆ E2, whether there exists a graph G = (V, E) with E1 ⊆ E ⊆ E2 that satisfies property Π. We consider the property of being H-free, where H is a fixed graph. Using a new variant of the SAT problem, we present a general framework to establish the NP-completeness of the sandwich problem for several H-free graph classes which generalizes the previous strategy for the class of Hereditary clique-Helly graphs. We also provide infinite families of 3-connected special forbidden induced subgraphs for which each forbidden induced subgraph sandwich problem is NP-complete. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.entcs.2019.08.035 | Electronic Notes in Theoretical Computer Science |
Keywords | Field | DocType |
algorithms and computational complexity,graph sandwich problems,satisfiability,Linear CNF-formula,3-sat,forbidden induced subgraph | Discrete mathematics,Graph,Existential quantification,Computer science,Sat problem,Induced subgraph,Completeness (statistics),Graph sandwich problem | Journal |
Volume | ISSN | Citations |
346 | 1571-0661 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Simone Dantas | 1 | 119 | 24.99 |
| Celina M. H. de Figueiredo | 2 | 296 | 38.49 |
| Priscila Petito | 3 | 12 | 1.74 |
| Rafael B. Teixeira | 4 | 49 | 5.31 |