zbMATH — the first resource for mathematics

Algorithmic aspects of clique-transversal and clique-independent sets. (English) Zbl 0948.68135
Summary: A Minimum Clique-Transversal set MCT\((G)\) of a graph \(G= (V, E)\) is a set \(S\subseteq V\) of minimum cardinality that meets all maximal cliques in \(G\). A Maximum Clique-Independent set MCI\((G)\) of G is a set of maximum number of pairwise vertex-disjoint maximal cliques. We prove that the problem of finding an MCT\((G)\) and an MCI\((G)\) is NP-hard for cocomparability, planar, line and total graphs. As an interesting corollary we obtain that the problem of finding a minimum number of elements of a poset to meet all maximal antichains of the poset remains NP-hard even if the poset has height two, thereby generalizing a result of D. Duffus, H. A. Kierstead and W. T. Trotter [J. Comb. Theory, Ser. A 58, No. 1, 158-164 (1991; Zbl 0757.06001)]. We present a polynomial algorithm for the above problems on Helly circular-arc graphs which is the first such algorithm for a class of graphs that is not clique-perfect. We also present polynomial algorithms for the weighted version of the clique-transversal problem on strongly chordal graphs, chordal graphs of bounded clique size, and cographs. The algorithms presented run in linear time for strongly chordal graphs and cographs. These mark the first attempts at the weighted version of the problem.

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
Full Text: DOI
[1] Andreae, T.; Schughart, M.; Tuza, Zs., Clique-transversal sets of line graphs and complements of line graphs, Discrete math., 88, 11-20, (1991) · Zbl 0734.05077
[2] Balachandhran, V.; Nagavamsi, P.; Pandu Rangan, C., Clique transversal and clique independence on comparability graphs, Inform. process. lett., 58, 181-184, (1996)
[3] Booth, K.S.; Lueker, G.S., Testing for the consecutive ones property, interval graphs and graph planarity using P-Q tree algorithms, J. comput. system sci., 13, 335-379, (1976) · Zbl 0367.68034
[4] Chang, M.S.; Chen, Y.H.; Chang, G.J.; Yan, J.H., Algorithmic aspects of the genralized clique-transversal problem on chordal graphs, Discrete appl. math., 66, 189-203, (1996) · Zbl 0854.68072
[5] Chang, G.J.; Farber, M.; Tuza, Z., Algorithmic aspects of neighbourhood numbers, SIAM J. discrete 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] Corneil, D.G.; Fonlupt, J., The complexity of generalized clique covering, Discrete appl. math., 22, 109-118, (1988/1989) · Zbl 0685.68046
[8] Corneil, D.G.; Perl, Y.; Stewart, L.K., A linear recognition algorithm for cographs, SIAM J. comput., 14, 926-934, (1985) · Zbl 0575.68065
[9] Duffus, D.; Kierstead, H.A.; Trotter, W.T., Fibres and ordered set coloring, J. combin. theory ser. A, 58, 158-164, (1991) · Zbl 0757.06001
[10] Farber, M., Characterizations of strongly chordal graphs, Discrete math., 43, 173-189, (1983) · Zbl 0514.05048
[11] Farber, M., Domination, independent domination, and duality in strongly chordal graphs, Discrete appl. math., 7, 115-130, (1984) · Zbl 0531.05045
[12] Gavril, F., Algorithms on circular-arc graphs, Networks, 4, 357-369, (1974) · Zbl 0309.05126
[13] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980. · Zbl 0541.05054
[14] F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.
[15] 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
[16] Horton, J.D.; Kilakos, K., Minimum edge dominating sets, SIAM J. discrete math., 6, 375-387, (1993) · Zbl 0782.05083
[17] Lehel, J.; Tuza, Zs., Neighbourhood perfect graphs, Discrete math., 61, 93-101, (1986) · Zbl 0602.05053
[18] Lonc, Z.; Rival, I., Chains, antichains and fibres, J. combin. theory ser. A, 44, 207-228, (1987) · Zbl 0637.06001
[19] Ramalingam, G.; Pandu Rangan, C., A unified approach to domination problems on interval graphs, Inform. process. lett., 27, 271-274, (1988) · Zbl 0658.05040
[20] Tuza, Zs., Covering all cliques of a graph, Discrete math., 86, 117-126, (1990) · Zbl 0744.05040
[21] Yannakakis, M.; Gavril, F., Edge dominating sets in graphs, SIAM J. appl. math., 38, 364-372, (1980) · Zbl 0455.05047
[22] Yannakakis, M.; Gavril, F., The maximum k-colorable subgraph problem for chordal graphs, Inform. process. lett., 24, 133-137, (1987) · Zbl 0653.68070
[23] Yannakakis, M., Edge-deletion problems, SIAM J. comput., 10, 297-309, (1981) · Zbl 0468.05043
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.