Maximum Independent Set
(graph/maximum_independent_set.hpp)

• View this file on GitHub
• Last update: 2024-01-08 13:32:33+09:00
• Include: #include "graph/maximum_independent_set.hpp"

Description

最大独立集合を求める．

計算量はよくわからないが，実用上は非常に高速である．$n = 40$ のときに 2 ms 程度で動作する．

Operations

• vector<int> maximum_independent_set(vector<vector<int>> G)
  • グラフ $G$ の隣接リストが与えられたとき， $G$ の最大独立集合を求める．
  • 時間計算量: $O(n1.466^n)$

Verified with

• test/yosupo/maximum_independent_set.test.cpp

Code

#pragma once
#include <algorithm>
#include <vector>

std::vector<int> maximum_independent_set(
    const std::vector<std::vector<int>>& G) {
    const int n = G.size();
    std::vector<bool> used(n), ans(n);
    std::vector<int> deg(n), dead(n);
    std::ranges::transform(G, deg.begin(), [&](auto& g) { return g.size(); });
    int res = 0, cnt = 0, alive = n;

    auto dfs = [&](const auto& dfs) {
        if (cnt + alive <= res) return;

        int v = -1;
        for (int i = 0; i < n; ++i) {
            if (used[i] || dead[i]) continue;
            if (deg[i] <= 1) {
                v = i;
                break;
            }
            if (v < 0 || deg[v] < deg[i]) v = i;
        }
        if (v < 0) return;

        // not use
        if (deg[v] != 1) {
            dead[v] = true;
            --alive;
            for (int u : G[v]) --deg[u];

            dfs(dfs);

            dead[v] = false;
            ++alive;
            for (int u : G[v]) ++deg[u];
        }

        // use
        used[v] = true;
        --alive;
        for (int u : G[v]) {
            if (!dead[u]) --alive;
            ++dead[u];
        }
        ++cnt;
        if (res < cnt) {
            ans = used;
            res = cnt;
        }

        dfs(dfs);

        used[v] = false;
        ++alive;
        for (int u : G[v]) {
            --dead[u];
            if (!dead[u]) ++alive;
        }
        --cnt;
    };

    dfs(dfs);

    std::vector<int> ret;
    for (int i = 0; i < n; ++i) {
        if (ans[i]) ret.push_back(i);
    }
    return ret;
}

#line 2 "graph/maximum_independent_set.hpp"
#include <algorithm>
#include <vector>

std::vector<int> maximum_independent_set(
    const std::vector<std::vector<int>>& G) {
    const int n = G.size();
    std::vector<bool> used(n), ans(n);
    std::vector<int> deg(n), dead(n);
    std::ranges::transform(G, deg.begin(), [&](auto& g) { return g.size(); });
    int res = 0, cnt = 0, alive = n;

    auto dfs = [&](const auto& dfs) {
        if (cnt + alive <= res) return;

        int v = -1;
        for (int i = 0; i < n; ++i) {
            if (used[i] || dead[i]) continue;
            if (deg[i] <= 1) {
                v = i;
                break;
            }
            if (v < 0 || deg[v] < deg[i]) v = i;
        }
        if (v < 0) return;

        // not use
        if (deg[v] != 1) {
            dead[v] = true;
            --alive;
            for (int u : G[v]) --deg[u];

            dfs(dfs);

            dead[v] = false;
            ++alive;
            for (int u : G[v]) ++deg[u];
        }

        // use
        used[v] = true;
        --alive;
        for (int u : G[v]) {
            if (!dead[u]) --alive;
            ++dead[u];
        }
        ++cnt;
        if (res < cnt) {
            ans = used;
            res = cnt;
        }

        dfs(dfs);

        used[v] = false;
        ++alive;
        for (int u : G[v]) {
            --dead[u];
            if (!dead[u]) ++alive;
        }
        --cnt;
    };

    dfs(dfs);

    std::vector<int> ret;
    for (int i = 0; i < n; ++i) {
        if (ans[i]) ret.push_back(i);
    }
    return ret;
}

Back to top page