The complexity of generalized clique covering
type: Item
instance of: scholarly article
title: The complexity of generalized clique covering
zbMATH Open document ID: 0685.68046
DOI: 10.1016/0166-218X(88)90086-8
published in: Discrete Applied Mathematics
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 4123300
zbMATH Keywords: computational complexity
zbMATH Keywords: NP-completeness
zbMATH Keywords: clique cover
zbMATH Keywords: chordal graphs
author: Derek G. Corneil
author: Jean Fonlupt
reviewed by: Franz Aurenhammer
MaRDI profile type: Publication
cites work: \(K_ i\)-covers. I: Complexity and polytopes
cites work: Ki-covers. II.Ki-perfect graphs
cites work: The complexity of generalized clique packing
cites work: A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
cites work: Q4198056
cites work: Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
cites work: Algorithms on clique separable graphs
cites work: Q4142699
cites work: Triangulated graphs and the elimination process
cites work: Decomposition by clique separators
cites work: Edge-Deletion Problems
cites work: The maximum k-colorable subgraph problem for chordal graphs
full work available at URL: 0166-218x(88)90086-8
OpenAlex ID: W2006147407
description: scientific article; zbMATH DE number 4123300