zbMATH — the first resource for mathematics

Algorithms for finding clique-transversals of graphs. (English) Zbl 1163.90768
Summary: A clique-transversal of a graph \(G\) is a subset of vertices intersecting all the cliques of \(G\). It is NP-hard to determine the minimum cardinality \(\tau_c\) of a clique-transversal of \(G\). In this work, first we propose an algorithm for determining this parameter for a general graph, which runs in polynomial time, for fixed \(\tau_c\). This algorithm is employed for finding the minimum cardinality clique-transversal of \(\overline{3K_{2}}\)-free circular-arc graphs in \(O(n^{4})\) time. Further we describe an algorithm for determining \(\tau_c\) of a Helly circular-arc graph in \(O(n)\) time. This represents an improvement over an existing algorithm by Guruswami and Pandu Rangan which requires \(O(n^{2})\) time. Finally, the last proposed algorithm is modified, so as to solve the weighted version of the corresponding problem, in \(O(n^{2})\) time.

90C35 Programming involving graphs or networks
Full Text: DOI
[1] Balachandran, V., Nagavamsi, P., & Pandu Rangan, C. (1996). Clique transversal and clique independence on comparability graphs. Information Processing Letters, 58, 181–184. · doi:10.1016/0020-0190(96)00054-3
[2] Bonomo, F., Durán, G., Lin, M. C., & Szwarcfiter, J. L. (2006). On balanced graphs. Mathematical Programming B, 105, 233–250. · Zbl 1080.05058 · doi:10.1007/s10107-005-0651-y
[3] 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
[4] Chang, G. J., Farber, M., & Tuza, Z. (1993). Algorithmic aspects of neighbourhood numbers. SIAM Journal on Discrete Mathematics, 6, 24–29. · Zbl 0777.05085 · doi:10.1137/0406002
[5] Chang, M. S. (1998). Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM Journal on Computing, 27, 1671–1694. · Zbl 0911.05051 · doi:10.1137/S0097539792238431
[6] 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
[7] 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
[8] Durán, G., Lin, M. L., Mera, S., & Szwarcfiter, J. L. (2006). Algorithms for clique-independent sets on subclasses of circular-arc graphs. Discrete Applied Mathematics, 154(13), 1783–1790. · Zbl 1104.05054 · doi:10.1016/j.dam.2006.03.022
[9] Durán, G., Lin, M. L., & Szwarcfiter, J. L. (2002). On clique-transversals and clique-independent sets. Annals of Operations Research, 116, 71–77. · Zbl 1013.90107 · doi:10.1023/A:1021363810398
[10] Erdös, P., Gallai, T., & Tuza, Z. (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
[11] Gavril, F. (1974). Algorithms on circular-arc graphs. Networks, 4, 357–369. · Zbl 0309.05126 · doi:10.1002/net.3230040407
[12] Guruswami, V., & Pandu Rangan, C. (2000). Algorithmic aspects of clique transversals and clique independent sets. Discrete Applied Mathematics, 100, 183–202. · Zbl 0948.68135 · doi:10.1016/S0166-218X(99)00159-6
[13] Hsu, W. L., & Tsai, K. H. (1991). Linear time algorithms on circular-arc graphs. Information Processing Letters, 40, 123–129. · Zbl 0748.68044 · doi:10.1016/0020-0190(91)90165-E
[14] Joeris, B. C., McConnell, R. M., & Spinrad, J. P. (2006). Helly circular-arc graphs. SIAM conference on discrete mathematics, Victoria. · Zbl 1209.68376
[15] Lee, C. M., Chang, M. S., & Sheu, S. C. (2002). The clique transversal and clique independence of distance hereditary graphs. In Proceedings of the 19th workshop on combinatorial mathematics and computation theory, pp. 64–69, Taiwan.
[16] Lin, M., & Szwarcfiter, J. (2006). Characterizations and linear time recognition of Helly circular-arc graphs. In Lecture notes in computer science: Vol. 4112. Proceedings of the 12th annual international conference on computing and combinatorics (COCOON’06)(pp. 73–82). · Zbl 1162.05360
[17] Payan, C. (1979). Remarks on cliques and dominating sets in graphs. Ars Combinatoria, 7, 181–189. · Zbl 0443.05063
[18] Tuza, Z. (1990). Covering all cliques of a graph. Discrete Mathematics, 86, 117–126. · Zbl 0744.05040 · doi:10.1016/0012-365X(90)90354-K
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.