Minimum clique cover problem: how to generate test cases?

Question

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!

Answer 1

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

Answer 2

Algorithm

• Input I the intersection number. ( i.e. the minimum number of cliques that, together, cover every vertex in the graph. )

• Input ni numbers, the number of vertices in each of the I cliques. Each number must be 3 or more.

• Construct I vertices { VI }, linked together in a circle so that each vertex is connected to two others

• LOOP i over I

  • Construct ni - 1 vertices { ni }
  • Connect every vertex in { ni } to every other one in { ni } and to the ith member of { VI }

• RANDOMIZE the order of vertices and links ( to obscure the construction )

C++ implementation

#include <string>
#include <fstream>
#include <sstream>
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include "../PathFinder/src/cGraph.h"   // https://github.com/JamesBremner/PathFinder

int intersectionNumber;
std::vector<int> vCliqueCount;
raven::graph::cGraph g;

void input()
{
    std::cout << "Intersection Number: ";
    std::cin >> intersectionNumber;
    std::cout << "clique counts:\n";
    for (int i = 0; i < intersectionNumber; i++)
    {
        int cc;
        std::cout << "#" << i+1 << ": ";
        std::cin >> cc;
        vCliqueCount.push_back(cc);
    }
}

void generate()
{
    std::string previs;
    std::vector<std::string> vsclique;
    for (int i = 0; i < intersectionNumber; i++)
    {
        auto is = std::to_string(i);
        auto is0 = is+"_0";
        if (i > 0)
            g.add(is0, previs);
        previs = is0;

        vsclique.clear();
        for( int c1 = 0; c1 < vCliqueCount[i]-1; c1++ ) {
            vsclique.push_back(is+"_"+std::to_string(c1+1));
            g.add( is0,vsclique.back());
        }
        for( int c1 = 0; c1 < vsclique.size(); c1++ )
        {

            for( int c2 = c1+1; c2 < vsclique.size(); c2++ )
                g.add(vsclique[c1],vsclique[c2]);
        }
    }
    if( intersectionNumber>2)
        g.add("0_0", previs);

}

void output()
{
    std::ofstream ifs("gengraph.txt");
    if( ! ifs.is_open())
        throw std::runtime_error("Cannot open output");

    auto vl = g.edgeList();

    // this outputs vertex names that reveal the clique each vertex belongs to
    // for( auto& l : vl )
    // {
    //     ifs << "l " << g.userName(l.first)
    //          <<" "<<g.userName(l.second)<< "\n";
    // }

    // this outputs obscured graph construction
    std::random_shuffle( vl.begin(),vl.end());
    std::map<int,int>  obvertex;
    int kv = 0;
    for( auto& l : vl )
    {
        obvertex.insert(std::make_pair(l.first,kv++));
        obvertex.insert(std::make_pair(l.second,kv++));
        ifs << std::to_string(obvertex.find(l.first)->second)
             <<" "<<std::to_string(obvertex.find(l.second)->second)<< "\n";
    }

}

main()
{
    input();
    generate();
    output();

    return 0;
}

Test Run

Input

Intersection Number: 3
clique counts:
#1: 3
#2: 4
#3: 5

Output ( obscured )

0 1
2 3
4 5
2 7
2 9
5 11
7 11
14 15
9 3
0 15
1 15
7 4
0 14
0 27
4 11
1 27
7 5
2 0
27 15
1 14
7 0
27 14

Output ( vizgraph layout )

Windows build: https://github.com/JamesBremner/genclique/releases/tag/v1.0.0

Extra Edges

To further obscure the clique construction, we can add edges between vertices in different cliques stopping short of reducing the intersection number below specified. ( Suggestion by @Dave )

Each vertex in a clique has an index number. The vertex labels look like this "X_Y" where X is the clique index and Y is the vertex index in the clique, all indices zero-based. The zeroth vertex is the one connected to the other zeroth vertices in two other cliques during the initial construction. We now add edges between the other vertices, except for the vertices indexed 0 ( already connected to other cliques ) and 1 ( to prevent collapsing the intersection number ) to the vertices in other cliques, except for the same two exceptions.

It is probably easier to see what is going on if you look at the unobscured graphs that the code in the github repo outputs.

Here is the code

void extraEdges()
{
    // loop over all cliques
    for (int c1 = 0; c1 < intersectionNumber; c1++)
    {
        auto is = std::to_string(c1) + "_1";

        // loop over other cliques, not already connected to c1
        for (
            int c2 = c1 + 1;
            c2 < intersectionNumber;
            c2++)
        {
            // loop over vertices on other clique, except numbers 0 and 1
            for (int v = 2; v < vCliqueCount[c2]; v++)
            {
                auto sv2 = std::to_string(c2) + "_" + std::to_string(v);
                g.add(is, sv2);
            }
        }
    }
}

Here is the layout of the simplest construction, unobscured

2 3 3

Here is the layout ( obscured ) of a larger construction

3 3 4 5

Complete code, including extra edges and vizgraph layout at https://github.com/JamesBremner/genclique