Graph - K-Cores

K-Cores of a graph

Problem

Given a graph G and an integer K, K-cores of the graph are connected components that are left after all vertices of degree less than k have been removed.

Solution

To implement above algorithm, we do a modified DFS on the input graph and delete all the vertices having degree less than ‘K’, then update degrees of all the adjacent vertices, and if their degree falls below ‘K’ we will delete them too.

//Modified DFS function
bool Graph::DFSUtil(int v, vector<bool> &visited, 
                    vector<int> &vDegree, int k) 
{ 
    // Mark the current node as visited and print it 
    visited[v] = true; 
  
    // Recur for all the vertices adjacent to this vertex 
    list<int>::iterator i; 
    for (i = adj[v].begin(); i != adj[v].end(); ++i) 
    { 
        // degree of v is less than k, then degree of adjacent 
        // must be reduced 
        if (vDegree[v] < k) 
            vDegree[*i]--; 
  
        // If adjacent is not processed, process it 
        if (!visited[*i]) 
        { 
            // If degree of adjacent after processing becomes 
            // less than k, then reduce degree of v also. 
            if (DFSUtil(*i, visited, vDegree, k)) 
                vDegree[v]--; 
        } 
    } 
  
    // Return true if degree of v is less than k 
    return (vDegree[v] < k); 
} 

In the actual function, find the min degree vertex. Run DFSutil function.
Now apply DFSutil on all unvisited vertices.

Reference - geeksforgeeks

P.S.

Degeneracy : Degeneracy of a graph is the largest value k such that the graph has a k-core.

For example, the above shown graph has a 3-Cores and doesn’t have 4 or higher cores. Therefore, above graph is 3-degenerate.

Degeneracy of a graph is used to measure how sparse graph is.