ICPC 2023 アジア地区予選横浜大会で、本質的にラミナーマトロイドの最小重み基を求める問題が出題されたので、その復習をしていきます。

ラミナーマトロイド

ラミナー族

集合 $E$ の部分集合族 $\mathcal{F}$ は、以下の条件を満たすときにラミナー族と呼ばれます。

任意の $E$ の部分集合 $A,B\in\mathcal{F}$ について、 $A\backslash B,\;B\backslash A,\;A\cap B$ の少なくとも 1 つが空集合である。

ラミナー族は競技プログラミングでも馴染みの深い概念です。例えば、頂点集合を $V$ とする根付き木について、頂点 $v$ を根とする部分木に含まれる頂点集合を $T(v)\subseteq V$ とすれば、 $V$ の部分集合族 $\left\{T(v)\mid v\in V\right\}$ はラミナー族となります。

ラミナーマトロイド

集合 $E$ とそのラミナー族 $F$ について、容量関数 $c:\mathcal{F}\to\mathbb{Z}_{\geq 0}$ があるとします。このとき、 $E$ の部分集合族 $\mathcal{I}$ を

$\displaystyle \mathcal{I}:= \left\{X\subseteq E\mid\forall A\in\mathcal{F},\; |X\cap A|\leq c(A)\right\}$

と定義します。このとき、 $(E,\mathcal{I})$ は $\mathcal{I}$ を独立集合とするマトロイドになります。このように、ラミナー族とその容量関数を用いて表現できるマトロイドはラミナーマトロイドと呼ばれます。

マトロイドであることの証明*1

$\mathcal{I}$ がマトロイドの独立集合の公理、つまり以下の 3 条件を満たすことを見ていきます。

$\emptyset\in\mathcal{I}$ である。
$Y\in\mathcal{I}$ かつ $X\subseteq Y$ ならば、 $X\in\mathcal{I}$ である。
$X,Y\in\mathcal{I}$ かつ $|X|\gt|Y|$ ならば、ある $x\in X\backslash Y$ が存在して $Y\cup\{x\}\in\mathcal{I}$ である。

$c$ の非負性から、条件 (1),(2) は明らかに成立します。

条件 (3) が成立することを確認するために、 $X,Y\in\mathcal{I}$ が $|X|\gt |Y|$ を満たすとします。 $\mathcal{A}:=\{E\},\;A:=E$ と初期化し、以下の操作を繰り返し行います。

$\mathcal{F}_A:=\left\{Z\in\mathcal{F}\mid Z\subseteq A\right\}$ とする。 $A\in\mathcal{F}_A$ または $\mathcal{F}_A\subseteq\{\emptyset\}$ のときは操作を終了する。
そうでない場合は $\mathcal{F}_A$ の極大集合を $A_1,\dots,A_t$ とし、 $A_0:=A\backslash(A_1\cup\dots\cup A_t)$ とする。 $\mathcal{F}$ がラミナー族であることより $A_0,\dots,A_t$ は互いに交わらないことが保証される。 $|X\cap A|\gt |Y\cap A|$ なので、 $|X\cap A_i|\gt |Y\cap A_i|$ を満たす $i\in \{0,\dots,t\}$ が存在する。この $i$ を用いて $\mathcal{A}\leftarrow\mathcal{A}\cup\{A_i\},\;A\leftarrow A_i$ と更新する。

1 回の操作で $A$ の要素数は必ず小さくなるので操作は有限回で終了します。また、操作終了後の $A$ は $|X\cap A|\gt |Y\cap A|$ を満たすので、 $x\in(X\backslash Y)\cap A$ を満たす $x$ を取ることができます。この $x$ について $Y\cup\{x\}\in\mathcal{I}$ となります。

実際、 $|(Y\cup\{x\})\cap B|\gt|Y\cap B|$ を満たす $B\in\mathcal{F}$ は $B\in\mathcal{A}$ であるので、 $|(Y\cup\{x\})\cap B|\leq|X\cap B|\leq c(B)$ が成り立ちます。

これで条件 (3) の成立も言えたので、 $(E,\mathcal{I})$ がマトロイドになっていることが確認できました。

出題例

ICPC 2023 アジア地区予選横浜大会 J 問題が、ラミナーマトロイドの最小重み基を求める問題となっていることを見ていきます。考察をすると、元の問題が以下の問題と等価であることがわかります。

頂点集合を $V$ とする根付き木と $f\in\mathbb{N}^V$ が与えられる。頂点 $v$ を根とする部分木に含まれる頂点集合を $T(v)\subseteq V$ とするとき、以下の値を求めよ。

$\min\left\{\sum_{v\in V} f_vx_v^2\;\middle|\;\begin{array}{l} x\in\mathbb{Z}_{\geq 0}^V\\ \sum_{v\in V}x_v = |V|\\ \sum_{u\in T(v)}x_u\leq|T(v)|\;(\forall v\in V) \end{array}\right\}$