Helly Property, Clique Graphs, Complementary Graph Classes, and Sandwich Problems

**
Mitre C. Dourado,
Priscila Petito,
Rafael B. Teixeira,
Celina M. H. de Figueiredo.
**

A sandwich problem for property ¦ asks whether thereexists a sandwich graph of a given pair of graphs whichhas the desired property ¦. Graph sandwich problemswere first defined in the context of Computational Biologyas natural generalizations of recognition problems.We contribute to the study of the complexity of graphsandwich problems by considering the Helly property andcomplementary graph classes. We obtain a graph classdefined by a finite family of minimal forbidden subgraphsfor which the sandwich problem is NP-complete. Agraph is clique-Helly when its family of cliques satisfiesthe Helly property. A graph is hereditary clique-Hellywhen all of its induced subgraphs are clique-Helly. Theclique graph of a graph is the intersection graph of thefamily of its cliques. The recognition problem for the classof clique graphs was a long-standing open problem thatwas recently solved. We show that the sandwich problemsfor the graph classes: clique, clique-Helly, hereditaryclique-Helly, and clique-Helly nonhereditary are allNP-complete. We propose the study of the complexity ofsandwich problems for complementary graph classes asa mean to further understand the sandwich problem as ageneralization of the recognition problem.

http://www.lbd.dcc.ufmg.br/colecoes/jbcs/14/2/004.pdf

Biblioteca Digital Brasileira de Computação - Contato: bdbcomp@lbd.dcc.ufmg.br