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
Adding more context..
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.