zbMATH — the first resource for mathematics

The complexity of generalized clique covering. (English) Zbl 0685.68046
A vertex cover of a graph G is a minimal set of vertices of G such that every edge of G contains at least one vertex in the set. The paper studies the following generalized clique cover problem. Let \(c_{ij}(G)\) denote the minimum number of complete graphs \(K_ j\) in G such that every \(K_ i\) in G \((i>j)\) contains at least one such \(K_ j\). Given an input graph G and an integer a, decide whether \(c_{ij}(G)\leq a\). The problem has been known to be NP-complete if \(i=j+1\), for \(j\geq 1\). This result is extended to arbitrary i,j, \(j>j\geq 1\), by generalizing the construction of proof. Moreover, when the input graph is restricted to be chordal (i.e., each cycle of length greater than 3 has some chord) then the NP-completeness of the problem is shown for \(i>j\geq 2\) by reduction from the general problem. (The restricted problem has been settled for \(i=j+1.)\) Finally, a polynomial-time algorithm for chordal graphs, \(j=1\), and fixed i is given whose complexity, however, is exponential in i. It is shown that even this problem becomes NP-complete if i is regarded as part of the input.
Reviewer: F.Aurenhammer

68Q25 Analysis of algorithms and problem complexity
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68R10 Graph theory (including graph drawing) in computer science
05C35 Extremal problems in graph theory
Full Text: DOI
[1] Conforti, M.; Corneil, D.G.; Mahjoub, A.R., K_{i}-covers I: complexity and polytopes, Discrete math., 58, 2, 121-142, (1986) · Zbl 0584.05052
[2] Conforti, M.; Corneil, D.G.; Mahjoub, A.R., K_{i}-covers II: ki-perfect graphs, J. graph theory, 11, 4, 569-584, (1987) · Zbl 0696.05042
[3] Corneil, D.G., The complexity of generalized clique packing, Discrete appl. math., 12, 233-239, (1985) · Zbl 0588.05037
[4] Corneil, D.G.; Keil, J.M., A dynamic programming approach to the dominating set problem on k-trees, SIAM J. algebraic discrete methods, 8, 4, 535-543, (1987) · Zbl 0635.05040
[5] 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
[6] Gavril, F., Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM J. comput., 1, 2, 180-187, (1972) · Zbl 0227.05116
[7] Gavril, F., Algorithms on clique separable graphs, Discrete math., 19, 159-165, (1977) · Zbl 0378.05042
[8] Karp, R.M., Reducibility among combinatorial problems, (), 85-103 · Zbl 0366.68041
[9] Rose, D.J., Triangulated graphs and the elimination process, J. math. anal. appl., 32, 597-609, (1970) · Zbl 0216.02602
[10] Tarjan, R.E., Decomposition by clique separators, Discrete math., 55, 221-232, (1985) · Zbl 0572.05039
[11] Yannakakis, M., Edge-deletion problems, SIAM J. comput., 10, 2, 297-309, (1981) · Zbl 0468.05043
[12] 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.