Abstract
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 τ 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 τ 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 τ 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.
Similar content being viewed by others
References
Balachandran, V., Nagavamsi, P., & Pandu Rangan, C. (1996). Clique transversal and clique independence on comparability graphs. Information Processing Letters, 58, 181–184.
Bonomo, F., Durán, G., Lin, M. C., & Szwarcfiter, J. L. (2006). On balanced graphs. Mathematical Programming B, 105, 233–250.
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.
Chang, G. J., Farber, M., & Tuza, Z. (1993). Algorithmic aspects of neighbourhood numbers. SIAM Journal on Discrete Mathematics, 6, 24–29.
Chang, M. S. (1998). Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM Journal on Computing, 27, 1671–1694.
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.
Dahlhaus, E., Manuel, P. D., & Miller, M. (1998). Maximum h-colourable subgraph problem in balanced graphs. Information Processing Letters, 65, 301–303.
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.
Durán, G., Lin, M. L., & Szwarcfiter, J. L. (2002). On clique-transversals and clique-independent sets. Annals of Operations Research, 116, 71–77.
Erdös, P., Gallai, T., & Tuza, Z. (1992). Covering the cliques of a graph with vertices. Discrete Mathematics, 108, 279–289.
Gavril, F. (1974). Algorithms on circular-arc graphs. Networks, 4, 357–369.
Guruswami, V., & Pandu Rangan, C. (2000). Algorithmic aspects of clique transversals and clique independent sets. Discrete Applied Mathematics, 100, 183–202.
Hsu, W. L., & Tsai, K. H. (1991). Linear time algorithms on circular-arc graphs. Information Processing Letters, 40, 123–129.
Joeris, B. C., McConnell, R. M., & Spinrad, J. P. (2006). Helly circular-arc graphs. SIAM conference on discrete mathematics, Victoria.
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.
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).
Payan, C. (1979). Remarks on cliques and dominating sets in graphs. Ars Combinatoria, 7, 181–189.
Tuza, Z. (1990). Covering all cliques of a graph. Discrete Mathematics, 86, 117–126.
Author information
Authors and Affiliations
Corresponding author
Additional information
G. Durán’s research partially supported by FONDECyT Grant 1050747 and Millennium Science Institute “Complex Engineering Systems”, Chile and CNPq under PROSUL project Proc. 490333/2004-4, Brazil.
M.C. Lin’s research partially supported by UBACyT Grants X184 and X212, PICT ANPCyT Grant 11-09112 and PID Conicet Grant 644/98, Argentina and CNPq under PROSUL project Proc. 490333/2004-4, Brazil.
S. Mera’s research partially supported by UBACyT grant X184, Fundación YPF, Argentina.
J.L. Szwarcfiter’s research partially supported by the Conselho Nacional de Desenvolvimento Científico e Tecnológico, CNPq, and Fundação de Amparo à Pesquisa do Estado do Rio de Janeiro, FAPERJ, Brasil.
Rights and permissions
About this article
Cite this article
Durán, G., Lin, M.C., Mera, S. et al. Algorithms for finding clique-transversals of graphs. Ann Oper Res 157, 37–45 (2008). https://doi.org/10.1007/s10479-007-0189-x
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-007-0189-x