Paper Info
Title
Helly Property, Clique Graphs, Complementary Graph Classes, and Sandwich Problems
Abstract
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 Biol- ogy 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 prob- lems for the graph classes: clique, clique-Helly, heredi- tary 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.
Year
DOI
Venue
2008
10.1590/S0104-65002008000200004
J. Braz. Comp. Soc.
Keywords
Field
DocType
sandwich problems,clique graphs,computational difficulty of problems.,helly property,satisfiability,computational biology
Data mining,Block graph,Combinatorics,Line graph,Graph property,Clique graph,Computer science,Simplex graph,Null graph,Voltage graph,Split graph
Journal
Volume
Issue
Citations 
14
2
7
PageRank 
References 
Authors
0.52
8
4
Name
Order
Citations
PageRank
Mitre Dourado19018.43
Priscila Petito2121.74
Rafael B. Teixeira3495.31
Celina M. H. de Figueiredo429638.49