修士論文 要旨

グラフ構造上の離散凸性に基づくネットワーク最適化アルゴリズム
数理情報学専攻 48186209 池田 基樹
指導教員

1 はじめにグラフ構造上の離散凸解析の理論は，室田らによる整(A2) この L 凸関数について，各点の最急降下方向が多項式時間で求まることを示す．

(A3) 双対問題の最適解から主問題の最適解が求まる

数格子上の離散凸解析 [5] を元にして Hirai [3] によって導入された．この理論を利用すると，ある種の多品種フロー問題やネットワーク設計問題の効率的な組合せ的アルゴリズムを設計するための指針が得られる．ただし，具体的な問題にこの枠組みを適用するためには，問題ごとにいくつかの課題を解決しなければならない．
本修士論文では，頂点容量型最小コスト自由多品種フロー問題と頂点連結度型一般化ターミナルバックアップ問題の 2 つの問題に対してこれらの課題を解決することで，前者に対する組合せ的な弱多項式時間アルゴリズムと後者に対する組合せ的擬多項式時間アルゴリズムを与えた．また，後者に関連して新しいタイプのLovász–Cherkassky 型の定理が成り立つことを示した．

2 グラフ構造上の L 凸関数
向き付け可能なモジュラグラフとは，木や木の直積，またモジュラ束や分配束（の Hasse 図）を含む広いクラスのグラフである．最近の研究で，このクラスのグラフが最小ゼロ拡張問題 [3] や効率的に解けるような多品種フロー問題 [4] の背景に存在することが分かってきた．
（良い）向き付きモジュラグラフ（OM グラフ）の各点には近傍と呼ばれる領域が定義できる．OM グラフ Gの頂点上に定義された関数 g : V (G) → R ∪ {∞} が L
凸関数とは，各点の近傍上で g がモジュラ半束上の劣モジュラ性を満たすことを言う．

L 凸関数は最急降下法と呼ばれる，各点の近傍において関数値を最小にする点（最急降下方向）への移動を繰り返すアルゴリズムで最小化できることが知られている．
最急降下法は関数の有効定義域 {u ∈ G | g(u) < ∞} のサイズに比例する時間で停止することが知られている．
多品種フローに関連するような問題の双対問題は，しばしば OM グラフ上の L 凸関数最小化問題として表すことができる．そこで，次のような一般的なアルゴリズム設計の枠組みが考えられる：(A1) 主問題の双対問題が OM グラフ上の L 凸関数最小化問題であることを示す．

平井広志 准教授

ことを示す．
またコスト付きの問題設定では，しばしば素朴な最急降下法の反復回数は擬多項式回となることがある．そこで (A4) コストスケーリングなどの手法を用いることで反復回数を改善する．以上の (A1)–(A4) を具体的な問題に対して行うことで，最急降下法に基づく組合せ的アルゴリズムが設計できる．

3 頂点容量型最小コスト自由多品種フロー問題
G = (V, E) を単純無向グラフ，S ⊆ V を頂点部分集合（ターミナル）とし，頂点容量 c : V \ S → Z+ ，辺コスト a : E → Z+ を考える．S の異なる点同士を結ぶパスを S-パスと呼び，S-パス全体の集合を P で表す．
関数 f : P → R+ で，任意の i ∈ V \ S について容量制
約 f (i) :=∑P ∈P:i∈V (P ) f (P ) ≤ c(i) を満たすものを（自由）多品種フローと言い，その中で流量∑P ∈P f (P )が最大のものを最大フローと呼ぶ．最大フローの中でコスト∑e∈E a(e)∑P ∈P:e∈E(P ) f (P ) が最小のものを求める問題が頂点容量型最小コスト自由多品種フロー問題（MNMF）である．この問題の変種に対しては，L凸関数の最急降下法に基づく効率的な組合せ的アルゴリズムが得られている [2, 4]．本研究では主に [4] の手法を拡張し，MNMF に対する初の組合せ的な弱多項式時間アルゴリズムを設計した．

MNMF については，(A1) は Hirai [4] によって既に示されており，双対問題が図 1 のような OM グラフ上のL 凸関数最小化となることが分かっている．(A2)(A3)では頂点周りの流量保存条件と頂点容量制約からなる問題を解く必要がある．Hirai [4] は頂点次数が 3 ならこの問題が劣モジュラフロー問題と呼ばれる問題に帰着できることを示した．本研究ではこれを一般化して帰着可能双劣モジュラフロー問題の理論にまとめ，次数一般の頂点でもこの問題が劣モジュラフロー問題に帰着できることを示した．また (A4) については L 凸関数の感度分析によって辺コストの微小な変化に対する近グラフ構造上の離散凸性に基づくネットワーク最適化アルゴリズム (池田 基樹)

図 1. MNMF の双対問題に現れる OM グラフ．
図 2. NTB の双対問題に現れる OM グラフ．

接定理を証明することで，最急降下法にコストスケーリングを組み合わせ，反復回数を改善した．以上により，

MNMF を解く O(m log(nAC) SF(kn, m, k)) 時間のアルゴリズムを設計した．ただし n := |V |，m := |E|，k := |S|，A := maxe∈E a(e)，C := maxi∈V \S c(i) である．また SF(n′ , m′ , η) は頂点数 n′ ，弧の数 m′ ，交換容量が η 時間で計算できるような劣モジュラフロー問題を解くアルゴリズムの計算量を表す．

ような OM グラフ上の L 凸関数最小化問題であることを示した．(A2)(A3) については頂点の分割などの議論を経ることで，巡回フロー問題に帰着できることを示した．これにより，NTB の半整数最適解を得る

O(nmU A · MF(kn, m + k 2 n)) 時間アルゴリズムを設計した．ただし U := maxi∈V \S u(i) で，MF(n′ , m′ ) は頂点数 n′ ，辺の数 m′ の最大フロー問題を解くアルゴリ
ズムの計算量を表す．NTB に関する (A4) は未だ明ら

4 頂点連結度型一般化ターミナルバックアップ問題
MNMF での設定に加えて，辺容量 u : E → Z+ と各ターミナルの需要 r : S → Z+ を考える．頂点部分集合U ⊆ V \ S と辺部分集合 F ⊆ E の組を G から削除したときに s ∈ S から S \ {s} へのパスが無くなるならば，これを s-カットと呼ぶことにする．頂点連結度型
一般化ターミナルバックアップ問題（NTB）とは，容量条件 0 ≤ x ≤ u を満たす x ∈ ZE+ で，任意の s ∈ S とs-カット (U, F ) について c(U ) + x(F ) ≥ r(s) が成り立∑つようなものから，コスト e∈E a(e)x(e) が最小の xを求める問題である．NTB が NP 困難なのか P に属するのかは未解決である．Fukunaga [1] は LP 緩和の技法に基づく 4/3-近似アルゴリズムを提案した．彼の手法は NTB の制約を x ∈ RE+ に緩和した問題に半整数最適解が存在することを利用しており，半整数最適解を得るために LP ソルバーを用いている．c ≡ ∞ の場合（辺連結度型一般化ターミナルバックアップ問題）については，Hirai [2] が多品種フロー問題との関係を利用し，Fukunaga のアルゴリズムを組合せ的に実現している．本研究では一般の NTB について半整数最適解を求める組合せ的な擬多項式時間アルゴリズムを設計した．

NTB の双対問題は，グラフの各頂点に無限 k-木の部分木を割り当てるポテンシャル配置問題になる．本
研究では (A1) のステップとして，これが図 2 に示すかになってない箇所が存在し，これを解決して弱多項式時間アルゴリズムを設計することは今後の課題である．

(A2)(A3) の証明は新しい Lovász–Cherkassky 型の定理も導く．定理の主張は，頂点容量と辺容量を満たすような最大多品種フロー f : P → R+ の流量が各 s ∈ Sについての最小 s-カットの和の 1/2 倍に等しいというものである．ただし頂点容量については f そのものが満たす必要は無く，各 s ∈ S について f を s とそれ以外のターミナルを繋ぐ S-パスの族上に制限したフローが満たせばよいものとする．このような容量条件を考える多品種フロー問題は新しく，NTB とは独立に興味深いものである．本定理は現状，NTB の議論を経由して証明されており，オリジナルの Lovász–Cherkasskyの定理の証明の拡張は今後の課題である．

参考文献[1] T. Fukunaga. Approximating the generalized terminal
backup problem via half-integral multiflow relaxation.
SIAM J. Discrete Math., 30(2):777–800, 2016.
[2] H. Hirai. L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem.
Discrete Optim., 18:1–37, 2015.
[3] H. Hirai. Discrete convexity and polynomial solvability in minimum 0-extension problems. Math. Program.
A, 155(1):1–55, 2016.
[4] H. Hirai.
A dual descent algorithm for nodecapacitated multiflow problems and its applications.
ACM Trans. Algorithms, 15(1):15:1–15:24, 2018.
[5] K. Murota.
Discrete Convex Analysis.
SIAM,
Philadelphia, 2003.