Helly property, clique raphs, complementary graph classes, and sandwich problems
Tóm tắt
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.
Tài liệu tham khảo
L. Alcón, L. Faria, C. M. H. de Figueiredo, M. Gutierrez. Clique graph recognition is NP-complete. InProc. WG 2006, Lecture Notes in Comput. Sci., vol. 4271, pages 269–277, 2006.
C. Berge and P. Duchet. A generalization of Gilmore’s theorem. InRecent Advances in Graph Theory, pages 49–55, Acad. Praha, Prague, 1975.
A. Brandstädt, V.B. Le, J.P. Spinrad.Graph Classes: A survey. SIAM Monographs on Discrete Mathematics and Applications, 1999.
S. Dantas, L. Faria, and C. M. H. de Figueiredo. On decision and optimization (k, l)-graph sandwich problems.Discrete Appl. Math., 143:155–165, 2004.
M. C. Dourado, F. Protti, J. L. Szwarcfiter. Computational aspects of the Helly property: a Survey.Journal of the Brazilian Computer Society, 12:7–33, 2006.
F. F. Dragan. Centers of Graphs and the Helly Property (in Russian). Doctoral Thesis, Moldava State University, Chisinâu, 1989.
C. M. H. de Figueiredo, S. Klein, and K. Vusković. The graph sandwich problem for 1-join composition is NP-complete.Discrete Appl. Math., 121:73–82, 2002.
M. C. Golumbic, H. Kaplan, and R. Shamir. Graph sandwich problems.J. of Algorithms, 19:449–473, 1995.
M. C. Golumbic and A. Wassermann. Complexity and algorithms for graph and hypergraph sandwich problems.Graphs Combin., 14:223–239, 1998.
M. Gutierrez and J. Meidanis. On the clique operator. InProc. Latin’98: Theoretical Informatics, Lecture Notes in Comput. Sci., vol. 1380, pages 261–272, 1998.
H. Kaplan and R. Shamir. Bounded degree interval sandwich problems.Algorithmica, 24:96–104, 1999.
T. A. McKee, F. R. McMorris.Topics in Intersection Graph Theory. SIAM Monographs on Discrete Mathematics and Applications, 1999.
E. Prisner. Hereditary clique-Helly graphs.J. Combin. Math. Combin. Comput., 14:216–220, 1993.
E. Prisner. A common generalization of line graphs and clique graphs,J. Graph Theory, 18:301–313, 1994.
E. Prisner.Graph Dynamics. Pitman Research Notes in Mathematics 338, Longman, 1995.
F. S. Roberts and J. H. Spencer. A characterization of clique graphs.J. Combin. Theory B, 10:102–108, 1971.
J. L. Szwarcfiter. Recognizing clique-Helly graphs. Ars Combinatoria, 45:29–32, 1997.
J. L. Szwarcfiter. A survey on clique graphs. InRecent Advances in Algorithms and Combinatorics, pages 109–136, Springer (CMS books in Mathematics), 2003.
W. D. Wallis and G. H. Zhang. On maximal clique irreducible graphs.J. Combin. Math. Combin. Comput., 8:187–193, 1990.