Data: 29/04/2019

Título:  PA general method for forbidden induced subgraph sandwich problem NP-completeness.

Palestrante: Rafael Teixeira, ICE-UFRRJ.

Data: 29 de Abril de 2019, 13 h.
Local: Sala 407, Bloco H, Campus Gragoatá, UFF.

Resumo: 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. Este trabalho foi aceito no X Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2019) (http://www.lagos2019.dcc.ufmg.br/ ) e foi realizado em colaboração com Simone Dantas (UFF),  Celina M. H. de Figueiredo (COPPE-UFRJ) e Priscila Petito (UERJ).