2
$\begingroup$

I'm looking for a fast algorithm to find a clique cover on an undirected unweighted graph.

I'm not looking for an optimal solution (ie minimal number of cliques). Obviously I'm also not looking for a maximal solution (ie 1 clique per edge on an edge cover).

Any pointer towards a nice algorithm?

$\endgroup$
2
  • 3
    $\begingroup$ This is usually studied as a conventional colouring problem on the complement of the graph instead ... as you probably know, there are many fast (somewhat intelligent greedy-styled) colouring algorithms which are fast. If the vast literature on graph colouring does not cover what you are looking for, you might need to be more specific as to what sort of attributes an algorithm you are looking for should have. $\endgroup$
    – JimN
    Mar 16, 2014 at 6:07
  • $\begingroup$ Coloring is inapproximable within $n^{1-\epsilon}$ for any $\epsilon>0$. DSATUR is a commonly used heuristic. There's a linear-time algorithm for finding a coloring using degeneracy+1 colors. $\endgroup$ Mar 16, 2014 at 22:15

1 Answer 1

2
$\begingroup$

You can use a fast (e.g. greedy) max clique algorithm to find cliques one after another. That is, find a maximal clique, remove it from the graph, and repeat until the graph is empty. If fact, I just coded this in C++ for some project that I'm working on now. I can share the code if you'd like it (it accepts DIMACS files).

$\endgroup$
1
  • $\begingroup$ It's fine I ended up coding it myself yesterday. But thanks :) $\endgroup$
    – m09
    Mar 17, 2014 at 1:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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