1
$\begingroup$

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 Answers 1

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

  • 0
    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".2012-04-18