×

Finding a sun in building-free graphs. (English) Zbl 1256.05082

Summary: Deciding whether an arbitrary graph contains a sun was recently shown to be NP-complete [C. T. Hoàng in SIAM J. Discrete Math. 23, No. 4, 2156–2162 (2009; Zbl 1207.68165)].
We show that whether a building-free graph contains a sun can be decided in \(O(\min\{mn ^{3}, m ^{1.5} n ^{2}\})\) time and, if a sun exists, it can be found in the same time bound. The class of building-free graphs contains many interesting classes of perfect graphs such as Meyniel graphs which, in turn, contains classes such as \(hhd\)-free graphs, \(i\)-triangulated graphs, and parity graphs. Moreover, there are imperfect graphs that are building-free.
The class of building-free graphs generalizes several classes of graphs for which an efficient test for the presence of a sun is known. We also present a vertex elimination scheme for the class of (building, gem)-free graphs. The class of (building, gem)-free graphs is a generalization of the class of distance hereditary graphs and a restriction of the class of (building, sun)-free graphs.

MSC:

05C17 Perfect graphs
05C85 Graph algorithms (graph-theoretic aspects)
05C12 Distance in graphs
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68R10 Graph theory (including graph drawing) in computer science

Citations:

Zbl 1207.68165
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon N., Yuster R., Zwick U.: Finding and counting given length cycles. Algorithmica 17, 209–223 (1997) · Zbl 0865.68093 · doi:10.1007/BF02523189
[2] Bandelt H.-J., Mulder H.M.: Distance-hereditary graphs. J. Combin. Theory B 41, 182–208 (1986) · Zbl 0605.05024 · doi:10.1016/0095-8956(86)90043-2
[3] Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications (1999) · Zbl 0919.05001
[4] Chvátal V.: Perfectly ordered graphs. In: Berge, C., Chvátal, V. (eds) Topics on Perfect Graphs, pp. 63–65. North-Holland, Amsterdam (1984)
[5] Dirac G.A.: On rigid circuit graphs. Abh. Math. Sem. Univ. Hamburg 25, 71–76 (1961) · Zbl 0098.14703 · doi:10.1007/BF02992776
[6] Dragan F.: Strongly orderable graphs: a common generalization of strongly chordal and chordal bipartite graphs. Discret. Appl. Math. 99, 427–442 (2000) · Zbl 0960.05094 · doi:10.1016/S0166-218X(99)00149-3
[7] Dragan, F., Nicolai, F.: LexBFS-orderings of distance-hereditary graphs. Schriftenreihe des Fachbereichs Mathematik der Universität Duisburg, Duisburg, Germany, SM-DU-303 (1995) · Zbl 0940.05024
[8] Eschen E.M., Hoàng C.T., Sritharan R.: An O(n 3)-time recognition algorithm for hhds-free graphs. Graphs Comb. 23, 209–231 (2007) · Zbl 1123.68089 · doi:10.1007/s00373-007-0706-3
[9] Farber M.: Characterizations of strongly chordal graphs. Discret. Math. 43, 173–189 (1983) · Zbl 0514.05048 · doi:10.1016/0012-365X(83)90154-1
[10] Golumbic M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980) · Zbl 0541.05054
[11] Hammer P.L., Maffray F.: Completely separable graphs. Discret. Appl. Math 27, 85–99 (1990) · Zbl 0694.05060 · doi:10.1016/0166-218X(90)90131-U
[12] Hoàng C.T.: On the complexity of finding a sun in a graph. SIAM J. Discret. Math. 23, 2156–2162 (2010) · Zbl 1207.68165 · doi:10.1137/080729281
[13] Hoàng C.T., Khouzam N.: On brittle graphs. J. Graph Theory 12, 391–404 (1988) · Zbl 0653.05059 · doi:10.1002/jgt.3190120310
[14] Hoàng C.T., Sritharan R.: Finding houses and holes in graphs. Theor. Comput. Sci. 259, 233–244 (2001) · Zbl 0973.68184 · doi:10.1016/S0304-3975(00)00005-0
[15] Nikolopoulos, S.D., Palios, L.: Recognizing hhds-free graphs. In: Proceedings of the 31st International Workshop on Graph Theoretic Concepts in Computer Science (WG 2005). Metz, France (2005) · Zbl 1123.68096
[16] Nikolopoulos S.D., Palios L.: Recognizing hh-free, hhd-free, and Welsh-Powell opposition graphs. Discret. Math. Theor. Comput. Sci. 8, 65–82 (2006) · Zbl 1153.05331
[17] Paige R., Tarjan R.E.: Three partition refinement algorithms. SIAM J. Comput. 16, 973–989 (1987) · Zbl 0654.68072 · doi:10.1137/0216062
[18] Rose D.J., Tarjan R.E., Leuker G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5, 266–283 (1976) · Zbl 0353.65019 · doi:10.1137/0205021
[19] Spinrad J.P.: Doubly lexical ordering of dense 0/1 matrices. Inf. Process. Lett. 45, 229–235 (1993) · Zbl 0771.68068 · doi:10.1016/0020-0190(93)90209-R
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.