3

I am trying to write an algorithm that computes the edge clique cover number (the smallest number of cliques that cover all edges) of an input graph (undirected and no self-loops). My idea would be to

  1. Calculate all maximal cliques with the Bron-Kerbosch algorithm, and
  2. Try if any 1,2,3,... of them would cover all edges until I find the minimum number

Would that work and does anyone know a better method; is there a standard algorithm? To my surprise, I couldn't find any such algorithm. I know that the problem is NP-hard, so I don't expect a fast solution.

Rishav
  • 3,818
  • 1
  • 31
  • 49
E. Noether
  • 33
  • 3

2 Answers2

2

I would gather maximal cliques as you do now (or perhaps using a different algorithm, as suggested by CaptainTrunky), but then use branch and bound. This won't guarantee a speedup, but will often produce a large speedup on "easy" instances.

In particular:

  • Instead of trying all subsets of maximal cliques in increasing subset size order, pick an edge uv and branch on it. This means:
    • For each maximal clique C containing uv:
      • Make a tentative new partial solution that contains all cliques in the current solution
      • Add C to this partial solution
      • Make a new subproblem containing the current subproblem's graph, but with all vertices in C collapsed into a single vertex
      • Recurse to solve this smaller subproblem.
  • Keep track of the best complete solution so far. This is your upper bound (UB). You do not need to continue processing any subproblem that has already reached this upper bound but still has edges present; a better solution already exists!
  • It's best to pick an edge to branch on that is covered by as few cliques as possible. When choosing in what order to try those cliques, try whichever you think is likely to be the best (probably the largest one) first.

And here is an idea for a lower bound to improve the pruning level:

If a subgraph G' contains an independent set of size s, then you will need at least s cliques to cover G' (since no clique can cover two or more vertices in an independent set). Computing the largest possible IS is NP-hard and thus impractical here, but you could get a cheap bound by using the 2-approximation for Vertex Cover: Just keep choosing an edge and throwing out both vertices until no edges are left; if you threw out k edges, then what remains is an IS that is within k of optimal.

You can add the size of this IS to the total number of cliques in your solution so far; if that is larger than the current UB, you can abort this subproblem, since we know that fleshing it out further cannot produce a better solution than one we have already seen.

j_random_hacker
  • 50,331
  • 10
  • 105
  • 169
1

I was working on the similar problem 2 years ago and I've never seen any standard existing approaches to it. I did the following:

  1. Compute all maximal cliques. MACE was way better than Bron-Kerbosch in my case.
  2. Build a constraint-satisfaction problem for determining a minimum number of cliques required to cover the graph. You could use SAT, Minizinc, MIP tools to do so. Which one to pick? It depends on your skills, time resources, environment and dozens of other parameters. If we are talking about proof-of-concept, I would stick with Minizinc.

A bit details for the second part. Define a set of Boolean variables with respect to each edge, if it's value == True, then it's covered, otherwise, it's not. Add constraints that allow you covering sets of edges only with respect to each clique. Finally, add variables corresponding to each clique, if it's == True, then it's used already, otherwise, it's not. Finally, require all edges to be covered AND a number of used cliques is minimal.

CaptainTrunky
  • 1,562
  • 2
  • 15
  • 23