今回は マトロイド交差 を扱います。
マトロイド交差そのものを解くためには複雑なアルゴリズムが必要ですが、線形マトロイド交差 と呼ばれるマトロイド交差の特殊ケースでは簡単な乱択アルゴリズムがあり、複雑な実装無しに問題を解くことが出来ます。

マトロイドの定義

有限集合 \(E\) と \(E\) の部分集合の集合 \(I\) が次の条件を全て満たす時、\((E, I)\) を マトロイド と呼びます。

• (1) : \(I\) は空集合を含む。
• (2) : \(I\) が \(X\) を含むとき、\(X\) の任意の部分集合 \(Z\) もまた \(I\) に含まれる。
• (3) : \(X, Y \in I\) かつ \(\vert X \vert \lt \vert Y \vert\) ならば、ある \(e \in Y \setminus X\) が存在して \(X \cup \lbrace e \rbrace \in I\)

また、用語をいくつか定義します。

• 独立集合 : \(I\) に含まれる集合
• 従属集合 : \(E\) の部分集合であって \(I\) に含まれない集合
• 基 : 極大な独立集合
• \(X \subseteq E\) について、\(X\) の基 : \(X\) に含まれる極大な独立集合

マトロイドの定義の \(3\) 番目の条件は次の条件と等価です。(証明略)

• (3’) : \(\forall X \subseteq E\) について \(X\) の基のサイズは全て等しい。

特に \(X = E\) の場合を考えると、マトロイドの基のサイズは全て等しいことがわかります。

マトロイドの具体例

具体的なマトロイドの例をいくつか見ていきましょう。

一様マトロイド, 分割マトロイド

\(E\) を有限集合として、ある非負整数 \(r\) に対して \(E\) の部分集合の集合 \(I\) を

\[I = \lbrace X \subseteq E \mid \vert X \vert \leq r \rbrace\]

と定義すると \((E, I)\) はマトロイドとなり、これを 一様マトロイド と呼びます。
また、一様マトロイドの直和もまたマトロイドになり、 分割マトロイド と呼びます。具体的には、集合 \(E\) の分割 \(\lbrace E_1, E_2, \dots, E_k \rbrace\) および非負整数 \(r_1, r_2, \dots, r_k\) を用いて

\[I = \lbrace X \subseteq E \mid \forall i \in \lbrace 1,2,\dots, k \rbrace, \vert X \cap E_i \vert \leq r_i \rbrace\]

と定義すると \((E, I)\) はマトロイドになります。(証明については (1), (2), (3) いずれも明らかです。)

線形マトロイド

行列 \(A\) があります。\(E\) を行列 \(A\) の列集合とします。

\[I = \lbrace X \subseteq E \mid X に含まれる列は線形独立 \rbrace\]

と定義すると、\((E, I)\) はマトロイドになり、これを 線形マトロイド と呼びます。(証明については、(1), (2) および (3’) が線形代数の知識より明らかであることから確認できます。)

閉路マトロイド(グラフ的マトロイド)

\(E\) をグラフ \(G\) の辺集合とします。\(V\) を \(G\) の頂点集合として、

\[I = \lbrace X \subseteq E \mid グラフ(V, X) が閉路を含まない \rbrace\]

と定義すると、\((E, I)\) はマトロイドになり、これを 閉路マトロイド (グラフ的マトロイドとも) と呼びます。(証明については、競技プログラミングの知識から (1), (2), (3’) が容易に従います。)

マトロイド交差

マトロイド関連の問題でよく出題されるテーマがマトロイドの 交差 です。
マトロイド \((E, I_1), (E, I_2)\) に対して、\(I_1\) と \(I_2\) の交差 \(I_1 \cap I_2\) は次のように定義されます。

\[I_1 \cap I_2 = \lbrace X \mid X \in I_1, X \in I_2 \rbrace\]

そして、\(\vert X \vert\) が最大となる \(X \in I_1 \cap I_2\) を求める問題を マトロイド交差問題 と呼びます。

マトロイド交差によって記述できる問題の代表例として二部グラフの最大マッチング問題があります。部集合を \(U, V\), 辺集合を \(E\) とする二部グラフを考えます。\(U\) と \(E\) に関するマッチングの条件を考えると、各 \(u \in U\) について \(u\) に隣接する辺を 1 本以下選ぶという条件になるのでこれは分割マトロイドです。\(V\) と \(E\) についても同様に分割マトロイドとして条件が書けるので、二部グラフのマッチングは分割マトロイド同士の交差になります。他にも多くの問題がマトロイドの交差として書けることが知られています。

マトロイド交差問題は多項式時間 (解となる集合のサイズを \(r\) として \(\mathrm{O}(|E|^2 r)\) 程度) で解けることが知られていますがアルゴリズムが複雑なのでここでは割愛します。詳しく知りたい方は以下の資料を参照してください。

• 岡本吉央氏による資料, hitonanode さんによる実装例

線形マトロイド交差

マトロイド交差の特殊ケースとして 線形マトロイド交差 と呼ばれる問題があります。
線形マトロイド交差問題は、サイズだけを求めるのであれば通常のマトロイド交差よりも簡潔に解くことが出来ることが知られています。

まずは定式化を行います。行列 \(A_1, A_2\) を列数が等しい行列、\(E\) を列集合とします。すると \(A_1, A_2\) に対応する線形マトロイド \((E,I_1), (E,I_2)\) が出来て、この交差 \(I_1 \cap I_2\) が線形マトロイド交差です。

線形マトロイド交差問題について、次の命題が成り立ちます。

\(x_1, x_2, \dots, x_{\vert E \vert}\) を変数とする多項式行列 \(D, M\) を次のように置く。

\(D = \mathrm{diag}(x_e)\) (\(x_e\) を対角に並べた \(E \times E\) 行列)

\[M = A_1 D A_2^{T}\]

このとき、線形マトロイド交差問題の解のサイズは \(\mathrm{rank}(M)\) と一致する。

証明については 大城泰平氏の資料 を参照してください。

上記の命題により、線形マトロイド交差は多項式行列の rank を計算する問題に帰着します。多項式行列の rank を直接計算することは難しいですが、行列を \(\text{mod }p\) 上の行列とみなして変数に乱数を代入して得られる行列の rank を計算することで高確率で行列の rank を計算できることがわかります。(正当性は Schwarz-Zippel lemma により保証されます。) よって、\(A_1\) と \(A_2\) の行数の大きい方を \(n\), 小さい方を \(m\) として \(\mathrm{O}(nm^2)\) 程度で線形マトロイド交差問題の解のサイズが計算できることがわかりました。

線形マトロイド交差の具体例(Edmonds 行列)

線形マトロイド交差の具体例として、二部グラフの最大マッチング問題、および Edmonds 行列を取り上げます。
部集合を \(U, V\), 辺集合を \(E\) とする二部グラフの Edmonds 行列 \(N\) を次のように定義します。

\[N_{u,v} = \begin{cases} x_{u,v}& &(u,v) \in E \\ 0 & & \mathrm{otherwise} \end{cases} \]

この時、二部グラフの最大マッチングのサイズは \(\mathrm{rank}(N)\) と一致します。この事実は線形マトロイド交差を利用しなくても証明することができますが、ここでは線形マトロイド交差を経由して証明してみましょう。

先述した通り、二部グラフの最大マッチングは分割マトロイド同士の交差として書くことができますが、さらに次のように変形することで線形マトロイド交差に帰着できます。第 \(i\) 成分のみが \(1\) で他の成分が \(0\) であるような列ベクトルを \(\mathbf{e}_i\) と表します。行列 \(A_1, A_2\) を、辺 \(e=(u,v)\) に対応する \(A_1\) の列ベクトルが \(\mathbf{e}_u\), \(A_2\) の列ベクトルが \(\mathbf{e}_v\) となるように取ります。このように \(A_1, A_2\) を取ることで \(A_1, A_2\) に対応する線形マトロイド \(I_1, I_2\) の交差として二部グラフのマッチングを表現できていることが分かります。

この時の行列 \(M\) を計算すると、次のようになります。

\[ \begin{aligned} M &= A_1 D A_2^{T} \\ &= \sum_{e=(u,v) \in E} \mathbf{e}_u \mathbf{e}_v^T x_{u,v} \end{aligned} \]

このとき \(\mathbf{e}_u \mathbf{e}_v^T\) は \(uv\) 成分のみが \(1\) で他の成分は \(0\) である行列です。よって \(M\) は Edmonds 行列 \(N\) と一致することが確認できて、ここから二部グラフの最大マッチングのサイズと \(\mathrm{rank}(N)\) が一致することも言えました。

さて、線形マトロイド交差に関する内容を一通り概観しました。では、線形マトロイド交差を用いて今回の問題を解く方法を考えてみましょう。

問題の解法

今回の問題は題名にもある通り カラフル全域木 を題材とした問題です。カラフル全域木とは問題文に定義されているような全域木のことで (ただし学術的には \(A_i = 1\) のケースを指すようです)、カラフル全域木を発見する問題はマトロイド交差の典型例として知られています。

まずは簡単のため \((L, R)\) の制約がない場合にカラフル全域木の存在判定を行う問題を考えてみましょう。グラフを \((V, E)\) として、\(E_c\) を色 \(c\) の辺からなる集合とします。

\[I_1 = \lbrace X \subseteq E \mid \forall c \in \lbrace 1,2,\dots, C \rbrace, \vert X \cap E_c \vert \leq A_c \rbrace\]

\[I_2 = \lbrace X \subseteq E \mid グラフ(V, X) が閉路を含まない \rbrace\]

とおくと \((E, I_1)\) と \((E, I_2)\) はそれぞれ分割マトロイドと閉路マトロイドになります。辺集合 \(X\) がカラフル全域木をなす条件は \(X \in I_1 \cap I_2\) かつ \(\vert X \vert = N-1\) なので、\(I_2\) の基のサイズが \(N-1\) であることも合わせると、カラフル全域木の存在判定はマトロイド交差 \(I_1 \cap I_2\) に含まれる集合の最大サイズが \(N-1\) であるかを判定する問題と等価であることがわかります。

よってこの問題はマトロイド交差のアルゴリズムを用いれば多項式時間で解けることがわかりましたが、これをさらに変形することで線形マトロイド交差に帰着させましょう。すなわち、分割マトロイドと閉路マトロイドを、ともにある行列に対する線形マトロイドへと変形しましょう。
\(A_1, A_2\) を \(I_1, I_2\) に対応する \(\text{mod }p\) 係数の行列とします。(\(p\) は十分大きい素数)うまく \(A_1, A_2\) を設計して適切な対応付けを取ることを考えます。
\(A_2\) の方は比較的シンプルで、行数を \(N\) として、辺 \((u, v)\) に対応する列ベクトルを第 \(u\) 成分を \(1\), 第 \(v\) 成分を \(-1\) とする列ベクトルとすればよいことがわかります。正当性は極小な列ベクトルの従属集合が閉路をなすことから証明できます。
\(A_1\) の方はあまり明らかではないですが、「色 \(c\) の列ベクトルは \(A_c\) 個まで自由に選べる」という仕組みになるように行列を設計すればよく、すると次の手順で設計すればよいことがわかります。

• \(\sum_{c=1}^C A_c = K\) とする。\(A_1\) を \(K\) 行 \(\vert E \vert\) 列の行列とする。
• 上から \(A_1\) 行を「色 \(1\) に対応する行」, 次の \(A_2\) 行を「色 \(2\) に対応する行」、…というように行と色を対応させていく。
• 色 \(c\) の辺に対応する列ベクトルは次のように値を設定する。
  • 今見ている辺が \(n\) 番目だとする。この時、色 \(c\) に対応する行のうち \(1\) 番目の行には \(n^0\), \(2\) 番目の行には \(n^1\), \(\dots\), \(A_c\) 番目の行には \(n^{A_c-1}\) を埋める。それ以外の行は \(0\) で埋める。

\(A_1\) の正当性は ヴァンデルモンドの行列式 が非 \(0\) であることから従います。

さて、以上の方法によりマトロイド交差を線形マトロイド交差へと帰着させることができました。よって \(L, R\) の制約がない問題に関しては線形マトロイド交差の乱択アルゴリズムを適用することで問題を解くことができます。

元の問題、すなわち問題文の条件を満たす \((L, R)\) を数え上げる問題を考えてみましょう。 乱択アルゴリズムで登場する行列 \(M = A_1 D A_2^T\) の形に注目すると、色 \(c\) の辺は先に色 \(c\) に対応させた行にしか影響がないことがわかります。\(S_c = \sum_{i=1}^{c-1} A_i\) とおくと、\((L, R)\) が問題文の条件を満たすことは \(M\) の \(S_L+1\) 行目から \(S_R\) 行目までからなる部分行列の rank が \(N-1\) であることと等価です。よって、次の問題が解ければ、全ての \((L, R)\) に対して問題文の条件を満たすか判定できることがわかります。

\(c=1,2,\dots,C\) について次の問題を解け。

• \(S_c+1\) 行目から始めて下に向けて進んでいく。今まで見た行たちからなる部分行列の rank がはじめて \(N-1\) になる行はどこか？

この問題は \(c=1,2,\dots,C\) それぞれに対して基底を管理しながら行ベクトルを追加していくアルゴリズムで \(\mathrm{O}(N^2 C K)\) で解くことができます。さらに、ABC223H で出題されたテクニックを利用すれば \(\mathrm{O}(N^2 K)\) に計算量を落とすことができます。(詳細な説明は割愛します)

以上の考察を適切に実装することで、\(\sum_{c=1}^C A_c = K\) として \(\mathrm{O}(N^2 K)\) でこの問題を解くことができて、これは十分高速です。制約が緩めに設定されているので定数倍が良好な \(\mathrm{O}(N^2 C K)\) も通ります。

• これは別解ですが、一般的なマトロイド交差を解くアルゴリズムでこの問題を通すことを考えてみましょう。実は次の事実が成り立ちます。
  • 色 \(c\) ごとに極大な部分森を取り森に含まれない辺を削除しても問題の答えは変わらない。
• この事実を利用すると辺集合 \(E\) のサイズをオーダーレベルで減らすことができて、一般的なマトロイド交差アルゴリズムを使用しながら尺取り法を行うアルゴリズムが \(\mathrm{O}(N^3 C^2)\) で動作するようになります。このままでは TLE すると思いますが、定数倍高速化や効果的な枝刈りをいくつか行えば十分通る可能性があると予想しています。

Bonus

1. 今回のアルゴリズムを応用すると、重み付き線形マトロイド交差問題、すなわち \(X \in I_1 \cap I_2\) である \(X\) に対する \(\sum_{e \in X} w_e\) の最大値を求める問題を、行列の行数を \(n\)、重みの最大値を \(W\) として \(\mathrm{O}(W n^4)\) で解くことができます。考えてみましょう。

2. この問題(ネタバレ注意) は実はマトロイド交差から着想した問題で、実際に答えをとある行列の行列式として表すことができます。上記の問題をマトロイド交差を用いて解釈してみましょう。