Chordal Graph Recognition
(graph/chordal_graph_recognition.hpp)

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

Description

Chordal graph は，任意の長さ $4$ 以上のサイクルが弧 (chord) を持つようなグラフである．

Chordal graph である必要十分条件は perfect elimination ordering (PEO) を持つことである．PEO は，頂点の列 $(v_1,v_2,\dots,v_n)$ であって，次の性質を持つものである．

• 各 $i=1,2,\dots,n$ について，$N(v_i) \cap {v_{i+1},v_{i+2},\dots,v_n}$ が clique となる (ここで， $N(v)$ は頂点 $v$ の隣接頂点の集合である)

PEO が存在するならば， Lex-BFS の逆順が PEO になっている．

Operations

• pair<bool, vector<int>> recognize_chordal_graph(vector<vector<int>> G)
  • $G$ が chordal graph か判定し，そうならば PEO を，そうでないならば長さ $4$ 以上の induced cycle を一つ返す
  • 時間計算量: $O((n+m)\log n)$

Reference

• Chordal Graph: Perfect elimination ordering -kazu0x17’s diary
• 辞書順幅優先探索Lex BFS（Chordal Graph 5回）- kazu0x17’s diary

Depends on

• Partition Refinement (data-structure/partition_refinement.hpp)
• Lexicographic BFS (graph/lex_bfs.hpp)

Verified with

• test/yosupo/chordal_graph_recognition.test.cpp

Code

#pragma once
#include <algorithm>
#include <cassert>
#include <queue>
#include <set>
#include <utility>
#include <vector>

#include "lex_bfs.hpp"

// if G is chordal, return a perfect elimination ordering
// otherwise return an induced cycle of length >= 4
std::pair<bool, std::vector<int>> recognize_chordal_graph(
    const std::vector<std::vector<int>>& G) {
    const int n = G.size();
    std::vector<std::set<int>> st(n);
    for (int x = 0; x < n; ++x) {
        for (int y : G[x]) st[x].insert(y);
    }

    auto ord = lex_bfs(G);
    std::ranges::reverse(ord);
    std::vector<int> idx(n, -1);
    for (int x = 0; x < n; ++x) idx[ord[x]] = x;

    // check if ord is a perfect elimination ordering
    for (int i = n - 1; i >= 0; --i) {
        int x = ord[i];

        // find the first neighbor z of x that appears after x
        std::pair<int, int> neighbor(n, -1);
        for (int y : G[x]) {
            if (idx[y] > i) {
                neighbor = std::min(neighbor, {idx[y], y});
            }
        }
        auto [j, z] = neighbor;
        if (j == n) continue;

        // check if N(x) - z is a subset of N(z)
        for (int y : G[x]) {
            if (idx[y] > i && y != z && !st[y].count(z)) {
                // not chordal
                // bfs from y to z using vertices after x and not in N(x)

                std::queue<int> que;
                que.push(y);
                std::vector<int> prv(n, -1);
                prv[y] = y;
                prv[z] = -1;
                for (int v : G[x]) {
                    if (v != y && v != z) {
                        prv[v] = -2;
                    }
                }
                while (!que.empty()) {
                    int v = que.front();
                    que.pop();
                    for (int u : G[v]) {
                        if (idx[u] > i && prv[u] == -1) {
                            prv[u] = v;
                            que.push(u);
                        }
                    }
                }

                assert(prv[z] != -1);

                std::vector<int> cycle;
                int v = z;
                while (prv[v] != v) {
                    cycle.push_back(v);
                    v = prv[v];
                }
                cycle.push_back(y);
                cycle.push_back(x);

                return {false, cycle};
            }
        }
    }

    return {true, ord};
}

#line 2 "graph/chordal_graph_recognition.hpp"
#include <algorithm>
#include <cassert>
#include <queue>
#include <set>
#include <utility>
#include <vector>

#line 4 "graph/lex_bfs.hpp"

#line 4 "data-structure/partition_refinement.hpp"
#include <map>
#line 7 "data-structure/partition_refinement.hpp"

class PartitionRefinement {
   public:
    PartitionRefinement() = default;
    explicit PartitionRefinement(int n) : sets(1), cls(n, 0) {
        for (int i = 0; i < n; ++i) sets[0].insert(i);
    }

    int find(int x) const { return cls[x]; }

    bool same(int x, int y) const {
        int cx = find(x), cy = find(y);
        return cx != -1 && cy != -1 && cx == cy;
    }

    bool contains(int x) const { return cls[x] != -1; }

    void erase(int x) {
        if (contains(x)) {
            sets[cls[x]].erase(x);
            cls[x] = -1;
        }
    }

    int size(int i) const { return sets[i].size(); }

    int member(int i) const {
        assert(0 <= i && i < (int)sets.size());
        return *sets[i].begin();
    }

    std::vector<int> members(int i) const {
        assert(0 <= i && i < (int)sets.size());
        return std::vector<int>(sets[i].begin(), sets[i].end());
    }

    std::vector<std::pair<int, int>> refine(const std::vector<int>& pivot) {
        std::map<int, std::vector<int>> split;
        for (auto x : pivot) {
            if (!contains(x)) continue;
            int i = cls[x];
            split[i].push_back(x);
            sets[i].erase(x);
        }
        std::vector<std::pair<int, int>> updated;
        for (auto& [i, s] : split) {
            int ni = sets.size();
            sets.emplace_back(s.begin(), s.end());
            if (sets[i].size() < sets[ni].size()) {
                std::swap(sets[i], sets[ni]);
            }
            if (sets[ni].empty()) {
                sets.pop_back();
                continue;
            }
            for (auto x : sets[ni]) {
                cls[x] = ni;
            }
            updated.push_back({i, ni});
        }
        return updated;
    }

   private:
    std::vector<std::set<int>> sets;
    std::vector<int> cls;
};
#line 6 "graph/lex_bfs.hpp"

std::vector<int> lex_bfs(const std::vector<std::vector<int>>& G) {
    const int n = G.size();
    PartitionRefinement pr(n);
    std::vector<int> prv(1, -1), nxt(1, -1);
    std::vector<int> ord;
    int k = 0;
    for (int i = 0; i < n; ++i) {
        while (pr.size(k) == 0) {
            k = nxt[k];
        }
        int x = pr.member(k);
        ord.push_back(x);
        pr.erase(x);
        std::vector<int> pivot;
        std::set<int> neighbor;
        for (int y : G[x]) {
            if (pr.contains(y)) {
                pivot.push_back(y);
                neighbor.insert(y);
            }
        }
        for (auto [s, t] : pr.refine(pivot)) {
            if ((int)prv.size() <= t) {
                prv.resize(t + 1, -1);
                nxt.resize(t + 1, -1);
            }
            if (neighbor.contains(pr.member(s))) {
                if (nxt[s] >= 0) prv[nxt[s]] = t;
                nxt[t] = nxt[s];
                prv[t] = s;
                nxt[s] = t;
            } else {
                if (prv[s] >= 0) nxt[prv[s]] = t;
                prv[t] = prv[s];
                prv[s] = t;
                nxt[t] = s;
            }
        }
        if (prv[k] != -1) k = prv[k];
    }
    return ord;
}
#line 10 "graph/chordal_graph_recognition.hpp"

// if G is chordal, return a perfect elimination ordering
// otherwise return an induced cycle of length >= 4
std::pair<bool, std::vector<int>> recognize_chordal_graph(
    const std::vector<std::vector<int>>& G) {
    const int n = G.size();
    std::vector<std::set<int>> st(n);
    for (int x = 0; x < n; ++x) {
        for (int y : G[x]) st[x].insert(y);
    }

    auto ord = lex_bfs(G);
    std::ranges::reverse(ord);
    std::vector<int> idx(n, -1);
    for (int x = 0; x < n; ++x) idx[ord[x]] = x;

    // check if ord is a perfect elimination ordering
    for (int i = n - 1; i >= 0; --i) {
        int x = ord[i];

        // find the first neighbor z of x that appears after x
        std::pair<int, int> neighbor(n, -1);
        for (int y : G[x]) {
            if (idx[y] > i) {
                neighbor = std::min(neighbor, {idx[y], y});
            }
        }
        auto [j, z] = neighbor;
        if (j == n) continue;

        // check if N(x) - z is a subset of N(z)
        for (int y : G[x]) {
            if (idx[y] > i && y != z && !st[y].count(z)) {
                // not chordal
                // bfs from y to z using vertices after x and not in N(x)

                std::queue<int> que;
                que.push(y);
                std::vector<int> prv(n, -1);
                prv[y] = y;
                prv[z] = -1;
                for (int v : G[x]) {
                    if (v != y && v != z) {
                        prv[v] = -2;
                    }
                }
                while (!que.empty()) {
                    int v = que.front();
                    que.pop();
                    for (int u : G[v]) {
                        if (idx[u] > i && prv[u] == -1) {
                            prv[u] = v;
                            que.push(u);
                        }
                    }
                }

                assert(prv[z] != -1);

                std::vector<int> cycle;
                int v = z;
                while (prv[v] != v) {
                    cycle.push_back(v);
                    v = prv[v];
                }
                cycle.push_back(y);
                cycle.push_back(x);

                return {false, cycle};
            }
        }
    }

    return {true, ord};
}

Back to top page