# Non-disjoint partition of a graph into cliques of bounded size

I am looking for a method to list cliques in a graph such that:

• All vertices of the graph are included in at-least one clique
• The size of every clique is no greater than a bound K

The problem seems to be similar to the Clique Cover Problem. However, my problem places a bound on the size of cliques rather than on the number of cliques listed in the solution.
Also in my problem, a vertex may appear in more than one clique. In other words, I am not looking for disjoint partitions into cliques.

I would prefer to have a small number cliques in the output, but a minimum solution is not necessary.

I don't have too much experience with graph-theory or graph-algorithms, so I would appreciate any pointers towards a relevant method for this situation.

Thanks!

EDIT

What I started with originally is a graph-representation of my problem (say graph G).
There are certain nodes (and groups of nodes) in G which are independent. I want to add more edges to this graph with the aim of making G more 'connected' to optimize my original problem.
(I have a bunch of sets of edges over G, and the objective is to select a minimum number of sets to include all nodes)

So I construct the complement graph of G ($G_C$), and try to find cliques in $G_C$, to help me find groups of nodes to attempt to connect in G.
The computation of new edges is expensive, so I want to do it as few times as possible, and also keep a bound on the number of nodes in consideration at a time.

I realize that I am probably being too vague.. I tried to be general enough while avoiding telling a long story :). The bottomline objective is to find cliques of moderate size in $G_C$ that I can attempt to break-up.

So I am trying to think of ways to list cliques to cover all nodes, while keeping as less overlap between cliques as possible.

-

There are a number of trivial solutions: Take each node as its own clique, or take each edge as a $K_2$ (2 node clique).
Degree-based clique growing could be an interesting attempt. Start by computing the degree of each node (note that each node has a set of neighbors [edges]). Start with your highest degree node. Pick the neighbor with highest degree and intersect the neighbor sets [denote this set $S$]. Pick the node $n$ from $S$ with highest degree and intersect the neighbors of $n$ with $S$ and rename that $S$. Repeat. Once $S$ is empty, pick a new node by taking the highest degree node that is not yet in a clique and repeat. This has lots of flaws, but it's hard to optimize without a precise goal. – Justin Apr 15 '12 at 20:52