# 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

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.

-

## 1 Answer

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).

Do you have more parameters or context for this problem? If you don't want a minimum solution, what is the most desired output, as there are many ways this can be done? Many clique-related problems are NP complete, so are you looking for a poly-time algorithm to find said "most desired output"?

-

I am looking for heuristics or greedy solutions at this point, so "most desired output" is not a constraint. That said, I want to avoid singular cliques; and triangles and cliques of size K are preferred over cliques of size 2. – Dhrumeel Bakshi Apr 15 '12 at 20:19
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
Thanks @Justin this sounds like a good place to start! I'm gonna try this and maybe it will be sufficient for what I need.  I'll also maybe edit the question to add more context. – Dhrumeel Bakshi Apr 17 '12 at 2:00
Reading the context you added - if you just want to make sure the graph is connected, computing the connected components of a graph is quite easy.  From there it is a simple matter of adding edges between the components.  I'm not sure how the "sets" you've described work (where do new edges go?), but there are a number of metrics which are easy to compute which may assist you in determining edges to add.  Edge-connectivity, min-cuts, diameter of a graph, and max distance from a vertex to any other vertex are all useful and can be ways to measure "connectivity". – Justin Apr 18 '12 at 2:22
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 11, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9568375945091248, "perplexity_flag": "head"}