Maximum weighted clique in a large graph with high density

Question

Is there any software or an algorithm description that would let to find a maximum clique (approximately) with known number of vertices in a graph with ~17000 weighted vertices and ~75% density? I tried to use Cliquer but it's too slow (got me few days to get the result).

A little about my problem, just in case - it's a sceduling problem, I have 18 time slots, each of them can be filled by different numbers of alternatives. Each variable represents one alternative for one slot. So, all alternatives for one slot are mutually exclusive and some alternatives for different slots are incompatible. If two alternatives are compatible than there is an edge between them. Weight reperesent the value of the alternative.

Answer 1

The Boost Graph Library actually seems to have an implementation of a clique search algorithm, although I have not been able to find the documentation for it. However, you can take a look at the implementation source code of the algorithm and at this example to get an idea of how it's used. For your purpose, you could do something like this (this code compiles and works with Boost 1.55.0 and g++ 4.8.2 using flag -std=c++11):

#include <boost/graph/undirected_graph.hpp>
#include <boost/graph/bron_kerbosch_all_cliques.hpp>
#include <set>
#include <iostream>

// this is the visitor that will process each clique found by the algorithm
template <typename VertexWeight>
struct max_weighted_clique {
    typedef typename boost::property_traits<VertexWeight>::key_type Vertex;
    typedef typename boost::property_traits<VertexWeight>::value_type Weight;

    max_weighted_clique(const VertexWeight& weight_map, std::set<Vertex>& max_clique, Weight& max_weight)
        : weight_map(weight_map), max_weight(max_weight), max_clique(max_clique) {
        // max_weight = -inf
        max_weight = std::numeric_limits<Weight>::lowest();
    }

    // this is called each time a clique is found
    template <typename Clique, typename Graph>
    void clique(const Clique& c, const Graph& g) {
        // check the current clique value
        std::set<Vertex> current_clique;
        Weight current_weight = Weight(0);
        for(auto it = c.begin(); it != c.end(); ++it) {
            current_clique.insert(*it);
            current_weight += weight_map[*it];
        }
        // if it is a bigger clique, replace
        if (current_weight > max_weight) {
            max_weight = current_weight;
            max_clique = current_clique;
        }
    }

    const VertexWeight& weight_map;
    std::set<Vertex> &max_clique;
    Weight& max_weight;
};


// may replace with long, double...
typedef int Weight;

// this struct defines the properties of each vertex
struct VertexProperty {
    Weight weight;
    std::string name;
};

int main(int argc, char *argv[]) {
    // graph type
    typedef boost::undirected_graph<VertexProperty> Graph;
    // vertex descriptor type
    typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;

    // create the graph
    Graph g;

    // add vertices
    Vertex v1 = boost::add_vertex(g);
    g[v1].weight = 5; g[v1].name = "v1";
    Vertex v2 = boost::add_vertex(g);
    g[v2].weight = 2; g[v2].name = "v2";
    Vertex v3 = boost::add_vertex(g);
    g[v3].weight = 6; g[v3].name = "v3";
    // add edges
    boost::add_edge(v1, v2, g);
    boost::add_edge(v1, v3, g);
    boost::add_edge(v2, v3, g);

    // instantiate the visitor
    auto vertex_weight = boost::get(&VertexProperty::weight, g);
    std::set<Vertex> max_clique;
    Weight max_weight;
    max_weighted_clique<decltype(vertex_weight)> visitor(vertex_weight, max_clique, max_weight);

    // use the Bron-Kerbosch algorithm to find all cliques
    boost::bron_kerbosch_all_cliques(g, visitor);

    // now max_clique holds a set with the max clique vertices and max_weight holds its weight

    auto vertex_name = boost::get(&VertexProperty::name, g);
    std::cout << "Max. clique vertices:" << std::endl;
    for (auto it = max_clique.begin(); it != max_clique.end(); ++it) {
        std::cout << "\t" << vertex_name[*it] << std::endl;
    }
    std::cout << "Max. clique weight = " << max_weight << std::endl;

    return 0;
}

I don't know if this code would perform better or worse than Cliquer (I've not done much clique searching in big graphs), but you might as well give it a try (and share your conclusions :) )

There is also a Parallel Boost Graph Library, but unfortunately it does not seem to implement a clique search algorithm (not even a "hidden" one).

Also, I've just bumped into a parallel implementation of an algorithm to find maximum cliques called MaxCliquePara. I've not used it, so I cannot talk about ease of use or performance, but it looks good. However, note that this implementation search for cliques with maximum amount of vertices, which is not exactly what you're looking for - although maybe you can tweak the code to your needs.

EDIT:

It seems that there exists some documentation about the BGL bron_kerbosch_all_cliques() in the quickbook sources of the library. Although it's a documentation generator, it's fairly readable. So there's that.