Finding maximum clique with node count and nonadjacent edge list given

Question

I have a task which I have been trying to solve for the last week. It's driving me crazy. The task is:

Given a node count N(1 <= N <= 10`000),

nonadjacent node pair count M(1 <= M <= 200`000)

and the nonadjacent node pairs themselves

M_0A, M_0B,

M_1A, M_1B,

...

M_M-1A, M_M-1B,

find the maximum clique.

I am currently trying all kinds of bron-kerbosch algorithm variations. But every time I get a time limit on the testing site. I posted the only code that doesn't have a time limit BUT it has a wrong answer. The code is kind of optimized by not creating a new set every recursion.

Anyways, PLEASE help me. I am a desperate latvian teen programmer. I know this problem can be solved, because many people have solved it on the testing site.

#include <set>
#include <vector>

std::map<int, std::set<int> > NotAdjacent;

unsigned int MaxCliqueSize = 0;

void PrintSet(std::set<int> &s){
    for(auto it = s.begin(); it!=s.end(); it++){
        printf("%d ",*it);
    }
    printf("\n");
}

void Check(std::set<int> &clique, std::set<int> &left){
    //printf("printing clique: \n");
    //PrintSet(clique);
    //printf("printing left: \n");
    //PrintSet(left);

    if(left.empty()){
        //PrintSet(clique);
        if(clique.size()>MaxCliqueSize){
            MaxCliqueSize = clique.size();
        }
        return;
    }


    while(left.empty()==false){
        std::vector<int> removed;

        int v = *left.begin();
        left.erase(left.begin());


        for(auto it2=NotAdjacent[v].begin();it2!=NotAdjacent[v].end();it2++){

            auto findResult = left.find(*it2);

            if(findResult!=left.end()){
                removed.push_back(*it2);
                left.erase(findResult);
            }

        }

        clique.insert(v);
        Check(clique, left);
        clique.erase(v);

        for(unsigned int i=0;i<removed.size();i++){
            left.insert(removed[i]);
        }

    }
}

int main(){
    int n, m;
    scanf("%d%d",&n,&m);

    int a, b;
    for(int i=0;i<m;i++){
        scanf("%d%d",&a,&b);
        NotAdjacent[a].insert(b);
        NotAdjacent[b].insert(a);
    }

    std::set<int> clique, left;

    for(int i=1;i<=n;i++){
        left.insert(i);
    }
    Check(clique, left);
    printf("%d",MaxCliqueSize);
}

Answer 1

For what it's worth, this code seems to pass 5 tests and I think all the rest exceed either time or memory limits (submitted as C++11). This idea is to find a maximum independent set in the graph complement, for which we readily receive the edges for. The algorithm is what I could understand of the standard greedy one. Perhaps this can give you or others more ideas? I believe there are some improved algorithms for MIS.

#include <iostream>
using namespace std;

#include <map>
#include <set>
#include <vector>
#include <algorithm>

std::map<int, std::set<int> > NotAdjacent;
vector<int> Order;
unsigned int NumConnectedToAll = 0;
unsigned int MaxCliqueSize = 0;

bool sortbyN(int a, int b){ 
  return (NotAdjacent[a].size() > NotAdjacent[b].size());
}  

void mis(std::set<int> &g, unsigned int i, unsigned int size){
    if (g.empty() || i == Order.size()){
        if (size + NumConnectedToAll > MaxCliqueSize)
          MaxCliqueSize = size + NumConnectedToAll;
        return;
    }

    if (g.size() + size + NumConnectedToAll <= MaxCliqueSize)
     return;

    while (i < Order.size() && g.find(Order[i]) == g.end())
      i++;
    int v = Order[i];
    std::set<int> _g;
    _g = g;
    _g.erase(v);
    for (auto elem : NotAdjacent[v])
      _g.erase(elem);

    mis(_g, i + 1, size + 1);
}

int main(){
    int n, m;
    scanf("%d%d",&n,&m);

    int a, b;
    for(int i=0;i<m;i++){
        scanf("%d%d",&a,&b);
        NotAdjacent[a].insert(b);
        NotAdjacent[b].insert(a);
    }

    std::set<int> g;
    Order.reserve(NotAdjacent.size());
    for (auto const& imap: NotAdjacent){
      Order.push_back(imap.first);
      g.insert(imap.first);
    }
    sort(Order.begin(), Order.end(), sortbyN); 

    for (int i=1; i<=n; i++)
      if (NotAdjacent.find(i) == NotAdjacent.end())
        NumConnectedToAll++;

    for (unsigned int i=0; i<Order.size(); i++){
      mis(g, i, 0);
      g.erase(Order[i]);
    }

    printf ("%d", MaxCliqueSize);
    return 0;
}