×

zbMATH — the first resource for mathematics

Algorithmic aspects of the generalized clique-transversal problem on chordal graphs. (English) Zbl 0854.68072
Summary: Suppose \(G = (V,E)\) is a graph in which each maximal clique \(C_i\) is associated with an integer \(r_i\), where \(0 \leq r_i \leq |C_i |\). The generalized clique transversal problem is to determine the minimum cardinality of a subset \(D\) of \(V\) such that \(|D \cap C_i |\geq r_i\) for every maximal clique \(C_i\) of \(G\). The problem includes the clique-transversal problem, the \(i,1\) clique-cover problem, and for perfect graphs, the maximum \(q\)-colorable subgraph problems as special cases. This paper gives complexity results for the problem on subclasses of chordal graphs, e.g., strongly chordal graphs, \(k\)-trees, split graphs, and undirected path graphs.
Reviewer: Reviewer (Berlin)

MSC:
68R10 Graph theory (including graph drawing) in computer science
05C35 Extremal problems in graph theory
05C15 Coloring of graphs and hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andreae, T.; Schughart, M.; Tuza, Z., Clique-transversal sets of line graphs and complements of line graphs, Discrete math., 88, 11-20, (1991) · Zbl 0734.05077
[2] Berge, C., Graphs and hypergraphs, (1973), North-Holland Amsterdam · Zbl 0483.05029
[3] Bertossi, A.A., Dominating sets for split and bipartite graphs, Inform. process. lett., 19, 37-40, (1984) · Zbl 0539.68058
[4] Booth, K.S.; Johnson, J.H., Dominating sets in chordal graphs, SIAM J. comput., 11, 191-199, (1982) · Zbl 0485.05055
[5] Chang, G.J.; Farber, M.; Tuza, Z., Algorithmic aspects of neighborhood numbers, SIAM J. disc. math., 6, 24-29, (1993) · Zbl 0777.05085
[6] Chang, G.J.; Nemhauser, G.L., The k-domination and k-stability problems on Sun-free chordal graphs, SIAM J. algebraic discrete methods, 5, 332-345, (1984) · Zbl 0576.05054
[7] Conforti, M.; Corneil, D.G.; Mahjoub, A.R., k, i-covers I: complexity and polytopes, Discrete math., 58, 121-142, (1986) · Zbl 0584.05052
[8] Corneil, D.G.; Fonlupt, J., The complexity of generalized clique covering, Discrete appl. math., 22, 109-118, (1989) · Zbl 0685.68046
[9] Corneil, D.G.; Keil, J.M., A dynamic programming approach to the dominating set problem on k-trees, SIAM J. algebraic discrete methods, 8, 535-543, (1987) · Zbl 0635.05040
[10] P. Erdös, T. Gallai and Z. Tuza, Covering the cliques of a graph with vertices, Discrete Math., to appear.
[11] Farber, M., Characterizations of strongly chordal graphs, Discrete math., 43, 173-189, (1983) · Zbl 0514.05048
[12] Földes, S.; Hammer, P.L., Split graphs, (), 311-315
[13] Frank, A., On chain and antichain families of a partially ordered set, J. combin. theory ser. B, 29, 176-184, (1980) · Zbl 0443.06003
[14] Fulkerson, D.R.; Gross, O.A., Incidence matrices and interval graphs, Pacific J. math., 15, 835-855, (1965) · Zbl 0132.21001
[15] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[16] Gavril, F., Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM J. comput., 1, 180-187, (1972) · Zbl 0227.05116
[17] Gavril, F., The intersection graphs of subtrees in trees are exactly the chordal graphs, J. combin. theory ser. B, 16, 47-56, (1974) · Zbl 0266.05101
[18] Gavril, F., A recognition algorithm for the intersection graphs of directed paths in directed trees, Discrete math., 13, 237-249, (1975) · Zbl 0312.05108
[19] Gavril, F., A recognition algorithm for the intersection graphs of paths in trees, Discrete math., 23, 221-227, (1978) · Zbl 0398.05060
[20] Gavril, F., Algorithms for maximum k-colorings and k-coverings of transitive graphs, Networks, 17, 465-470, (1987) · Zbl 0642.05021
[21] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[22] Greene, C., Some partitions associated with a partially ordered set, J. combin. theory ser. A, 20, 69-79, (1976) · Zbl 0323.06002
[23] Greene, C.; Kleitman, D., The structure of sperner k-families, J. combin. theory ser. A, 20, 41-68, (1976) · Zbl 0361.05016
[24] Hajnal, A.; Surányi, J., Über die auflos̈ung von graphen in vollständige teilgraphen, Ann. univ. sci. Budapest Eötvös sect. math., 1, 113-121, (1958) · Zbl 0093.37801
[25] Hedetniemi, S.T.; Laskar, R.C., Bibliography on domination in graphs and some definitions of domination parameters, Discrete math., 86, 257-277, (1990) · Zbl 0733.05076
[26] Hoffman, A.J.; Kolen, A.W.J.; Sakarovitch, M., Totally balanced and greedy matrices, SIAM J. algebraic discrete methods, 6, 721-730, (1985) · Zbl 0573.05041
[27] Hwang, S.H.; Chang, G.J., k-neighborhood covering and independence problems, ()
[28] Karp, R.M., Reducibility among combinatorial problems, (), 85-103 · Zbl 0366.68041
[29] Lekkerkerker, C.G.; Boland, J.C., Representation of a finite graph by a set of intervals on the real line, Fund. math., 51, 45-64, (1962) · Zbl 0105.17501
[30] Lehel, J.; Tuza, Z., Neighborhood perfect graphs, Discrete math., 61, 93-101, (1986) · Zbl 0602.05053
[31] Marathe, M.V.; Ravi, R.; Rangan, C.Pandu, Generalized vertex covering in interval graphs, Discrete appl. math., 39, 87-93, (1992) · Zbl 0766.05082
[32] Paige, R.; Tarjan, R.E., Three partition refinement algorithms, SIAM J. comput., 16, 973-989, (1987) · Zbl 0654.68072
[33] Rose, D.J., Triangulated graphs and the elimination process, J. math. anal. appl., 32, 597-609, (1970) · Zbl 0216.02602
[34] Sampathkumar, E.; Neeralagi, P.S., The neighborhood number of a graph, Indian J. pure appl. math., 16, 126-132, (1985) · Zbl 0564.05052
[35] J.P. Spinrad, Doubly lexical ordering of dense 0-1 matrices, preprint. · Zbl 0771.68068
[36] Tuza, Z., Covering all cliques of a graph, Discrete math., 86, 117-126, (1990) · Zbl 0744.05040
[37] Yannakakis, M., Edge-deletion problems, SIAM J. comput., 10, 297-309, (1981) · Zbl 0468.05043
[38] Yannakakis, M.; Gavril, F., The maximum k-colorable subgraph problem for chordal graphs, Inform. process. lett., 24, 133-137, (1987) · Zbl 0653.68070
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.