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
    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.2012-04-15
  • 0
    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.2012-04-15
  • 0
    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.2012-04-17
  • 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