Graph Coloring Problem

1

For a Given a undirected graph , find a set of vertices such that no two vertices in this set are connected by an edge.

Can anyone help me understand why the below-mentioned algorithm is wrong?

  1. Iterate on vertices in increasing order of their degree.
  2. Choose a vertex into the set if it is not marked yet.
  3. Iterate on its neighbours and mark them unfit to be chosen.

Code

vector<pi> q;
  for(int i=0; i<n; i++) {
    q.pb({adj[i].size(), i});
  }

  sort(all(q));
  vector<bool> chosen(n, false);
  vector<int> ans;
  for(auto x:q){
    if(chosen[x.second])
      continue;
    ans.pb(x.second);
    for(auto y:adj[x.second])
      chosen[y] = true;
  }
2

Did you mean “find the largest set”? Otherwise you can choose any vertex and be done.

Can you prove the correctness of your algorithm? Then I can tell you your mistake. If you don’t have a proof, then your code is just another heuristic algorithm.

spoiler

It’s called a maximum independent set and is NP hard.