FIT2022（第 21 回情報科学技術フォーラム）A-014
マトロイド判定問題に対する ZDD を用いた解法とその評価
ZDD-Based Methods for the Matroid Recognition Problem and Their Evaluation
江本 洸海1）

岩政 勇仁1）

湊 真一1）

Hiromi Emoto Yuni Iwamasa Shin-ichi Minato
1 はじめにマトロイドは、ベクトル空間における線形独立性を抽象化したある性質を満たす有限集合とその部分集合族の組であり、Whitney [1] と Nakasawa [2] によってそれぞれ独立に導入された。部分集合族は課す公理系によって名称が変わり、独立集合族や基族などとよぶ。マトロイドは貪欲法を用いて解ける組合せ最適化問題の背後に潜む数理構造であり、離散構造上の凸性をなす概念である [3]。そのため組合せ最適化分野において重要な役割を果たしているマトロイドが、どのような数理構造から現れるかを考えることは重要である。
本研究では、有限集合 𝐸 とその部分集合族 ℬ ⊆ 2𝐸 の組 (𝐸, ℬ) が何らかの形で与えられたとき、(𝐸, ℬ) がマトロイドをなすか否か判定する問題（マトロイド判定問題）について考える。特に ℬ が 𝐸 上で基族をなすか否かについて考える。この問題に対しては、これまで(𝐸, ℬ) が公理系を満たすか否か愚直に調べるという単純2な解法や、𝑂(|𝐸| |ℬ|) 時間で判定できる解法が提案されている [4]。基族以外の公理系を前提とした判定も存在する [5]。
しかしマトロイド判定問題を実用的に扱った研究は少ない。𝐵 のサイズが 𝐸 のサイズに対して指数的に大きくなりうる、すなわち入力サイズが大きくなりやすいことが理由の一つである。そこでゼロサプレス型二分決定
グラフ (ZDD) によって問題を扱いやすくする。ZDD はMinato [6] によって導入されたデータ構造であり、集合族を圧縮して一意に表現する。
以上を踏まえ、本研究では、マトロイド判定問題に対する ZDD を用いた解法を二つ提案し、計算機実験によって性能を評価する。二つの解法ではそれぞれ ZDDの構造に基づいた再帰関数や、ZDD の特徴である集合演算を主に用いており、ともに ZDD の圧縮効果を活かした解法と言える。マトロイドを判定できれば、さらにマトロイドを前提とした操作や判定を適用できる。たとえばマトロイドの重要な部分クラスであるグラフ的マトロイドを判定できる [7]。

2 準備
本稿では集合 𝑋, 𝑌 に対して、{𝑥 ∈ 𝑋 ∶ 𝑥 ∉ 𝑌} を 𝑋−𝑌と表す。単一の要素 𝑒 に対して、𝑋 ∪ {𝑒}, 𝑋 − {𝑒} をそれぞれ 𝑋 ∪ 𝑒, 𝑋 − 𝑒 と表す。

2.1 マトロイド
マトロイド [1, 2] はある性質を満たす有限集合とその部分集合族の組であり、具体的には定義 2.1 により定められる。なお記号の用法などは Oxley [8] に従う。
定義 2.1. 有限集合 𝐸 とその部分集合族 ℬ ⊆ 2𝐸 が以下をすべて満たすとき、組 (𝐸, ℬ) をマトロイドとよぶ。

1） 京都大学大学院情報学研究科
Informatics, Kyoto University

Graduate School of(B1) ℬ ≠ ∅ が成り立つ。
(B2) 任意の 𝐵1 , 𝐵2 ∈ ℬ, 𝑒 ∈ 𝐵1 に対して、(𝐵1 − 𝑒)∪𝑓 ∈ ℬを満たす 𝑓 ∈ 𝐵2 が存在する。
(B3) 𝐵1 ⊆ 𝐵2 を満たす任意の 𝐵1 , 𝐵2 ∈ ℬ に対して、
𝐵1 = 𝐵2 が成り立つ。
このとき 𝐸 を台集合、ℬ を基族とよぶ。
基族には同値な特徴づけが複数存在する。たとえば定義 2.2 によっても基族を定義できる。
定義 2.2. 有限集合 𝐸 とその部分集合族 ℬ ⊆ 2𝐸 が (B1)と以下をすべて満たすとき、組 (𝐸, ℬ) をマトロイドとよぶ。
(B4) 任意の 𝐵1 , 𝐵2 ∈ ℬ, 𝑥 ∈ 𝐵2 −𝐵1 に対して、(𝐵1 − 𝑦)∪𝑥 ∈ ℬ を満たす 𝑦 ∈ 𝐵1 − 𝐵2 が存在する。
台集合 𝐸 上の基族 ℬ に対し、ℐ ≔ {𝐼 ⊆ 𝐸 ∶ ∃𝐵 ∈ℬ, 𝐼 ⊆ 𝐵} と定めた ℐ を独立集合族とよぶ。実は ℐ が有限集合 𝐸 上で独立集合族をなすことと、𝐸 の部分集合族ℐ ⊆ 2𝐸 が以下をすべて満たすことは同値である。
(I1) ∅ ∈ ℐ が成り立つ。
(I2) 任意の 𝐼 ∈ ℐ, 𝐼 ′ ⊆ 𝐸 に対して、𝐼 ′ ⊆ 𝐼 ならば 𝐼 ′ ∈ ℐが成り立つ。
(I3) 部分集合 𝑋 ⊆ 𝐸 に対して、ℐ|𝑋 ≔ {𝐼 ∈ ℐ ∶ 𝐼 ⊆ 𝑋} とおく。任意の 𝑋 ⊆ 𝐸 に対して、半順序集合 (ℐ|𝑋, ⊆)における任意の極大元 𝐼1 , 𝐼2 ∈ ℐ|𝑋 は |𝐼1 | = |𝐼2 | を満たす。
独立集合族 ℐ ⊆ 2𝐸 と部分集合 𝑋 ⊆ 𝐸 に対して、ℐ|𝑋
は 𝑋 上で独立集合族をなす。マトロイド (𝑋, ℐ|𝑋) を 𝑋への制限とよぶ。半順序集合 (ℐ|𝑋, ⊆) の極大元となる集合の要素数を 𝑋 のランク 𝑟(𝑋) とよぶ。これは (I3) より一意に定まる。本稿では独立集合族 ℐ における 𝑋 のランクを 𝑟ℐ (𝑋) と表す。また (𝑋, ℐ|𝑋) の基の一つを 𝐵𝑋 とおくと、{𝐼 ⊆ 𝐸 − 𝑋 ∶ 𝐼 ∪ 𝐵𝑋 ∈ ℐ} は 𝐸 − 𝑋 上で独立集合族をなす。マトロイド (𝐸 − 𝑋, {𝐼 ⊆ 𝐸 − 𝑋 ∶ 𝐼 ∪ 𝐵𝑋 ∈ ℐ})
を 𝐸 − 𝑋 への縮約とよぶ。
無向グラフ 𝐺 について、枝集合を 𝐸(𝐺)、森をなす𝐸(𝐺) の部分集合の集まりを ℐ ⊆ 2𝐸(𝐺) とおくと、ℐ は𝐸(𝐺) 上で独立集合族をなす。これをグラフ的マトロイドとよぶ。
半順序集合 (𝑆, ≤)、部分集合 𝑆 ′ ⊆ 𝑆 について、任意の𝑠 ∈ 𝑆, 𝑠′ ∈ 𝑆 ′ に対して 𝑠 ≤ 𝑠′ ならば 𝑠 ∈ 𝑆 ′ が成り立つ
とき、𝑆 ′ を (𝑆, ≤) の下方集合とよぶ。特に (I2) を満たす 𝐸 の部分集合族は半順序集合 (2𝐸 , ⊆) の下方集合である。本稿では下方集合とよぶとき、べき集合と包含関係についてのものとする。
有限集合上の集合族 ℱ について、𝐹1 ⊆ 𝐹2 を満たす任意の 𝐹1 , 𝐹2 ∈ ℱ に対して 𝐹1 = 𝐹2 が成り立つとき、ℱ をclutter とよぶ。(B3) または補題 2.3 より基族は clutterである。
補 題 2.3 ([1, Theorem 6]). ℬ を 基 族 と お く。任 意 の𝐵1 , 𝐵2 ∈ ℬ に対して、|𝐵1 | = |𝐵2 | が成り立つ。

127
第 1 分冊Copyright © 2022 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.

FIT2022（第 21 回情報科学技術フォーラム）2.2 ゼロサプレス型二分決定グラフ

2ゼロサプレス型二分決定グラフ (ZDD) [6] は二分決定グラフの派生形であり、集合族を表す。節点のラベル 𝑥は集合の要素を表し、それぞれ集合に 𝑥 を含むか含まないかを表す 1-枝、0-枝という有向枝が各節点に存在する。ZDD 𝑃 の 0-枝、1-枝の行き先である ZDD をそれ
ぞれ 𝑃0 , 𝑃1 と表す。ただし特別な節点として 0-終端節点と 1-終端節点が存在し、これら終端節点にはラベルや0-枝、1-枝が存在しない。このような節点と有向枝からなるグラフは有向非巡回グラフをなし、根節点から 1終端節点までの有向パス一つが集合族に属する集合一つに対応する。ZDD 𝑃 の根節点のラベルを 𝑃.top と表す。
ZDD 内の任意の節点を根とする部分グラフも ZDD となり、これを部分 ZDD とよぶ。
ZDD の特徴はその圧縮規則にある。まず根節点から終端節点までの有向パスに現れる要素の順序を一定にする。すなわち現れる要素を並べた列はすべてある要素列
𝑥𝑛 , 𝑥𝑛−1 , … , 𝑥1 , 𝑥0 (𝑛 ∈ ℕ) の部分列にする。ここで 𝑥0は終端節点を表す特別なラベルとして便宜上用意したものであり、集合の要素は表さない。𝑖, 𝑗 ∈ {0, 1, … , 𝑛} に対して、𝑥𝑖 > 𝑥𝑗 ⟺ 𝑖 > 𝑗 と定義する。次に図 1 のよ
うに冗長な節点を削除し、図 2 のように等価な節点を共有させることで圧縮する。たとえば図 3 に示す ZDD は集合族 {{𝑥1 }, {𝑥1 , 𝑥2 }, {𝑥1 , 𝑥2 , 𝑥3 }} を表す。
本稿では ZDD の節点数を終端節点以外の節点の数とする。表記として集合族と ZDD は同様に扱う。ただしZDD 𝑃 に対して、|𝑃| は集合族に属する集合の数ではな
く、𝑃 の節点数を表す。
ZDD 𝑃, 𝑄、変数 𝑥 に対して、ZDD の集合演算は

𝑃.change(𝑥) ≔ {𝑆 − 𝑥 ∶ 𝑥 ∈ 𝑆 ∈ 𝑃} ⊔ {𝑆 ∪ 𝑥 ∶ 𝑥 ∉ 𝑆 ∈ 𝑃},
𝑃.onset0(𝑥) ≔ {𝑆 − 𝑥 ∶ 𝑥 ∈ 𝑆 ∈ 𝑃},
𝑃 ⊓ 𝑄 ≔ {𝑆 ∩ 𝑇 ∶ 𝑆 ∈ 𝑃, 𝑇 ∈ 𝑄},
𝑃 △ 𝑄 ≔ {𝑆 ∈ 𝑃 ∶ ∃𝑇 ∈ 𝑄, 𝑇 ⊆ 𝑆}などがある。meet 演算 𝑃 ⊓ 𝑄 は 𝑂(|𝑃| |𝑄| ) 時間で計算
3

案した [14]。これを改善する形で Spinrad は 𝑂(|𝐸| |ℬ|)
時間で判定できる解法を提案した [4]。

3でき [9]、restriction 演算 𝑃 △ 𝑄 は 𝑂(|𝑃||𝑄| ) 時間ま2

たは 𝑂(|𝑃| |𝑄|) 時間で計算できる [10]。どちらの演算も実用上は高速である。
23 マトロイド判定問題
2.1 節で見たように、マトロイドには基族による定義や独立集合族による定義が存在する。ほかにもランク関数などさまざまな概念によるマトロイドの特徴づけが存在する [8]。どの概念を対象とするかによってマトロイド判定問題の難しさは変化する。本稿ではマトロイド判定問題を基族に限定する。
問題 3.1. 有限集合 𝐸 上の集合族 ℬ ⊆ 2 が与えられる。
ℬ は 𝐸 上で基族をなすか。
𝐸明 示 的 に 有 限 集 合 𝐸 が 与 え ら れ る 必 要 は な く、𝐸 = {𝑒 ∈ 𝐵 ∈ ℬ} とすればよい。
単純な解法として入力 (𝐸, ℬ) がマトロイドの公理系を満たすか否か愚直に調べればよい。マトロイドを扱う数学ソフトウェアではしばしばこの解法を用いている [11, 12, 13]。ℬ が非空な clutter という仮定の下で、Provan と Ball は 𝑂(|𝐸|3 |ℬ|) 時間で判定できる解法を提4 ZDD を用いた解法
本章では入力の集合族 ℬ がリストや配列などでなくZDD の形で与えられたとき、ZDD の圧縮効果を活かして問題 3.1 を解く方法を二つ提案する。集合族 ℱ を表す
ZDD を 𝑃(ℱ) と書くことにし、入力は ZDD 𝑃(ℬ) が与えられるとする。ZDD 𝑃 に対して 𝐸(𝑃) ≔ {𝑥 ∈ 𝑆 ∈ 𝑃} とおくと、有限集合 𝐸 として 𝐸(𝑃(ℬ)) を考えればよい。

4.1 再帰関数を主に用いた解法
本節の解法では補題 4.1 を用いる。補題 2.3 を用いることでこれを示せる。
補題 4.1. 有限集合 𝐸 上の集合族 ℬ ⊆ 2𝐸 に対して、ℬが 𝐸 上で基族をなす必要十分条件は (B1) と以下をすべて満たすことである。
(i) 任意の 𝐵1 , 𝐵2 ∈ ℬ に対して、|𝐵1 | = |𝐵2 | が成り立つ。
(ii) ℐ ≔ {𝐼 ⊆ 𝐸 ∶ ∃𝐵 ∈ ℬ, 𝐼 ⊆ 𝐵} とおくと、ℐ は (I3)を満たす。
問題 3.1 を解くためには (B1) と (i)–(ii) がすべて成り立つか否か調べればよい。(B1) は定数時間で判定できる。(i) は 𝑃(ℬ) を終端節点から根節点に向かって調べる
ことで、𝑃(ℬ) の節点数に比例する時間で判定できる。
以下では非空な下方集合 ℐ が (I3) を満たすか否かの判
定 CheckI3(ℐ) について考える。
ℐ = {∅} のとき、(I3) は成り立つ。ℐ ≠ {∅} のとき、部分集合 𝑋 ⊆ 𝐸(𝑃(ℬ)) が 𝑃(ℐ).top ∈ 𝑋 を満たすか否か で 場 合 分 け を 行 う。こ こ で 𝑃(ℐ)0 , 𝑃(ℐ)1 は と も に
非 空 な 下 方 集 合 で あ る こ と を 示 せ る。𝑃(ℐ).top ∉ 𝑋の と き、𝑃(ℐ).top を 含 む 集 合 は 判 定 に 影 響 し な い ため、CheckI3(𝑃(ℐ)0 ) を 調 べ れ ば よ い。𝑃(ℐ).top ∈ 𝑋の と き、半 順 序 集 合 𝑆 ≔ (𝑃(ℐ)|𝑋, ⊆), (𝑃(ℐ)1 |𝑋, ⊆) の極 大 元 に 注 目 す る と、ℐ が (I3) を 満 た す た め に は
CheckI3(𝑃(ℐ)1 ) が成り立たなければならないことを示せる。CheckI3(𝑃(ℐ)0 ), CheckI3(𝑃(ℐ)1 ) が成り立つと
き、それぞれ 𝑃(ℐ)0 , 𝑃(ℐ)1 は独立集合族であり、ℐ を独立集合族として仮定したときの 𝐸(𝑃(ℬ)) − 𝑃(ℐ).top への制限、または縮約に対応する。このとき ℐ が (I3) を満たす、すなわち 𝑟ℐ (𝑋) が存在することは、𝑃(ℐ).top を含まない 𝑆 の極大元が存在すれば 𝑟𝑃(ℐ)0 (𝑋) = 𝑟𝑃(ℐ)1 (𝑋) + 1が成り立つことと同値である。これも ZDD の根節点に注目した場合分けによって判定できるため、定理 4.2 を示せる。
定理 4.2. アルゴリズム 4.1 は非空な下方集合 ℐ が (I3)を満たすか否か調べる。ただし変数 𝑒1 , 𝑒2 に対して、
𝛿𝑒1,𝑒2 はクロネッカーのデルタである。

𝑃(ℐ) の計算には DOWNSET という演算を用いれば2よい。𝑃(ℐ) = DOWNSET(𝑃(ℬ)) は 𝑂(|𝑃(ℬ)| ⋅ 𝑁(𝑃(ℬ)) )時間で計算できる（𝑁(𝑃(ℬ)) ≔ max{|DOWNSET(𝑃 ′ )| ∶𝑃 ′ は 𝑃(ℬ) の部分 ZDD である。}）[15]。計算結果を記憶するキャッシュ [6] を用いると、𝑂(|𝑃(ℐ)|) 回 CheckI3、𝑂(|𝑃(ℐ)| ⋅ 2|𝐸(𝑃(ℬ))| ) 回 PandQMatch を呼び出す。ここで ℬ が 𝐸(𝑃(ℬ)) 上で基族をなすとき、定理 4.3 より|𝑃(ℬ)| = |𝑃(ℐ)| が成り立つ。

128
第 1 分冊Copyright © 2022 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.

FIT2022（第 21 回情報科学技術フォーラム）

𝑥3𝑥0
𝑃
図1𝑥 1
10 𝑥00𝑥2𝑥20 100 𝑥 11100

𝑃

冗長節点の削除

𝑃0𝑃0𝑃1
図2

アルゴリズム 4.1 非空な下方集合に対する (I3) の判定

Input: 非空な下方集合 ℐ を表す ZDD 𝑃(ℐ)
Output: ℐ が (I3) を満たすか。
1: function CheckI3(𝑃(ℐ))
2:
if 𝑃(ℐ) = {∅} then return true3:
return CheckI3(𝑃(ℐ)0 ) and CheckI3(𝑃(ℐ)1 ) andPandQMatch(1, 𝑃(ℐ)0 , 𝑃(ℐ)1 , 𝑃(ℐ)0 − 𝑃(ℐ)1 )Input: 𝑑 ∈ ℤ、独立集合族を表す ZDD 𝑃, 𝑄、ZDD 𝑅
Output: 任意の 𝑋 ⊆ 𝐸(𝑃) ∪ 𝐸(𝑄) ∪ 𝐸(𝑅) に対して、𝑅|𝑋 ≠ ∅ ならば 𝑟𝑃 (𝑋) − 𝑟𝑄 (𝑋) = 𝑑 が成り立つか。
4: function PandQMatch(𝑑, 𝑃, 𝑄, 𝑅)
5:
if 𝑅 = ∅ then return true6:
if ∅ ∈ 𝑅 then return 𝑑 = 0 and 𝑃 = 𝑄
7:
if 𝑅.top > 𝑃.top and 𝑅.top > 𝑄.top then8:
return PandQMatch(𝑑, 𝑃, 𝑄, 𝑅0 ∪ 𝑅1 )9:
𝑒top ← max {𝑃.top, 𝑄.top, 𝑅.top}▷ 𝑅 ≠ ∅, {∅} より 𝑒top は存在する。
10:
if not PandQMatch(𝑑,▷ 𝑒top ∉ 𝑋 のとき
if 𝑃.top = 𝑒top then 𝑃0 else 𝑃,
if 𝑄.top = 𝑒top then 𝑄0 else 𝑄,
if 𝑅.top = 𝑒top then 𝑅0 else 𝑅) then11:
return false
12:
return PandQMatch(▷ 𝑒top ∈ 𝑋 のとき
𝑑 − 𝛿𝑃.top,𝑒top + 𝛿𝑄.top,𝑒top ,if 𝑃.top = 𝑒top then 𝑃1 else 𝑃,
if 𝑄.top = 𝑒top then 𝑄1 else 𝑄,
if 𝑅.top = 𝑒top then 𝑅0 ∪ 𝑅1 else 𝑅)
定理 4.3. 台集合 𝐸 上の基族 ℬ について考える。𝑃(ℬ)の 0-枝のうち、行き先が 0-終端節点であるもののみ、その行き先が始点の 1-枝と等しくなるようにつけ替える。
この操作でできる ZDD 𝑄 は ℬ に対応する独立集合族 ℐを表し、さらに 𝑄 の節点数と 𝑃(ℬ) の節点数は等しい。
略証 𝑃(ℬ) への操作でできるグラフを 𝑄′ とおく。ただし 𝑄′ は圧縮規則の適用前とする。このとき補題 2.3 より 𝑄′ に等価な異なる節点が存在しないことを示せる。
そのため 𝑄′ = 𝑄 となり、|𝑄| = |𝑃(ℬ)| が成り立つ。
集合 𝐼 ∈ ℐ に対して、ℬ𝐼 ≔ {𝐵 ∈ ℬ ∶ 𝐼 ⊆ 𝐵} とおく。自身以外の任意の 𝐵 ∈ ℬ𝐼 に対して max {𝑒 ∈ 𝐵𝐼 ⊕ 𝐵} ∉ 𝐵𝐼（⊕ は対称差を表す）を満たすただ一つの集合 𝐵𝐼 ∈ ℬ𝐼に注目し、𝐵𝐼 を表す 𝑄 上の有向パスを 𝐷 とおく。(B4)より 𝑒 ∈ 𝐵𝐼 − 𝐼 を満たす任意の 𝑒 ∈ 𝐸 に対して、ラベル𝑒 をもつ 𝐷 上の節点は 0-枝と 1-枝の行き先が等しいこと

等価節点の共有

𝑃11𝑥1
101

図3

ZDD の例を示せる。そのため 𝐼 を表す 𝑄 上の有向パスが存在し、𝑃(ℐ) ⊆ 𝑄 が成り立つ。またつけ替えた 0-枝には始点と終点がともに等しい 1-枝が存在することに注意すると、𝑄 ⊆ 𝑃(ℐ) を示せるため、𝑄 = 𝑃(ℐ) が成り立つ。

4.2 集合演算を主に用いた解法
𝐸 ≔ {𝑒𝑛 , 𝑒𝑛−1 , … , 𝑒1 } (𝑛 ∈ ℕ) と お き、有 限 集 合 を
𝐸 + ≔ {𝑒2𝑛 , 𝑒2𝑛−1 , … , 𝑒𝑛+1 , 𝑒𝑛 , 𝑒𝑛−1 , … , 𝑒1 } と拡張する。
𝑖, 𝑗 ∈ {1, 2, … , 2𝑛} に対して、𝑒𝑖 > 𝑒𝑗 ⟺ 𝑖 > 𝑗 と定義する。𝑒2𝑛 , 𝑒2𝑛−1 , … , 𝑒𝑛+1 を用いて、判定に必要な集合族を ZDD の形で求める。
本節の解法では補題 4.4 を用いる。定義 2.1 と補題 2.3を用いることでこれを示せる。
補題 4.4. 有限集合 𝐸 上の集合族 ℬ ⊆ 2𝐸 に対して、ℬが 𝐸 上で基族をなす必要十分条件は (B1)–(B2) と (i) をすべて満たすことである。
問題 3.1 を解くためには (B1)–(B2) と (i) がすべて成り立つかを調べればよい。4.1 節で述べたように (B1) と(i) は比較的容易に判定できる。以下では (B2) の判定について考える。
ℛ ≔ {𝐵 − 𝑒 ∶ 𝑒 ∈ 𝐵 ∈ ℬ}、𝑅 ∈ ℛ に対して 𝐶 ∗ (𝑅) ≔{𝑓 ∈ 𝐸 ∶ 𝑅 ∪ 𝑓 ∈ ℬ}、さらに 𝒞 ∗ ≔ {𝐶 ∗ (𝑅) ∶ 𝑅 ∈ ℛ} とおくと、(B2) ⟺ ∀𝐵2 ∈ ℬ, ∀𝐶 ∗ ∈ 𝒞 ∗ , 𝐵2 ∩ 𝐶 ∗ ≠ ∅を 示 せ る。𝒞 ∗ を 表 す ZDD 𝑃(𝒞 ∗ ) を 計 算 で き れ ば、∅ ∉ 𝑃(ℬ) ⊓ 𝑃(𝒞 ∗ ) が成り立つか否か調べることで (B2)を判定できる。
𝑓 ∈ {1, 2, … , 𝑛} に対して、𝑒𝑓 ∈ 𝐶 ∗ (𝑅) を満たす 𝑅 ∈ ℛを求める。(i) より 𝑅 = 𝐵2 − 𝑒𝑓 を満たす 𝐵2 ∈ ℬ が存在しなければならないため、そのような 𝑅 ∈ ℛ の集合を表す ZDD は 𝑃(ℬ).onset0(𝑒𝑓 ) ⊆ 𝑃(ℛ) となる。
これを踏まえ、𝑃(𝒞 ∗ ) を求める。初期値を 𝑃(𝒞 ∗ ) ←𝑃(ℛ) と定める。𝑒𝑓 と 𝑒𝑓+𝑛 を対応づけることで、最終的に 𝑃(𝒞 ∗ ) が {𝑅 ∪ (𝐸 + − 𝐸 で表した 𝐶 ∗ (𝑅)) ∶ 𝑅 ∈ ℛ} となるように更新する。更新中は常に 𝑃(𝒞 ∗ ) ⊓ {𝐸} = 𝑃(ℛ) が成り立つことに注意すると、(i) より定理 4.5 を示せる。
定理 4.5. アルゴリズム 4.2 は (i) を満たす ℬ が (B2) を満たすか否か調べる。

5 計算機実験
既存手法と提案手法が問題 3.1 の例題を解くまでの時間を測定した。選んだ既存手法は Provan と Ball の解法 [14] と Spinrad の解法 [4] の二つである。すべての解法は C++で実装し、ZDD のライブラリとして BDD

129
第 1 分冊Copyright © 2022 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.

FIT2022（第 21 回情報科学技術フォーラム）アルゴリズム 4.2 (i) を満たす ℬ に対する (B2) の判定

6 おわりにInput: (i) を満たす ℬ を表す ZDD 𝑃(ℬ)
Output: ℬ が (B2) を満たすか。
1: for 𝑖 = 1 to 𝑛 do
2:𝑃(ℛ𝑖 ) ← 𝑃(ℬ).onset0(𝑒𝑖 )𝑛3: 𝑃(𝒞 ∗ ) ← ⋃𝑃(ℛ𝑖 )▷ 初期値は 𝑃(ℛ) に等しい。
𝑖=1
4: for 𝑓 = 1 to 𝑛 do
5:
𝑄 ← 𝑃(𝒞 ∗ ) △ 𝑃(ℛ𝑓 )6:
𝑃(𝒞 ∗ ) ← (𝑃(𝒞 ∗ ) ⧵ 𝑄) ∪ 𝑄.change(𝑒𝑓+𝑛 )本研究では、マトロイド判定問題に対する ZDD を用いた解法を提案し、計算機実験によって既存手法と性能を比較した。提案手法は ZDD の圧縮効果を活かしたものであり、実際に圧縮効果の大きいマトロイドを入力とするときは高速に判定できることを確認した。提案手法のさらなる解析や、マトロイドを表す ZDD 特有の性質の解明が今後の課題である。

7: 𝑃(𝒞 ∗ ) ← 𝑃(𝒞 ∗ ) ⊓ {{𝑒𝑛+1 , 𝑒𝑛+2 , … , 𝑒2𝑛 }}▷ 𝒞 ∗ を取り出す。
8: 𝑃(𝒞 ) の変数を 𝑒𝑛+𝑖 → 𝑒𝑖 (𝑖 = 1, 2, … , 𝑛) と変換する。
9: return ∅ ∉ 𝑃(ℬ) ⊓ 𝑃(𝒞 ∗ )謝辞
本研究の一部は JSPS 科研費 学変 (A) 20H05964 および基盤 (A) 20H00605 の助成による。

∗100
時間 [s]

1Provan と Ball の解法
Spinrad の解法
再帰関数を主に用いた解法
集合演算を主に用いた解法

101

0.8
0.6

10−1
10−2

0.4

10−3|𝑃(ℬ)|/ ∑𝐵∈ℬ |𝐵||𝑃(ℐ)|/ ∑𝐼∈ℐ |𝐼|

10−410−5

圧縮率

1020.20235𝑛4768(a) 𝑀(𝐾𝑛 ) を入力とするとき
150
Provan と Ball の解法
Spinrad の解法
再帰関数を主に用いた解法
集合演算を主に用いた解法

0.40.2

圧縮率

0.3

時間 [s]

100|𝑃(ℬ)|/ ∑𝐵∈ℬ |𝐵||𝑃(ℐ)|/ ∑𝐼∈ℐ |𝐼|50
0.1
002468101214𝑟

161820222426(b) 𝒦𝑟 を入力とするとき

図4

問題 3.1 を解くまでの時間と ZDD の圧縮率

Package SAPPORO-Edition [16] を用いた。実験に用いた計算機の CPU は Intel(R) Xeon(R) CPU E5-2637 v3 @3.50GHz、OS は 64 ビットの Ubuntu 16.04.7 LTS であり、1.5 TB のメモリをもつ。
図 4(a) は 𝑛 ∈ {2, 3, … , 8} 頂点完全グラフ 𝐾𝑛 を基にしたグラフ的マトロイド 𝑀(𝐾𝑛 ) = (𝐸, ℬ)、図 4(b) は有限集合 𝐸 の要素数を 28 とし、|𝐵| = 𝑟 (𝑟 ∈ {2, 3, … , |𝐸| − 1})を満たす任意の 𝐵 ⊆ 𝐸 に対して 1/2 の確率で 𝐵 ∈ ℬ とする 𝒦𝑟 = (𝐸, ℬ) を入力としたときの結果である。それ
ぞれにおいて問題 3.1 を解くまでの時間と 𝑃(ℬ), 𝑃(ℐ) の圧縮率を求めた。この例題では再帰関数を主に用いた解法がほかの解法よりもおおむね高速となった。具体的には既存手法より約 2 倍高速であり、ZDD の圧縮効果が大きい 𝑀(𝐾𝑛 ) では約 10 倍高速な入力も存在した。同様に集合演算を主に用いた解法も 𝑀(𝐾𝑛 ) を入力とする例
題では高速であったが、𝐾𝑟 では既存手法よりも時間を要した。ほかの解法とは異なり、最後まで計算を打ち切らないことが理由の一つであると考えられる。

参考文献[1] Whitney, H.: On the Abstract Properties of Linear Dependence, American Journal of Mathematics, Vol. 57, No. 3, pp.
509–533 (1935).
[2] Nakasawa, T.: Zur Axiomatik der linearen Abhängigkeit. I,
Science Reports of the Tokyo Bunrika Daigaku, Section A, Vol.
2, No. 43, pp. 235–255 (1935).
[3] 室田一雄：離散凸解析，共立出版 (2001)．
[4] Spinrad, J.: Note on recognition of matroid systems, Operations Research Letters, Vol. 10, No. 6, pp. 313–314 (1991).
[5] Chaourar, B.: An improved algorithm for recognizing matroids (2019).
[6] Minato, S.: Zero-Suppressed BDDs for Set Manipulationin Combinatorial Problems, Proceedings of the 30th International Design Automation Conference, DAC ’93, NewYork, NY, USA, Association for Computing Machinery, pp.
272–277 (1993).
[7] Seymour, P. D.: Recognizing graphic matroids, Combinatorica, Vol. 1, No. 1, pp. 75–78 (1981).
[8] Oxley, J.: Matroid Theory, Oxford Graduate Texts in Mathematics, Oxford University Press, Oxford, 2 edition (2011).
[9] Knuth, D.E.: The Art of Computer Programming, Volume 4,Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams, Addison-Wesley Professional, 12th edition (2009).
[10] Okuno, H. G., Minato, S. and Isozaki, H.: On the properties of combination set operations, Information Processing
Letters, Vol. 66, No. 4, pp. 195–199 (1998).
[11] Gawrilow, E. and Joswig, M.: polymake: a framework
for analyzing convex polytopes, Polytopes—combinatorics
and computation (Oberwolfach, 1997), DMV Sem., Vol. 29,
Birkhäuser, Basel, pp. 43–73 (2000).
[12] Kingan, R. J. and Kingan, S. R.: A software system for matroids, Graphs and Discovery, DIMACS Series in Discrete
Mathematics and Theoretical Computer Science, Vol. 69,pp. 287–296 (2005).
[13] The Sage Developers: SageMath, the Sage Mathematics Software System (Version 9.6) (2022). https://www.
sagemath.org.
[14] Provan, J. S. and Ball, M. O.: Efficient Recognition of Matroid and 2-Monotonic Systems, Applications of Discrete
Mathematics, Philadelphia, SIAM, pp. 122–134 (1988).
[15] 菅谷輝治：ZDD を用いた極大集合列挙アルゴリズム，
情報処理学会研究報告，Vol. 2014-AL-148, No. 19, pp. 1–8(2014)．
[16] Minato, S.: BDD Package SAPPORO-Edition (v.20211206)(2021). https://github.com/Shin-ichi-Minato/
SAPPOROBDD.

130
第 1 分冊Copyright © 2022 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.