APPROXIMATION ALGORITHMS FOR THE K-CLIQUE COVERING PROBLEM

The problem of covering edges and vertices in a graph (or in a hypergr aph) was motivated by a problem arising in the context of the componen t assembly problem. The problem is as follows: given a graph and a cli que size Ic, find the minimum number of k-cliques such that all edges and vertices of the graph are covered by (included in) the cliques. Th is 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 pro blem. It is shown that the algorithms we design, which exploit the str ucture of this special set covering problem, have better performance t han those derived from direct applications of general purpose algorith ms for the set covering. In particular, these special classes of set c overing problems can be solved with better worst-case bounds and/or co mplexity than if treated as general set covering problems.