Helly property, clique graphs, complementary graph classes, and sandwich problems

Journal of the Brazilian Computer Society

Universidade Federal do Rio de Janeiro, Seropedica, Brasil¹  Dourado, Mitre C.¹  Teixeira, Rafael B.¹  Universidade Federal Rural do Rio de Janeiro¹  Figueiredo, Celina M. H. de¹  Petito, Priscila¹  Universidade Federal do Rio de Janeiro Caixa Postal, Rio de Janeiro, Brasil¹ 

关键词: Helly property;    Clique graphs;    Sandwich problems;    Computational difficulty of problems.;   

DOI  :  10.1007/BF03192558

学科分类：农业科学（综合）

来源: Springer U K

【 摘 要 】

A sandwich problem for property Π asks whether there exists a sandwich graph of a given pair of graphs which has the desired property Π. Graph sandwich problems were first defined in the context of Computational Biology as natural generalizations of recognition problems. We contribute to the study of the complexity of graph sandwich problems by considering the Helly property and complementary graph classes. We obtain a graph class defined by a finite family of minimal forbidden subgraphs for which the sandwich problem is NP-complete. A graph is clique-Helly when its family of cliques satisfies the Helly property. A graph is hereditary clique-Helly when all of its induced subgraphs are clique-Helly. The clique graph of a graph is the intersection graph of the family of its cliques. The recognition problem for the class of clique graphs was a long-standing open problem that was recently solved. We show that the sandwich problems for the graph classes: clique, clique-Helly, hereditary clique-Helly, and clique-Helly nonhereditary are all NP-complete. We propose the study of the complexity of sandwich problems for complementary graph classes as a mean to further understand the sandwich problem as a generalization of the recognition problem.

【 授权许可】

Unknown