Minimum clique cover problem: how to generate test cases?

How can I generate non trivial test cases for a minimum clique cover algorithm?

In other words, I'd like to generate a graph for which the minimum number of cliques and the assignment of each node to a clique are known in advance.

Thanks!

I've done a lot of work on clique discovery in Rust.

In general, I've found that a cover of size k is hardest to find when the cliques are approximately equal size, so for my own testing that's what I generated. The approach is basically:

Input:

number of vertices (call this n), 
number of cliques in the cover (call this k), 
and the fraction of potential edges that exist (call this p). 

Procedure:

Generate k approximately equal sized cliques (approximate in that some will be larger by 1 vertex if n%k != 0)
Calculate the remaining edges: p*choose(n, 2) - (edges used up by k cliques)
Randomly assign remaining edges to pairs of nonadjacent vertices.

Here's the Rust code I used to generate random graphs with a specified number of cliques:

fn get_random_graph_with_k_cliques(
  num_vertices: usize,
  cliques_ct: usize,
  edge_probability: f64,
) -> Graph {
  if cliques_ct == 0 {
    return get_random_graph(num_vertices, edge_probability);
  }

  let mut ret_graph = Graph::new(num_vertices);
  let mut edge_candidates_remaining = num_vertices * (num_vertices - 1) / 2;
  let mut edges_remaining = (edge_candidates_remaining as f64 * edge_probability) as usize;

  let reserved_edges = cliques_ct * (num_vertices / cliques_ct) * (num_vertices / cliques_ct - 1)
    / 2
    + (num_vertices % cliques_ct) * (num_vertices / cliques_ct);
  edge_candidates_remaining -= reserved_edges;
  if reserved_edges > edges_remaining {
    edges_remaining = 0;
  } else {
    edges_remaining -= reserved_edges;
  }

  for i in 0..(ret_graph.size - 1) {
    for j in (i + 1)..(ret_graph.size) {
      if i % cliques_ct == j % cliques_ct {
        ret_graph.vertices[i].neighbors_bv.set(j, true);
        ret_graph.vertices[j].neighbors_bv.set(i, true);
      } else if fastrand::f64() < (edges_remaining as f64) / (edge_candidates_remaining as f64) {
        edges_remaining -= 1;
        ret_graph.vertices[i].neighbors_bv.set(j, true);
        ret_graph.vertices[j].neighbors_bv.set(i, true);
      }

      if i % cliques_ct != j % cliques_ct {
        edge_candidates_remaining -= 1;
      }
    }
  }
  for i in 0..(ret_graph.size) {
    if ret_graph.vertices[i].neighbors_bv.any() {
      ret_graph.vertices[i].has_neighbors = true;
    }
  }
  ret_graph.conform_cliques_to_vertices();
  ret_graph
}

This is simulating a graph with a known clique cover and a known edge ratio ((count of edges) / (count of potential edges == count of pairs of distinct vertices).

This makes k equal-sized cliques, then adds random edges to get the total edge count desired.

You can ignore the conform_cliques_to_vertices() line. For my purposes, when a vertex was added to a clique I 'merged' it, treating the clique as a vertex with the intersection of edges out of the clique, but your needs may differ.

While this generates a graph with a known clique cover of size k, it doesn't guarantee that a better clique cover doesn't exists, and with randomness, especially given larger edge probabilities, it's certainly possible that a better clique cover exists.

For actually finding cliques, I'd recommend looking into the iterated greedy & Tabu methods. There's a nice paper summarizing several different approaches: A survey of local search methods for graph coloring, by Galinier & Hertz