連載しょぼんコーダー 7 有限位相空間の判定

第7回では, $\{0, 1, \cdots, n-1\}$ の部分集合系 $S$ が与えられたときに, $S$ が開集合系の定義を満たす（ $(\{0, 1, \cdots, n-1\}, S)$ が位相空間になる）かどうかの判定について書きます.

計算量は $S$ の要素数を $m$ , ワードサイズを $w$ として, 時間計算量 $O(n^2 m /w)$ , 空間計算量 $O(n^2+m)$ です. これが多項式時間になるという雰囲気が好きです.

あらすじ: $S$ を含む最小の位相空間の要素数が $m$ であるかを判定すればよい. $S$ を含む最小の位相空間と対応する preorder を作り, 縮約し DAG にする. その DAG についてある種の DFS を行い, 開集合の個数を数え上げる. ただし, 個数が $m$ を超えたら切り上げる.

問題設定

正整数 $n$ と, $\{0, 1, \cdots, n-1\}$ の要素数 $m$ の部分集合系 $S$ が与えられます. 「 $S$ が開集合系かどうか判定して」と電話したら, あなたはすぐに答えてくれますか？

$n \le 60, m \le 300000$

preorder と有限位相空間

有限位相空間と前順序 (preorder) という二項関係とには全単射があります. 有限位相空間を $(X, \mathcal{O})$ （ $X$ は有限集合、 $\mathcal{O} \subset 2^X$ は開集合系）と書くことにします. また, preorder の二項関係を $\le$ とします.

開集合系 → preorder

$a, b \in X$ なら, $a \le b$ であることは,「任意の $\mathcal{O}$ の要素 $O$ について, $a \in O$ なら $b \in O$ が成り立つ」とき, かつそのときに限ることにします. そうすると, 開集合系から preorder が出来ます.

preorder → 開集合系

$a \in X$ に対し, $a \le b$ を満たす $b \in X$ の集合を $T_a$ とします. そうして

$\displaystyle \mathcal{O} = \{\bigcup_{a \in S} T_a \mid S \subset X\}$

とすると, preorder から開集合系が出来ます.

証明

J - Set Construction 解説：ストーリー

https://atcoder.jp/contests/ttpc2023/editorial/7404

に書きました

$S$ を含む最小の位相空間

与えられた $X = \{0, 1, \cdots, n-1\}$ の部分集合系 $S$ について, 「開集合系 → preorder」にしたがって順序を作ると, それは preorder になります.

これが $S$ を含む最小の位相空間 $(X, \mathcal{O})$ と対応する preorder であることを示します.

$S \subset \mathcal{O}$

「preorder → 開集合系」の各 $T_a$ ( $a \in X$ ) について, $T_a \in S$ です. 以下の補題より $A \in \mathcal{O}$ がわかるので示されます.

補題1 任意の開集合 $A \in S$ について $A = \bigcup_{a \in A} T_a$ が成り立つ.

証明: $a \in T_a$ なので $A \subset \bigcup_{a \in A} T_a$ がいえます.

$A \ne \bigcup_{a \in A} T_a$ とします. $k \in \left(\bigcup_{a \in A} T_a\right) - A$ をとると, ある $a \in A$ が存在して $k \in T_a$ となります. $T_a$ の定義より $k \in A$ となりますが, $k \not \in A$ なので矛盾です. ■

$\mathcal{P}$ が開集合系, $S \subset \mathcal{P}$ なら $\mathcal{O} \subset \mathcal{P}$

↑これは $\mathcal{O}$ が $S$ から生成される開集合系であることを言っています.

$\le_\mathcal{P}$ を $\mathcal{P}$ に対応する preorder とします. $R_a$ ( $a \in X$ ) を $a \le_{\mathcal{P}} b$ となる $b$ の集合とします. そうすると, $S \subset \mathcal{P}$ より, 任意の開集合 $A \in S$ について $A = \bigcup_{a \in A} R_a$ が言えます.

補題2 任意の $a \in X$ に対し $R_a \subset T_a$ である.

$R_a \not \subset T_a$ を仮定し, $k \in R_a - T_a$ をとります. $k \not \in T_a$ なので, ある $A \in S$ が存在して $a \in A$ かつ $k \not \in A$ です.

いま $A = \bigcup_{b \in A} R_b$ でしたが, $a \in A$ なので $k \in R_a \subset \bigcup_{b \in A} R_b = A$ です. これは $k \not \in A$ に矛盾します.■

補題3 $\mathcal{O}$ の任意の開集合 $O$ について, $O \in \mathcal{P}$ である.

証明: 任意の $a \in X$ に対して補題2より $R_a \subset T_a$ なので, $\bigcup_{a \in O} R_a \subset \bigcup_{a \in O} T_a = O$ です.

いま, 各 $b$ に対して $b \in R_b$ なので $b \in \bigcup_{a \in O} R_a$ です. よって $O \subset \bigcup_{a \in O} R_a$ です. したがって, $O = \bigcup_{a \in O} R_a$ であり, $O \in \mathcal{P}$ です.■

↑ の補題3より $\mathcal{O} \subset \mathcal{P}$ が言えました. これで $\mathcal{O}$ が $S$ から生成される最小の開集合系であることが言えます.

位相空間判定

Step.1 preorder を作る

$i \to j$ があるとき $e_{i, j} = 1$ , 他は $0$ というような行列 $e$ を作ると, これは preorder を表します.

bitset 高速化を用いると $O(n^2 m / w)$ です.

Step.2 preorder を SCC して poset (半順序集合)にする

preorder は強連結成分を縮約することで poset (半順序集合)になります.

ちなみに poset は有限 $T_0$ 位相空間と一対一対応があります.

ここは SCC をすればよいので $O(n^2)$ です.

Step.3 DFS をする

poset の要素数を $k$ とします. poset が推移律を満たす DAG であることに注目し, 位相空間の開集合の個数を重複なく数え上げます. antichain の個数を数える操作と同じだと思います.

次の DFS に従います.

$G$ の入次数 $0$ の点 $i$ を見つける. $i$ を使わない場合, $G$ から $i$ を消去する. $i$ を使う場合, $G$ から集合 $T_i$ の要素をすべて消去する.

個数が $m+1$ に達した場合, DFS をやめます.

bitset 高速化を用いると $O(n^2 m / w)$ です.

Step.4 判定

個数が $m$ なら $(\{0, 1, \cdots, n-1\}, S)$ は位相空間です. そうではない場合, 位相空間ではありません.

コード

$S$ の各要素を $i$ bit 目が $1$ のとき $i$ を含む / $0$ のとき $i$ を含まない, というようにして, $0$ 以上 $2^n$ 未満の整数で表すこととします.

#include<bits/stdc++.h>
#include<atcoder/scc>
using namespace std;
typedef long long ll;

int main(){
    int n, m; cin >> n >> m;
    vector<ll> a(m);
    for (int i=0; i<m; i++){
        cin >> a[i];
    }

    // make preorder
    vector<ll> e(n, (1LL << n) - 1);
    for (int i=0; i<n; i++){
        for (int j=0; j<m; j++){
            if (a[j] >> i & 1){
                e[i] &= a[j];
            }
        }
    }

    // scc
    atcoder::scc_graph scc(n);
    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++){
            if (e[i] >> j & 1){
                scc.add_edge(i, j);
            }
        }
    }

    vector<vector<int>> new_graph = scc.scc();
    vector<int> cores(n);
    int k = new_graph.size();
    for (int i=0; i<k; i++){
        for (int j: new_graph[i]){
            cores[j] = i;
        }
    }

    // make dag
    vector<ll> ne(k);
    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++){
            if (cores[i] == cores[j]){
                continue;
            }
            if (e[i] >> j & 1){
                ne[cores[i]] |= 1LL << cores[j];
            }
        }
    }

    for (int i=0; i<k; i++){
        ne[i] |= 1LL << i;
    }

    // dfs
    int cnt = 0;
    ll mask = (1LL << k) - 1;

    auto dfs = [&](auto self, ll state, int now) -> void {
        if (state == 0){
            cnt++;
            return;
        }
        while (!(state >> now & 1)) now++;
        // NOT USE
        self(self, state ^ (1LL << now), now + 1);
        if (cnt > m){
            return;
        }
        // USE
        self(self, state & (mask ^ ne[now]), now + 1);
        return;
    };

    dfs(dfs, mask, 0);
    
    if (cnt != m){
        cout << "No\n";
    }else{
        cout << "Yes\n";
    }
}