A Weighted Linear Matroid Parity Algorithm
joint work with 岩田 覚 （東京大学）

小林 佑輔
筑波大学
ERATO 感謝祭

August 3, 2017

はじめにSTOC
 Annual ACM Symposium on the Theory of Computing 理論計算機科学のトップ会議（他に FOCS, SODA などが有名）
 採択率 25% 程度，100件弱採択
STOC HP （http://acm-stoc.org/stoc2017/）

STOC Best Paper 受賞

3

主結果
重み付き線形マトロイドパリティ問題 に対して初の多項式時間アルゴリズムを与えた

4多項式時間アルゴリズム
計算時間が入力サイズの多項式で抑えられるアルゴリズム≈ （理論的に）効率の良いアルゴリズム
多項式時間アルゴリズムあり多項式時間アルゴリズム無し（と思われている）

 最短路問題

 SAT問題 マッチング問題

 巡回セールスマン問題

 最大流問題

 点彩色問題

 最小カット問題

 最大カット問題

 最小費用流問題

Petc.

 最大クリーク問題

NP-hardetc.
5多項式時間アルゴリズム
計算時間が入力サイズの多項式で抑えられるアルゴリズム≈ （理論的に）効率の良いアルゴリズム
多項式時間アルゴリズムあり多項式時間アルゴリズム無し（P≠NP を想定して） （と思われている）
 SAT問題
多項式時間で解ける問題の限界は？

 最短路問題 マッチング問題

 巡回セールスマン問題

 最大流問題

 点彩色問題

 最小カット問題

 最大カット問題

 最小費用流問題

Petc.

 最大クリーク問題

NP-hardetc.
6重み付き線形マトロイドパリティ

主結果
重み付き線形マトロイドパリティ問題 に対して初の多項式時間アルゴリズムを与えた
重み付き線形マトロイドパリティ問題 とは．．．？

 重み付き線形マトロイドマッチング問題とも呼ばれる
 重み付き2部グラフマッチングの 一般化の一般化
 30年以上多項式時間可解性が未解決だった
8

線形マトロイドパリティ問題
線形マトロイドパリティ
重み無し：Lovász (1978)
重み付き：Iwata-Kobayashi (2017+), Pap (??)

一般グラフのマッチング（線形）マトロイド交叉

重み無し：Edmonds (1965)

重み付き：Edmonds (1965)

重み無し：Edmonds (1968)
重み付き：Lawler (1975)
Iri-Tomizawa (1976)
Edmonds (1979)

2部グラフのマッチング
重み無し：van der Waerden (1927), Kőnig (1931)
重み付き： Egerváry (1931), Kuhn (1955)9線形マトロイドパリティ問題
線形マトロイドパリティ
重み無し：Lovász (1978)
重み付き：Iwata-Kobayashi (2017+), Pap (??)

一般グラフのマッチング（線形）マトロイド交叉

重み無し：Edmonds (1965)

重み付き：Edmonds (1965)

重み無し：Edmonds (1968)
重み付き：Lawler (1975)
Iri-Tomizawa (1976)
Edmonds (1979)

2部グラフのマッチング
重み無し：van der Waerden (1927), Kőnig (1931)
重み付き： Egerváry (1931), Kuhn (1955)10

２部グラフのマッチング
入力: ２部グラフ G=(U, V; E)
問題:１本以下の枝が接続最大サイズのマッチングは？

UV

11

２部グラフのマッチング
入力: ２部グラフ G=(U, V; E)
問題:

１本以下の枝が接続最大サイズのマッチングは？

UV12一般グラフのマッチング
入力: グラフ G=(V, E)

１本以下の枝が接続

問題: 最大サイズのマッチングは？

13グラフのマッチング（重み付き）
入力: グラフ G=(V, E)，枝重み 𝑤 𝑒
問題: 最大重みのマッチングは？

最小重みの完全マッチングは？
2つは本質的に等価
5781024414693114線形マトロイドパリティ問題
線形マトロイドパリティ
重み無し：Lovász (1978)
重み付き：Iwata-Kobayashi (2017+), Pap (??)

一般グラフのマッチング（線形）マトロイド交叉

重み無し：Edmonds (1965)重み付き：Edmonds (1965)

重み無し：Edmonds (1968)
重み付き：Lawler (1975)
Iri-Tomizawa (1976)
Edmonds (1979)

2部グラフのマッチング
重み無し：van der Waerden (1927), Kőnig (1931)
重み付き： Egerváry (1931), Kuhn (1955)15線形マトロイド交叉
 線形マトロイド → ここでは単に「行列」と思って十分

入力：

A1 =

110000V

V01
1000001
1000001
1000001
1

100001000010000001100010010100U A2 =U

共通独立集合 : 列ベクトルの集合がどちらでも一次独立
共通基 B : A1[B, U] も A2[B, U] も 正則

問題： 最大の共通独立集合は？
最小重みの 共通基 B は？

（重み w: V → R）
16

２部マッチング → 線形マトロイド交叉e fu1efv1u2v2

u1 1 1u2 0 0
A1 = 0 00 00 00 00100000
10000100000001000e fv1v2
A2 =マッチング
完全マッチング

1000000
10000

共通独立集合共通基17

線形マトロイドパリティ問題
線形マトロイドパリティ
重み無し：Lovász (1978)
重み付き：Iwata-Kobayashi (2017+), Pap (??)

一般グラフのマッチング（線形）マトロイド交叉

重み無し：Edmonds (1965)

重み付き：Edmonds (1965)

重み無し：Edmonds (1968)
重み付き：Lawler (1975)
Iri-Tomizawa (1976)
Edmonds (1979)

2部グラフのマッチング
重み無し：van der Waerden (1927), Kőnig (1931)
重み付き： Egerváry (1931), Kuhn (1955)18

線形マトロイドパリティ (or Matroid matching or Matchoid)
V

入力：

A=

10
0
0
0
0

0
1
0000001
1000001
1000001
1

10000
10000
100
0000
1

1
000
100
10
100

U

ライン 𝑙 = 𝑢, 𝑢 ∈ 𝐿
パリティ集合: ラインの和集合
問題： 最大サイズの 独立パリティ集合

19

線形マトロイドパリティ (or Matroid matching or Matchoid)
V入力：

A=

100000010000001100000110000011100001000010000001100010010100U

ライン 𝑙 = 𝑢, 𝑢 ∈ 𝐿
パリティ集合: ラインの和集合
問題： 最大サイズの 独立パリティ集合20重み付き線形マトロイドパリティ
V

入力：

A=

100000010000001
1000001
10000011100001000010000001100010010100U

ライン 𝑙 = 𝑢, 𝑢 ∈ 𝐿
パリティ基: パリティ集合 & 基
問題： 最小重みの パリティ基（重み w: L → R）

21

マッチング → 線形マトロイドパリティ
v1 e1v2
e2

マッチング
完全マッチング

v1v2
A=

e1

e2

0
10000100000

10000000
1000

独立パリティ集合
パリティ基

22

線形マトロイド交叉 → 線形マトロイドパリティ
e f

A1 =

1
10000101
100A1

e f

0
101101
10000

101
100010110𝑂

e f

A2 =

1234000
13010104220𝑂

123400013010e fライン

共通独立集合
共通基

104
220

A2

独立パリティ集合
パリティ基
23

線形マトロイドパリティ問題
線形マトロイドパリティ
重み無し：Lovász (1978)
重み付き：Iwata-Kobayashi (2017+), Pap (??)

一般グラフのマッチング（線形）マトロイド交叉

重み無し：Edmonds (1965)

重み付き：Edmonds (1965)

重み無し：Edmonds (1968)
重み付き：Lawler (1975)
Iri-Tomizawa (1976)
Edmonds (1979)

2部グラフのマッチング
重み無し：van der Waerden (1927), Kőnig (1931)
重み付き： Egerváry (1931), Kuhn (1955)24

応用
（重み無し）線形マトロイドパリティ• Structural solvability analysis of electric networks

Milić (1974)• Pinning down planar skeleton structures

Lovász (1980)• Feedback vertex set in subcubic graphs

Ueno, Kajitani, and Gotoh (1988)• Maximum genus cellular embedding

Furst, Gross, McGeoch (1988)• Maximum number of disjoint S-paths

Lovász (1980), Schrijver (2003)

 重み付き線形マトロイドパリティ• Approximation algorithm for Steiner Tree

Prömel & Steger (2000)• Weighted disjoint S-paths

Yamaguchi (2016)• Weighted Feedback vertex set in subcubic graphs
Kobayashi & Yamaguchi (2017)25

アルゴリズム既存アルゴリズム|V|=n, |U|=m（重み無し）線形マトロイドパリティ
Authors

Running time

Lovász (1978)
Gabow & Stallmann (1986)
Orlin & Vande Vate (1990)

PolynomialO(nm3)O(nm4)(or O(nm2.38))(or O(nm3.38))

Orlin (2008)
Cheung, Lau, Leung (2011)

O(nm3)O(nm2)(or O(nm2.38))(or O(nm1.38))

乱択 重み付き線形マトロイドパリティ• Camerini, Galbiati, and Maffioli (1992)• Cheung, Lau, and Leung (2014)

乱択・擬多項式27

本研究の方針・ポイント アルゴリズム 増加道アルゴリズム(重み無し版に対する Gabow and Stallmann のアルゴリズムを元に)
 “主双対アプローチ”

注意: 明示的な LP 表現は与えていない 最適性の保証
 “双対変数”の性質
 多項式行列の Pfaffian を用いた定式化
 組合せ緩和の思想

Murota (1990)28

双対変数 （概略） Laminar family of blossoms

Λ = 𝐻1 , 𝐻2 , … , 𝐻𝜆

 双対変数 𝑝: 𝑉 → 𝐑
 𝑞: Λ → 𝐑 +BlossomLaminar family29双対変数 （概略） 双対変数 Laminar family of blossoms

 𝑝: 𝑉 → 𝐑

Λ = 𝐻1 , 𝐻2 , … , 𝐻𝜆

 𝑞: Λ → 𝐑 +1

A

10

10

𝐶𝐶𝜆𝐶𝑈1𝐵

Λ で定義される基本変形𝑉∖𝐵 Dual feasibility(DF1) 𝑝 𝑢 + 𝑝 𝑢 = 𝑤(𝑙)for 𝑙 = {𝑢, 𝑢}(DF2) 𝑝 𝑣 − 𝑝 𝑢 ≥ 𝑄𝑢𝑣 ≔𝑢𝑣∈𝛿(𝐻) 𝑞(𝐻)𝑢𝐻𝜆 ≠0if 𝐶𝑢𝑣𝑣

30

主双対アルゴリズム
Initial Solution
B : a basep, q : feasible dual variables

Is B a parity base?

YES

Output B

NO

Search for an Augmenting PathYESAugmentation(Update B)NO

Update p, q

New tight edge

NO new tight edge

No feasible Solution31

主双対アルゴリズム
Initial Solution
B : a basep, q : feasible dual variables
YES

Is B a parity base?

∈𝐵
∈𝑉∖𝐵

Output B

NO: lines

Search for an Augmenting Path𝑢𝑣
Augmenting Pathsource line𝐹∘ =source line

𝜆 ≠ 0, 𝑝 𝑣 − 𝑝 𝑢 = 𝑄
𝑢, 𝑣 | 𝐶𝑢𝑣
𝑢𝑣

tightYES

Augmentation(Update B)NO

Update p, q

New tight edge

NO new tight edge

No feasible Solution32

主双対アルゴリズム
Initial Solution
B : a basep, q : feasible dual variables

Is B a parity base?

YES

Output BNO

Search for an Augmenting Pathsource line

source line

YES

Augmentation(Update B)NO

Update p, q

New tight edge

NO new tight edge

No feasible Solution

33

主双対アルゴリズム
Initial Solution
B : a basep, q : feasible dual variables
YES

Is B a parity base?

Output B

NO

Search for an Augmenting Path𝑢𝑣
Augmenting Pathsource line𝐹∘ =source line

𝜆 ≠ 0, 𝑝 𝑣 − 𝑝 𝑢 = 𝑄𝑢, 𝑣 | 𝐶𝑢𝑣
𝑢𝑣

tightYES

Augmentation(Update B)

NOUpdate p, q

New tight edge

NO new tight edge

No feasible Solution34

主双対アルゴリズム|V|=n, |U|=m

Initial Solution
B : a basep, q : feasible dual variables
YES

Is B a parity base?

Output BNO

Search for an Augmenting Path𝑢𝑣

2Augmenting Path𝑂(𝑛 ) operations

source line𝐹∘ =source line

𝜆 ≠ 0, 𝑝 𝑣 − 𝑝 𝑢 = 𝑄𝑢, 𝑣 | 𝐶𝑢𝑣
𝑢𝑣

tightYES

Augmentation(Update B)

𝑂(𝑚) times

NOUpdate p, q

Newtighttimes
edge
𝑂(𝑛)

NO new tight edge

No feasible Solution35

まとめ|V|=n, |U|=m定理
提案アルゴリズムは最小重み線形マトロイドパリティをO(n3m) 回の演算で求められる
 有限体 𝐊 上の問題であれば O(n3m) 時間で解ける
 有理数体 ℚ 上の問題は多項式時間で解ける （要議論）36まとめ|V|=n, |U|=m定理
提案アルゴリズムは最小重み線形マトロイドパリティをO(n3m) 回の演算で求められる
 有限体 𝐊 上の問題であれば O(n3m) 時間で解ける
 有理数体 ℚ 上の問題は多項式時間で解ける （要議論）

難しさ LP表現が無い → “双対変数”の適切な定義
 最適性の証明，各ステップの正確な記述・正当性

37

38