A general method for forbidden induced subgraph sandwich problem NP-completeness

Speaker: Rafael Bernardo Teixeira, ICE-UFRRJ.

Date: 29 apr 2019, 13h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

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.

Obs.: Joint work with Simone Dantas (UFF), Celina M. H. de Figueiredo (COPPE-UFRJ) and Priscila Petito (UERJ).