ei1333の日記

ぺこい

木幅が2以下のグラフの木分解と動的計画法

なんだこのよくわからんたいとる

卒論を書いているだけだと精神衛生上よくないので, つらくなったときに書いていました.

木幅・木分解についてと, 木分解上で動的計画法をするアルゴリズムについて解説します.

例えば最大独立集合は木幅 {t} として {O(2^{t+1} t^2 V)} とかで解けます.

また, 一般に木分解を求めるのはヒューリスティックなどをする必要があり最悪ケースを考慮する競プロ的には難しい(難しくなかったら教えてください)ので一般グラフに対する木分解はどこかの記事や本などを読んで頂くこととして, ここでは有用そうな木幅が {2} 以下のグラフの木分解について解説します. ちなみに木幅が {2} 以下のグラフは カクタス, なもりグラフ, 外平面グラフなどの, Series-parallel graph(直並列グラフ) などを含みます. カクタスみたいなのはこどふぉでよくみるかも.

グリッドグラフの問題

突然木分解・木幅といわれても, イメージがしづらいと思うので, まずはグリッドグラフ上での問題を考えてみます.

より形式的には次の問題を考えます.

{H} 行 {W} 列のマス目があって {i} 行 {j} 列目のマスを {(i, j)} で表します.
各マスには重みが割り当てられていて {(i, j)} の重みは {A_{i,j}} です.
辺で隣接するマス目を同時に選ばないという条件下で, 選んだマスの重みの和の最大値を求めてください.

bitdp で解きたくなると思います.

f:id:ei1333:20200212030623p:plain

をします. dp[bit][i][j] := 覚えているマスたちの状態が bit で, マス {(i, j)} を決めようとしているときの max

全体の計算量は {O(2 ^W HW)} です.

グリッドグラフの木幅は {W} です. よくみると, 今回設計しようとしているアルゴリズム {O(2 ^{t + 1} t^2 V)} と似たような計算量になっています. 実は, この bitdp の考え方とほとんど同じ考え方で木幅に依存したアルゴリズムを設計できます.

木幅・木分解について

木幅および木分解について簡単に書きます.

定義

ある無向グラフ {G=(V,E)} の木分解とは, 木 {T=(I,F)} であって以下を満たすものをいいます.

  • 各頂点 {i \in I} は, {V} のある部分集合 {X_i \subseteq V} に対応する ( {X_i} をバッグと呼ぶ)
  • すべての辺 {\{u, v\} \in E} について, {u, v \in X_i} であるバッグ {X_i} が存在する
  • すべての頂点 {v \in V} について, {v} を(その頂点に対応するバッグに)含む頂点たちは {T} で連結

結構柔軟なので, 木分解は一意ではなくていろいろ考えられます. 考えられるすべての木分解のうち, 最大のバッグの頂点数が最小値となる木分解をとってきて, (最大のバッグ)-1 が {G} の木幅 {t} です.

特殊なグラフの木幅

木なら木幅 {t = 1} です(必要十分条件). 平面グラフなら {t = O(\sqrt V)}, 完全グラフなら {t = V - 1}, {N \times N} のグリッドグラフなら {t = N} です.

外平面グラフ, なもりグラフ(Pseudoforest), カクタス(Cactus Graph) は {t \le 2} です. 競プロ的にはこれが多いのかも.

(想定クソリプ: {V \leq 1})

タイトルの通り, この記事では {t \le 2} のグラフに絞って考えることにします( {t \gt 2} のときにも同様に適用可能ですが, 一般のグラフの木幅が最小の木分解の構成は NPなので... グリッドグラフなど特殊なグラフだとはやく構成できます).

木幅が {2} 以下であることの認識

木幅が {2} 以下であるか否かは線形時間で判定出来ます.

常に多重辺は削れるだけ削っておくことにします.

次の操作を繰り返して {2} 頂点からなるグラフ {s, t} に {1} 本の辺 {\{s, t\}} がある状態にできるとき木幅が {2} 以下です.

  • 次数が {1} の頂点 {w} をみつけて, 頂点 {w} と辺 {\{s, w\}} を削除する操作
  • 次数が {2} の頂点 {w} をみつけて, 辺 {\{s, w\}, \{w, t\}} と頂点 {w} を削除し辺 {\{s, t\}} を追加する操作

次数が {1, 2} の頂点が複数ある場合がありますが, どのような順番で操作しても認識結果は変わらないことがちょっと考えるとわかるので, 適当にやればいいです.

{2} 頂点の状態にできたらそのグラフは木幅 {2} 以下で, できなかったらそうではありません. (想定クソリプ: {V \leq 1})

この判定は, 次数が {2} 以下の頂点を適切に管理しながら, いい感じにねねちゃんをすると {O(V + E)} でできるとおもいます.

木幅が {2} 以下の木分解の構成

基本的には認識アルゴリズムと同様に, 次数 {2} 以下の頂点を縮約していけばよいです.

え～自分で作図するのはだるいので, 先人たちが作ってくれた図を貼っておきます...(2012/Practice/模擬国内予選/講評 - ICPC OB/OG の会 姉妹港解説より)

f:id:ei1333:20200208200912p:plain

を最後まで続けます.

がんばって実装をしてみました. グラフは連結であることを仮定しています. 木幅が {2} より大きいとき, 空の tree が返されます. 根は {0} になります. バグっていたらごめんなさい.　(2/26 バグっていたので直しました. まだバグっていたらごめんなさい.)

struct DecompNode {
  vector< int > bag, child;

  DecompNode() = default;
};

struct TreeDecomposition {

  vector< vector< int > > g;

  explicit TreeDecomposition(int V) : g(V) {}

  void add_edge(int a, int b) {
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }

  vector< DecompNode > build() {
    const int N = (int) g.size();

    vector< int > used(N, -1), deg(N);
    queue< int > que;
    for(int i = 0; i < N; i++) {
      deg[i] = (int) g[i].size();
      if(deg[i] <= 2) que.emplace(i);
    }

    vector< set< int > > exists(N);
    for(int i = 0; i < N; i++) {
      for(auto &j : g[i]) {
        if(i < j) exists[i].emplace(j);
      }
    }

    vector< DecompNode > ret;
    ret.emplace_back();
    while(!que.empty()) {
      int idx = que.front();
      que.pop();
      if(deg[idx] > 2 || used[idx] != -1) continue;

      DecompNode r;
      r.bag.emplace_back(idx);
      int u = -1, v = -1;
      for(auto &to : g[idx]) {
        if(used[to] == -1) {
          (u == -1 ? u : v) = to;
          r.bag.emplace_back(to);
        } else if(used[to] >= 0) {
          r.child.emplace_back(used[to]);
          used[to] = -2;
        }
      }

      if(u == -1) {

      } else if(v == -1) {
        --deg[u];
      } else {
        if(u > v) swap(u, v);
        if(!exists[u].count(v)) {
          g[u].emplace_back(v);
          g[v].emplace_back(u);
          exists[u].emplace(v);
        } else {
          --deg[u];
          --deg[v];
        }
      }

      for(auto &to : g[idx]) {
        if(deg[to] <= 2) que.emplace(to);
      }

      used[idx] = (int) ret.size();
      deg[idx] = 0;
      ret.emplace_back(r);
    }
    for(int i = 0; i < N; i++) {
      if(deg[i] > 0) return {};
    }
    ret.front() = ret.back();
    ret.pop_back();
    return ret;
  }
};

Nice Tree-decomposition

日本語だと素敵な木分解とも呼ばれるようです. 素敵ですね.

最大独立集合などのDPをするときに, 普通の木分解をするのはたぶん面倒です.

DPするときには, Nice Tree-decomposition 上でするのが一般的らしいです. みんなだいすきな抽象化とか考えるときもおそらくこっちのほうが楽です.

すべての木分解上のノード {i} が次のいずれかに属するときその木分解を Nice Tree-decomposition と言います.

  • leaf: 葉であり, {|X_i| = 1}
  • introduce: 1つの子 {j} を持ち {X_i = X_j \cup \{v\}} （ {X_j} に頂点 {v} を加えたもの)
  • forget: 1つの子 {j} を持ち {X_i = X_j \setminus \{v\}} （ {X_j} から頂点 {v} を取り除いたもの)
  • join: 2つの子 {j, k} を持ち {X_i = X_j = X_k}

で、常に幅 {t} の木分解から幅 {t} の Nice Tree-decomposition を {O(t^2 V)} で得ることができます. 頑張って得てください.

頂点 {i} が {3} つ以上の子を持っている場合, 新たにバッグ {X_i} を複製して頂点 {j} を作って, {i} の親を {j} とします. {j} の子に頂点 {i} のある {1} つの子を追加して {i} からその子を削除することを繰り返せばよいです.

頂点 {i} が {2} つの子 {j, k} を持っていて join の条件を満たさない場合, 新たにバッグ {X_i} を複製して頂点を作って, {i} と {j, k} の間に作った頂点を挿入します. この操作を繰り返し適用することで {2} つの子を持つ頂点の条件についてはすべて満たすようにできます.

頂点 {i} が {1} つの子 {j} を持っていて, introduce と forget の条件を満たさない場合, {X_i} から {X_j} に条件を満たすように変形するようなバッグの列を構成して {i} と {j} の間にそれらの頂点を挿入すればよいです. 構成する列の長さを最小になるようにすると, その長さは 2*(木分解の幅) くらいなので頂点の個数はあまり増えません.

頂点 {i} の子の個数が {0} で leaf の条件を満たさない場合も適当に {1} 個ずつ減らしていけばよいです.

実装例はこちらです.

void to_nice(vector< DecompNode > &g, int root = 0) {

  for(auto &p : g) {
    sort(p.bag.begin(), p.bag.end());
  }

  stack< int > st;
  st.emplace(root);

  while(!st.empty()) {
    int idx = st.top();
    st.pop();

    // join
    while(g[idx].child.size() > 2) {
      DecompNode r;
      r.child.resize(2);
      r.child[0] = g[idx].child.back();
      g[idx].child.pop_back();
      r.child[1] = g[idx].child.back();
      g[idx].child.pop_back();
      r.bag = g[idx].bag;
      g[idx].child.emplace_back((int) g.size());
      g.emplace_back(r);
    }

    if(g[idx].child.size() == 2) {
      for(auto &ch : g[idx].child) {
        if(g[ch].bag != g[idx].bag) {
          DecompNode r;
          r.child = {ch};
          r.bag = g[idx].bag;
          ch = (int) g.size();
          g.emplace_back(r);
        }
      }
    }

    // introduce / forget
    if(g[idx].child.size() == 1) {
      int &ch = g[idx].child[0];

      vector< int > latte, malta;
      set_difference(g[idx].bag.begin(), g[idx].bag.end(),
                     g[ch].bag.begin(), g[ch].bag.end(),
                     back_inserter(latte));
      set_difference(g[ch].bag.begin(), g[ch].bag.end(),
                     g[idx].bag.begin(), g[idx].bag.end(),
                     back_inserter(malta));
      if(latte.size() + malta.size() > 1) {
        DecompNode r;
        r.child = {ch};
        r.bag = g[idx].bag;
        if(!latte.empty()) {
          r.bag.erase(find(r.bag.begin(), r.bag.end(), latte.back()));
        } else {
          r.bag.emplace_back(malta.back());
        }
        ch = (int) g.size();
        g.emplace_back(r);
      }
    }

    // leaf
    if(g[idx].child.empty()) {
      if(g[idx].bag.size() > 1) {
        DecompNode r;
        r.bag = g[idx].bag;
        r.bag.pop_back();
        g[idx].child.emplace_back((int) g.size());
        g.emplace_back(r);
      }
    }

    for(auto &ch : g[idx].child) {
      st.emplace(ch);
    }
  }
}

Nice Tree-decomposition 上のDP

先ほどのグリッドグラフの問題を解くために使った bitdp は, 次の {2} 種類のステップに分割できます.

  • 頂点を覚えて更新: マス {(i, j)} について埋めたときに, マス {(i, j)} の使用の有無の情報は, 今後の dp の計算に使うため, 新たに覚える必要があります. 今覚えている頂点の情報を使って, マス {(i, j)} で dp テーブル を更新し, マス {(i, j)} の使用の有無の情報を覚えます.
  • 頂点を忘れる: マス {(i, j)} について埋めたときに, マス {(i - 1, j)} の使用の有無の情報は, 今後の dp の計算に使わないため, 忘れてもよいです.

これらは, さっきの木分解で定義した用語と対応しています. 具体的には, 頂点 {X_i} が leaf or introduce のとき頂点を覚えて更新する, forget のとき忘れる です. {X_i} が join のときは, bitdpでは使わなかった新しい操作が必要です. まあそんな難しくないんですが...

join は2つの計算結果を重ねる操作(?)です. 多分よくわからない（僕もわからない）と思うので, 各操作をイメージを作図してみました　えらい.

  • leaf, introduce: 頂点を覚えて更新 f:id:ei1333:20200206015410p:plain

木分解の性質より, 忘れた頂点と追加した頂点を結ぶ辺は存在しません.

  • forget: 頂点を忘れる

f:id:ei1333:20200206015744p:plain

う

  • join: 2つの計算結果を重ねる

f:id:ei1333:20200206022805p:plain

木分解の性質より, 忘れた頂点①と忘れた頂点②の積集合は常に {\emptyset} で, ①の頂点と②の頂点を結ぶ辺も存在しません. また, Nice Tree-decomposition の性質より2つの覚えている頂点は全く同じです.

これらの性質と, 覚えている頂点は常に木幅+1以下であることを利用すると, なんかいい感じにいろいろなDPができちゃいます. すごい.

最大独立集合

leaf, join, forget, introduce を使って, 最大独立集合を求めてみます.

dp[idx][bit]:= (NicetTreeDecompositionの)頂点 idx の部分木で, 覚えている頂点を使ったかどうかの状態が bit(使った時1, 使ってない時0) のときの最大値とします.

  • leaf, introduce: 追加した頂点を {v} とします. {v} と, 覚えている頂点のうち使った頂点と結ばれていたら, その頂点は使えません. それ以外のとき使えます.
  • forget: まあこれはふつうにわすれます 忘れた頂点を {v} として {v} を使った場合と使っていない場合の max をとります.
  • join: idxの2つの子を {s,t} とします. dp[idx][bit] = dp[s][bit]+dp[t][bit]-pop_count(bit)です. bitの分だけ2回たされるので, 1回ぶんひきます.

頂点数が {O(t V)} で, いずれの遷移の計算量も {O(t)} なので, 全体の計算量は {O(2^{t+1} t^2 V)} です.

実装はしていません笑

AOJ2405：姉妹港

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2405

数え上げも出来ます. 完全マッチングの個数を求める問題です. 外平面グラフなのでできるやつです.

dp[idx][bit]:= (NicetTreeDecompositionの)頂点 idx の部分木で, 覚えている頂点を既にマッチングさせたかどうかの状態が bit(使った時1, 使ってない時0) のときの個数とします. 適当にやると, bit内の頂点同士でマッチングさせる場合に係数がおかしくなりそうですが, 頂点を forget するタイミングでマッチングさせるみたいなことをするといい感じに出来ます.

  • leaf, introduce: 頂点をくわえるだけで, 特にマッチングはさせません.
  • forget: 忘れる頂点を {v} とします. {v} が既にマッチングしていれば普通に忘れて, マッチングしていなければ {v} の他で覚えてる他の {1} 頂点とマッチングさせて忘れます.
  • join: idxの2つの子を {s,t} とします. ううううう(説明飽きちゃったので, 考えるか下のコードをみてください

計算量はよくわかりません

int main() {
  int N, M;
  while(cin >> N >> M, N) {
    TreeDecomposition td(N);
    set< pair< int, int > > edges;
    for(int i = 0; i < N; i++) {
      td.add_edge(i, (i + 1) % N);
      edges.emplace(minmax(i, (i + 1) % N));
    }
    for(int i = 0; i < M; i++) {
      int a, b;
      cin >> a >> b;
      --a, --b;
      td.add_edge(a, b);
      edges.emplace(minmax(a, b));
    }

    if(N % 2) {
      cout << 0 << endl;
      continue;
    }

    auto t = td.build();
    to_nice(t);
    vector< vector< modint > > dps(t.size());
    vector< int > buff(N), buff2(N, -1);
    MFP([&](auto rec, int idx) -> void {

      auto &ch = t[idx].child;
      auto &bag = t[idx].bag;

      for(auto &to : ch) rec(to);
      vector< modint > dp(1 << bag.size());

      if(ch.empty()) { // leaf
        dp[0] = 1;
      } else if(ch.size() == 2) { // join
        for(int i = 0; i < dp.size(); i++) {
          for(int j = 0; j < dp.size(); j++) {
            if((i & j) == 0) dp[i | j] += dps[ch[0]][i] * dps[ch[1]][j];
          }
        }
      } else {
        auto &ch_bag = t[ch[0]].bag;
        auto &ch_dp = dps[ch[0]];

        for(int i = 0; i < bag.size(); i++) {
          buff[bag[i]] = 1 << i;
          buff2[bag[i]] = idx;
        }

        if(ch_bag.size() + 1 == bag.size()) { // introduce
          for(int i = 0; i < ch_dp.size(); i++) {
            int bit = 0;
            for(int j = 0; j < ch_bag.size(); j++) {
              if((i >> j) & 1) bit |= buff[ch_bag[j]];
            }
            dp[bit] = ch_dp[i];
          }
        } else { // forget
          int v = -1;
          for(int i = 0; i < ch_bag.size(); i++) {
            if(buff2[ch_bag[i]] != idx) v = ch_bag[i];
          }
          vector< int > ok_match(bag.size());
          for(int i = 0; i < bag.size(); i++) {
            ok_match[i] = edges.count(minmax(bag[i], v));
          }

          for(int i = 0; i < ch_dp.size(); i++) {
            int bit = 0;
            bool v_use = false;
            for(int j = 0; j < ch_bag.size(); j++) {
              if((i >> j) & 1) {
                if(v != ch_bag[j]) bit |= buff[ch_bag[j]];
              } else {
                if(v == ch_bag[j]) v_use = true;
              }
            }
            if(v_use) {
              for(int j = 0; j < bag.size(); j++) {
                if((bit >> j) & 1) continue;
                if(ok_match[j]) dp[bit | (1 << j)] += ch_dp[i];
              }
            } else {
              dp[bit] += ch_dp[i];
            }
          }
        }
      }
      dps[idx].swap(dp);
    })(0);
    auto &dp = dps[0];
    cout << dp.back() << endl;
  }
}

TODO

抽象化しないとやってられないきがする

joinやforgetでどの頂点を覚える/忘れるかとかも持たせると楽なのかも わからん

誰か氏～～～　抽象化たのむ～～～

さいごに

木幅を使ったDP1000問出題されてくれ

はてなスター

おもしろ要素がなくてごめんなさい

じょえ～

う　し　た　ぷ　に　き　あ　く　ん　笑

ねんね

ソースコード含めると卒論より字数がおおいけど