Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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"?

share|improve this answer
    
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 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 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.