×

zbMATH — the first resource for mathematics

Variations of maximum-clique transversal sets on graphs. (English) Zbl 1235.90175
Summary: A maximum-clique transversal set of a graph \(G\) is a subset of vertices intersecting all maximum cliques of \(G\). The maximum-clique transversal set problem is to find a maximum-clique transversal set of \(G\) of minimum cardinality. Motivated by the placement of transmitters for cellular telephones, Chang, Kloks, and Lee introduced the concept of maximum-clique transversal sets on graphs in 2001. In this paper, we introduce the concept of maximum-clique perfect and some variations of the maximum-clique transversal set problem such as the \(\{k\}\)-maximum-clique, \(k\)-fold maximum-clique, signed maximum-clique, and minus maximum-clique transversal problems. We show that balanced graphs, strongly chordal graphs, and distance-hereditary graphs are maximum-clique perfect. Besides, we present a unified approach to these four problems on strongly chordal graphs and give complexity results for the following classes of graphs: split graphs, balanced graphs, comparability graphs, distance-hereditary graphs, dually chordal graphs, doubly chordal graphs, chordal graphs, planar graphs, and triangle-free graphs.

MSC:
90C35 Programming involving graphs or networks
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andreae, T. (1998). On the clique-transversal number of chordal graphs. Discrete Mathematics, 191, 3–11. · Zbl 0955.05058 · doi:10.1016/S0012-365X(98)00087-9
[2] Andreae, T., & Flotow, C. (1996). On covering all cliques of a chordal graph. Discrete Mathematics, 149, 299–302. · Zbl 0846.05050 · doi:10.1016/0012-365X(94)00276-O
[3] Andreae, T., Schughart, M., & Tuza, Zs. (1991). Clique transversal sets of line graphs and complements of line graphs. Discrete Mathematics, 88, 11–20. · Zbl 0734.05077 · doi:10.1016/0012-365X(91)90055-7
[4] Balachandran, V., Nagavamsi, P., & Rangan, C. P. (1996). Clique transversal and clique independence on comparability graphs. Information Processing Letters, 58, 181–184. · doi:10.1016/0020-0190(96)00054-3
[5] Bandelt, H. J., & Mulder, H. M. (1986). Distance hereditary graphs. Journal of Combinatorial Theory. Series B, 41, 182–208. · Zbl 0605.05024 · doi:10.1016/0095-8956(86)90043-2
[6] Berge, C., & Las Vergnas, M. (1970). Sur un Théorème du type König pour hypergraphes. Annals of the New York Academy of Sciences, 175, 32–40. · Zbl 0229.05136
[7] Bonomo, F., Durán, G., Lin, M. C., & Szwarcfiter, J. L. (2006a). On balanced graphs. Mathematical Programming, 105, 233–250. · Zbl 1080.05058 · doi:10.1007/s10107-005-0651-y
[8] Bonomo, F., Durán, G., Groshaus, M., & Szwarcfiter, J. L. (2006b). On clique-perfect and K-perfect graphs. Ars Combinatoria, 80, 97–112. · Zbl 1224.05358
[9] Bonomo, F., Chudnovsky, M., & Durán, G. (2008). Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs. Discrete Applied Mathematics, 156, 1058–1082. · Zbl 1138.05030 · doi:10.1016/j.dam.2007.05.048
[10] Bonomo, F., Chudnovsky, M., & Durán, G. (2009). Partial characterizations of clique-perfct graphs II: Diamond-free and Helly circular-arc graphs. Discrete Mathematics. doi: 10.1016/j.disc.2007.12.054 . · Zbl 1227.05151
[11] Brandstädt, A., Chepoi, V. D., & Dragan, F. F. (1997). Clique r-domination and clique r-packing problems on dually chordal graphs. SIAM Journal on Discrete Mathematics, 10, 109–127. · Zbl 0869.05048 · doi:10.1137/S0895480194267853
[12] Brandstädt, A., Dragan, F. F., Chepoi, V. D., & Voloshin, V. I. (1998). Dually chordal graphs. SIAM Journal on Discrete Mathematics, 11, 437–455. · Zbl 0909.05037 · doi:10.1137/S0895480193253415
[13] Brandstädt, A., Le, V. B., & Spinrad, J. P. (1999). Graph classes–a survey. SIAM monographs on discrete math. and applications. · Zbl 0919.05001
[14] Chang, G. J., Farber, M., & Tuza, Zs. (1993). Algorithmic aspects of neighborhood numbers. SIAM Journal on Discrete Mathematics, 6, 24–29. · Zbl 0777.05085 · doi:10.1137/0406002
[15] Chang, M. S., Chen, Y. H., Chang, G. J., & Yan, J. H. (1996). Algorithmic aspects of the generalized clique transversal problem on chordal graphs. Discrete Applied Mathematics, 66, 189–203. · Zbl 0854.68072 · doi:10.1016/0166-218X(95)00048-V
[16] Chang, M. S., Hsieh, S. Y., & Chen, G. H. (1997). Dynamic programming on distance-hereditary graphs. In: Proceedings of the 8th international symposium on algorithms and computation. Lecture notes in computer science, vol. 1350, pp. 344–353.
[17] Chang, M. S., Kloks, T., & Lee, C. M. (2001). Maximum clique transversals. In: Proceedings of the 27th international workshop on graph-theoretic concepts in computer science. Lecture notes in computer science, vol. 2204, pp. 32–43. · Zbl 1042.68619
[18] Dahlhaus, E., Kratochvíl, J., Manuel, P. D., & Miller, M. (1997). Transversal partitioning in balanced hypergraphs. Discrete Applied Mathematics, 79, 75–89. · Zbl 0887.05039 · doi:10.1016/S0166-218X(97)00034-6
[19] Dahlhaus, E., Manuel, P. D., & Miller, M. (1998). Maximum h-colourable subgraph problem in balanced graphs. Information Processing Letters, 65, 301–303. · Zbl 1338.68098 · doi:10.1016/S0020-0190(98)00019-2
[20] Dragan, F. F. (1993). HT-graphs: centers, connected r-domination, and Steiner trees. Computer Science Journal of Moldova, 1, 64–83.
[21] Durán, G., Lin, M. C., Mera, S., & Szwarcfiter, J. L. (2006). Algorithms for clique-independent sets on subclasses of circular-arc graphs. Discrete Applied Mathematics, 154, 1783–1790. · Zbl 1104.05054 · doi:10.1016/j.dam.2006.03.022
[22] Durán, G., Lin, M. C., Mera, S., & Szwarcfiter, J. L. (2008). Algorithms for finding clique-transversals of graphs. Annals of Operations Research, 157, 37–45. · Zbl 1163.90768 · doi:10.1007/s10479-007-0189-x
[23] Durán, G., Lin, M. C., & Szwarcfiter, J. L. (2002). On clique-transversal and clique-independent sets. Annals of Operations Research, 116, 71–77. · Zbl 1013.90107 · doi:10.1023/A:1021363810398
[24] Erdös, P., Gallai, T., & Tuza, Zs. (1992). Covering the cliques of a graph with vertices. Discrete Mathematics, 108, 279–289. · Zbl 0766.05063 · doi:10.1016/0012-365X(92)90681-5
[25] Farber, M. (1983). Characterizations of strongly chordal graphs. Discrete Mathematics, 43, 173–189. · Zbl 0514.05048 · doi:10.1016/0012-365X(83)90154-1
[26] Földes, S., & Hammer, P. L. (1977). Split graphs. Congressum Numberatum, 19, 311–315.
[27] Gabow, H. N., & Tarjan, R. E. (1991). Faster scaling algorithms for general graph matching problems. Journal of the Association for Computing Machinery, 38, 815–853. · Zbl 0799.68145
[28] Gavril, F. (1972). Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM Journal on Computing, 1, 180–187. · Zbl 0227.05116 · doi:10.1137/0201013
[29] Guruswami, V., & Rangan, C. P. (2000). Algorithmic aspects of clique-transversal and clique-independent sets. Discrete Applied Mathematics, 100, 183–202. · Zbl 0948.68135 · doi:10.1016/S0166-218X(99)00159-6
[30] König, D. (1916). Über Graphen und ihre Anwendungen auf Determinantentheorie und Mengenlehre. Mathematische Annalen, 77, 453–465. · JFM 46.0146.03 · doi:10.1007/BF01456961
[31] Lee, C. M., & Chang, M. S. (2006). Distance-hereditary graphs are clique-perfect. Discrete Applied Mathematics, 154, 525–536. · Zbl 1110.68108 · doi:10.1016/j.dam.2005.07.011
[32] Lee, C. M., & Chang, M. S. (2008). Variations of Y-dominating functions on graphs. Discrete Mathematics, 308, 4185–4204. · Zbl 1169.05037 · doi:10.1016/j.disc.2007.08.080
[33] Lehel, J., & Tuza, Zs. (1986). Neighborhood perfect graphs. Discrete Mathematics, 61, 93–101. · Zbl 0602.05053 · doi:10.1016/0012-365X(86)90031-2
[34] Makino, K., & Uno, T. (2004). New algorithms for enumerating all maximal cliques. In: Proceedings of the 9th Scandinavian workshop on algorithm theory. Lecture notes in computer science, vol. 3111, pp. 260–274. · Zbl 1095.68626
[35] Moscarini, M. (1993). Doubly chordal graphs, Steiner trees, and connected domination. Networks, 23, 59–69. · Zbl 0771.05076 · doi:10.1002/net.3230230108
[36] Paige, R., & Tarjan, R. E. (1987). Three partition refinement algorithms. SIAM Journal on Computing, 16, 973–989. · Zbl 0654.68072 · doi:10.1137/0216062
[37] Prisner, E. (1993). Hereditary clique-Helly graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 14, 216–220. · Zbl 0794.05113
[38] Rose, D. J. (1970). Triangulated graphs and the elimination process. Journal of Mathematical Analysis and Applications, 32, 597–609. · Zbl 0216.02602 · doi:10.1016/0022-247X(70)90282-9
[39] Shan, E., Liang, Z., & Chang, T. C. E. (2008). Clique-transversal number in cubic graphs. Discrete Mathematics and Theoretical Computer Science, 10, 115–124. · Zbl 1246.05123
[40] Spinrad, J. P. (1993). Doubly lexical ordering of dense 0-1 matrices. Information Processing Letters, 45, 229–235. · Zbl 0771.68068 · doi:10.1016/0020-0190(93)90209-R
[41] Uehara, R. (1996). NP-complete problems on a 3-connected cubic planar graph and their applications. Technical Report TWCU-M-0004, Tokyo Woman’s Christian University.
[42] Vazirani, V. V. (1994). A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm. Combinatorica, 14, 71–109. · Zbl 0806.05058 · doi:10.1007/BF01305952
[43] Xu, G., Shan, E., Kang, L., & Chang, T. C. E. (2007). The algorithmic complexity of the minus clique-transversal problem. Applied Mathematics and Computation, 189, 1410–1418. · Zbl 1125.05076 · doi:10.1016/j.amc.2006.12.027
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.