彩色数
(graph/chromatic-number.hpp)

• View this file on GitHub
• Last update: 2021-01-15 18:15:31+09:00
• Include: #include "graph/chromatic-number.hpp"

彩色数

頂点数$n$のグラフの彩色数を$\mathrm{O}(2^n n)$で求めるライブラリ。

概要

wata氏の指数時間アルゴリズムの資料やnoshi氏のライブラリの解説などに詳しい。

$\lbrace1,2,\ldots,m\rbrace$の部分集合からなる集合を$[m]$、実数の集合$R$を$[m]$に対して拡張したものを$R[U_m]$と置き、subset zeta convolutionを$R[U_m]$上の乗法とする。

この時、グラフ$G(V,E),|V|=n$が$k$彩色可能であることは、$d[s]=[s$が独立集合である$]$を満たす$d \in R[U_n]$について$d^k[\lbrace1,2,\ldots,n\rbrace] \neq 0$ であることと同値である。

よって、係数が非零になるまで$d^k$を昇順に計算していけば彩色数が求まる。これは愚直に計算すると$\mathrm{O}(2^n n^2)$だが、必要な係数は一つだけなのでゼータ/メビウス変換を陽に計算する必要はない事実を利用すると計算量を$\mathrm{O}(2^n n)$に改善できる。

Verified with

• verify/verify-yosupo-graph/yosupo-chromatic-number.test.cpp

Code

#pragma once

#include <cstdint>
#include <utility>
#include <vector>
using namespace std;

namespace ChromaticNumberImpl {
using i64 = int64_t;
template <uint32_t mod>
int calc(int n, vector<pair<int, int>> hist) {
  for (int c = 1; c <= n; c++) {
    i64 sm = 0;
    for (auto& [i, x] : hist) sm += (x = i64(x) * i % mod);
    if (sm % mod != 0) return c;
  }
  return n;
}
}  // namespace ChromaticNumberImpl

template <typename G>
__attribute__((target("avx2"))) int ChromaticNumber(G& g) {
  int n = g.size();
  vector<int> adj(n), dp(1 << n);
  for (int i = 0; i < n; i++)
    for (auto& j : g[i]) adj[i] |= 1 << j, adj[j] |= 1 << i;
  dp[0] = 1;
  for (int i = 1; i < (1 << n); i++) {
    int j = __builtin_ctz(i);
    int k = i & (i - 1);
    dp[i] = dp[k] + dp[k & ~adj[j]];
  }
  vector<int> memo((1 << n) + 1);
  for (int i = 0; i < (1 << n); i++)
    memo[dp[i]] += __builtin_parity(i) ? -1 : 1;
  vector<pair<int, int>> hist;
  for (int i = 1; i <= (1 << n); i++)
    if (memo[i]) hist.emplace_back(i, memo[i]);
  return min(ChromaticNumberImpl::calc<1000000021>(n, hist),
             ChromaticNumberImpl::calc<1000000033>(n, hist));
}

/**
 * @brief 彩色数
 * @docs docs/graph/chromatic-number.md
 */

#line 2 "graph/chromatic-number.hpp"

#include <cstdint>
#include <utility>
#include <vector>
using namespace std;

namespace ChromaticNumberImpl {
using i64 = int64_t;
template <uint32_t mod>
int calc(int n, vector<pair<int, int>> hist) {
  for (int c = 1; c <= n; c++) {
    i64 sm = 0;
    for (auto& [i, x] : hist) sm += (x = i64(x) * i % mod);
    if (sm % mod != 0) return c;
  }
  return n;
}
}  // namespace ChromaticNumberImpl

template <typename G>
__attribute__((target("avx2"))) int ChromaticNumber(G& g) {
  int n = g.size();
  vector<int> adj(n), dp(1 << n);
  for (int i = 0; i < n; i++)
    for (auto& j : g[i]) adj[i] |= 1 << j, adj[j] |= 1 << i;
  dp[0] = 1;
  for (int i = 1; i < (1 << n); i++) {
    int j = __builtin_ctz(i);
    int k = i & (i - 1);
    dp[i] = dp[k] + dp[k & ~adj[j]];
  }
  vector<int> memo((1 << n) + 1);
  for (int i = 0; i < (1 << n); i++)
    memo[dp[i]] += __builtin_parity(i) ? -1 : 1;
  vector<pair<int, int>> hist;
  for (int i = 1; i <= (1 << n); i++)
    if (memo[i]) hist.emplace_back(i, memo[i]);
  return min(ChromaticNumberImpl::calc<1000000021>(n, hist),
             ChromaticNumberImpl::calc<1000000033>(n, hist));
}

/**
 * @brief 彩色数
 * @docs docs/graph/chromatic-number.md
 */

Back to top page