Approximation algorithms for the k-Clique Covering Problem
The problem of covering edges and vertices in a graph (or in a hypergraph) was
motivated by a problem arising in the context of component assembly problem.
The problem is, given a graph and a clique size k, find the minimum number of
k-cliques such that all edges and vertices of the graph are covered by
(included in) the cliques. This paper provides a collection of approximation
algorithms for various clique sizes with proven worst-case bounds. The problem
has a natural extension to hypergraphs, for which we consider one particular
class. The k-clique covering problem can be formulated as a Set Covering
problem. It is shown that the algorithms we design, that exploit the structure
of this special Set Covering problem, have better performance than those
derived from direct applications of general purpose algorithms for the Set
Covering. In particular, these special classes of Set Covering problems can be
solved with better worst-case bounds and/or complexity than if treated as
general Set Covering problems.
Click on the following title to view and download the paper in PostScript format.
- Approximation algorithms for the k-Clique Covering Problem (24 pages, 280 KB),
- Dorit S. Hochbaum, O. Goldschmidt, C. Hurken and G. Yu. SIAM J. of Discrete Math, Vol 9:3, 492-509, August (1996).