Note

An independent set in a graph is a set of vertices, no two of which are adjacent. A maximal independent set is an independent set that is not a subset of any other independent set in the graph. Here’s a basic approach to find a Maximal Independent Set:

  1. Start with an empty set S.
  2. Iterate over all vertices of the graph. For each vertex:
  3. If the vertex and its neighbors are not in S, add the vertex to S.

The set S at the end of this process is a Maximal Independent Set. This algorithm does not necessarily find the maximum independent set (the largest possible), as that problem is NP-hard, but it finds a set that is maximal, meaning it cannot be extended by adding more vertices.

Code

#include <iostream>
#include <unordered_set>
#include <vector>

auto max_independent_set(const std::vector<int> &row_ptr,
                         const std::vector<int> &col_idx) {
    int num_nodes = row_ptr.size() - 1;
    std::unordered_set<int> mis;
    std::vector<bool> in_set(num_nodes, false);

    for (int i = 0; i < num_nodes; i++) {
        if (in_set[i])
            continue;
        bool can_add = true;
        // make sure that none of the neighbors are in the set
        for (int j = row_ptr[i]; j < row_ptr[i + 1]; j++) {
            auto neighbor = col_idx[j];
            if (in_set[neighbor]) {
                can_add = false;
                break;
            }
        }

        if (can_add) {
            mis.insert(i);
            in_set[i] = true;
            // mark all the neighbors as in the set
            for (int j = row_ptr[i]; j < row_ptr[i + 1]; j++) {
                auto neighbor = col_idx[j];
                std::cout << i << " " << neighbor << "\n";
                in_set[neighbor] = true;
            }
        }
    }
    return mis;
}

int main() {
    /*
    0 - 1 - 3 - 5
    |   |
    2 - 4
    */
    // CSR representation of the graph
    std::vector<int> row_ptr = {0, 2, 5, 7, 9, 11, 12};
    std::vector<int> col_idx = {1, 2, 0, 3, 4, 0, 4, 1, 5, 1, 2, 3};

    auto mis = max_independent_set(row_ptr, col_idx);

    std::cout << "Maximal Independent Set: ";
    for (int v : mis) {
        std::cout << v << " ";
    }
    std::cout << std::endl;

    return 0;
}