重み付き線形マトロイドパリティ

(1)

重み付き線形マトロイドパリティ

組合せ最適化問題に対する多面体的手法とその発展３コマ目

(2)

主結果

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

重み付き線形マトロイドパリティ問題とは．．．？



重み付き線形マトロイドマッチング問題とも呼ばれる



重み付き

2

部グラフマッチングの一般化の一般化

 30

年以上多項式時間可解性が未解決だった

2 Iwata-Kobayashi (2017)

(3)

線形マトロイドパリティ問題

2部グラフのマッチング

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

重み無し：van der Waerden (1927), Kőnig (1931) 重み付き：Egerváry (1931), Kuhn (1955)

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

重み無し：Edmonds (1968) 重み付き：Lawler (1975)

Iri-Tomizawa (1976) Edmonds (1979) 重み無し：Lovász (1978)

重み付き：Iwata-Kobayashi (2017+), Pap (??)

3

(4)

線形マトロイドパリティ

(or Matroid matching or Matchoid)

10 00 00

01 00 00

00 11 00

00 01 10

00 00 11

00 00 10

00 00 01

10 00 10

01 01 00

U V

A =

ライン

𝑙𝑙 = 𝑢𝑢, �𝑢𝑢 ∈ 𝐿𝐿

パリティ集合

:

ラインの和集合最大サイズの独立パリティ集合入力：

問題：

4 00

10 01

(5)

線形マトロイドパリティ

(or Matroid matching or Matchoid)

10 00 00

01 00 00

00 11 00

00 01 10

00 00 11

00 10 01

00 00 10

00 00 01

10 00 10

01 01 00

U V

A =

ライン

𝑙𝑙 = 𝑢𝑢, �𝑢𝑢 ∈ 𝐿𝐿

パリティ集合

:

ラインの和集合最大サイズの独立パリティ集合入力：

問題：

5

(6)

重み付き線形マトロイドパリティ

10 00 00

01 00 00

00 11 00

00 01 10

00 00 11

00 00 10

00 00 01

10 00 10

01 01 00

U V

A =

ライン

𝑙𝑙 = 𝑢𝑢, �𝑢𝑢 ∈ 𝐿𝐿

パリティ基

:

パリティ集合

&

基

最小重みのパリティ基（重み

w: L → R

）入力：

問題：

6 00

10 01

(7)

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

A =

10 00 00

01 00 00

10 00 00

00 10 00

v1

e1 e2 v2

v2 v1

e1

e2

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

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

7

(8)

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

共通独立集合共通基

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

e

11 00 00

10 11 00

01 01 10

A₁ =

A₂ =

12 34 00

01 30 10

10 42 20

f

e f

11 00 00

10 11 00

01 01 10

A₂

12 34 00

01 30 10

10 42 20

e f A₁

e f

𝑂𝑂

ライン

8

(9)

線形マトロイドパリティ問題

2部グラフのマッチング

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

重み無し：van der Waerden (1927), Kőnig (1931) 重み付き：Egerváry (1931), Kuhn (1955)

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

重み無し：Edmonds (1968) 重み付き：Lawler (1975)

Iri-Tomizawa (1976) Edmonds (1979) 重み無し：Lovász (1978)

重み付き：Iwata-Kobayashi (2017+), Pap (??)

9

(10)

応用

• Structural solvability analysis of electric networks

• Pinning down planar skeleton structures

• Feedback vertex set in subcubic graphs

• Maximum genus cellular embedding

• Maximum number of disjoint S -paths

• Approximation algorithm for Steiner Tree

• Weighted disjoint S -paths

• Weighted Feedback vertex set in subcubic graphs

Prömel & Steger (2000) Yamaguchi (2016)

10 Milić (1974)

Lovász (1980) Ueno, Kajitani, and Gotoh (1988)

Furst, Gross, McGeoch (1988) Lovász (1980), Schrijver (2003)

 （重み無し）線形マトロイドパリティ

 重み付き線形マトロイドパリティ

Kobayashi & Yamaguchi (2017)

(11)

既存アルゴリズム

Authors Running time

Lovász (1978) Polynomial

Gabow & Stallmann (1986) O(nm

³

) (or O(nm

^2.38

)) Orlin & Vande Vate (1990) O(nm

⁴

) (or O(nm

^3.38

)) Orlin (2008) O(nm

³

) (or O(nm

^2.38

)) Cheung, Lau, Leung (2011) O(nm

²

) (or O(nm

^1.38

))

|V|=n, |U|=m

乱択

 （重み無し）線形マトロイドパリティ

 重み付き線形マトロイドパリティ

• Camerini, Galbiati, and Maffioli (1992)

• Cheung, Lau, and Leung (2014)

乱択・擬多項式

11

(12)

アルゴリズム

(13)

提案アルゴリズムの方針・ポイント

 アルゴリズム

 増加道アルゴリズム

(重み無し版に対する Gabow and Stallmann のアルゴリズムを元に)

 “主双対アプローチ”

 最適性の保証

 “双対変数”の性質

 多項式行列の Pfaffian を用いた定式化

 組合せ緩和の思想

注意

:

明示的な

LP

表現は与えていない

Murota (1990)

13

(14)

Augmenting Path Algorithm (unweighted)

Gabow and Stallmann (1986)

Input

U V

A =

Line 𝑙𝑙 = 𝑢𝑢, �𝑢𝑢 ∈ 𝐿𝐿

Parity set: union of lines

Find An independent parity set of maximum size

w.l.o.g. assume that A is row-full rank Linear Matroid Parity

14

(15)

Augmenting Path Algorithm (unweighted)

B : an arbitrary base Initial Solution

Input

U V

A =

Line 𝑙𝑙 = 𝑢𝑢, �𝑢𝑢 ∈ 𝐿𝐿

Parity set: union of lines

Find An independent parity set of maximum size

15

(16)

Augmenting Path Algorithm (unweighted)

Is B a parity base?

Output B

YES

Input

U V

A =

Line 𝑙𝑙 = 𝑢𝑢, �𝑢𝑢 ∈ 𝐿𝐿

Parity set: union of lines

Find An independent parity set of maximum size

16

(17)

Augmenting Path Algorithm (unweighted)

Is B a parity base?

NO

Output B Search for an Augmenting Path

YES

Augmentation

(Update B) Output the maximal

parity set in B

NO

17

(18)

Augmenting Path Algorithm (unweighted)

Is B a parity base?

NO

YES

Augmentation

parity set in B

NO

∈ 𝐵𝐵

∈ 𝑉𝑉 ∖ 𝐵𝐵

: lines

source line source line

𝐹𝐹 = 𝑢𝑢,𝑣𝑣 | 𝑢𝑢 ∈ 𝐵𝐵, 𝑣𝑣 ∈ 𝑉𝑉 ∖ 𝐵𝐵,𝐵𝐵 − 𝑢𝑢 + 𝑣𝑣: base

𝑢𝑢 𝑣𝑣

Augmenting Path

18

(19)

Augmenting Path Algorithm (unweighted)

Is B a parity base?

NO

YES

Augmentation

parity set in B

NO

∈ 𝐵𝐵

: lines

19

(20)

Augmenting Path Algorithm (unweighted)

Is B a parity base?

NO

YES

Augmentation

parity set in B

NO

∈ 𝐵𝐵

: lines

𝐹𝐹 = 𝑢𝑢,𝑣𝑣 | 𝑢𝑢 ∈ 𝐵𝐵, 𝑣𝑣 ∈ 𝑉𝑉 ∖ 𝐵𝐵,𝐵𝐵 − 𝑢𝑢 + 𝑣𝑣: base

𝑢𝑢 𝑣𝑣

Augmenting Path

 Creating Blossoms

 Introducing new vertices

 Validity proof Omitted Details

20

(21)

21

Dual Variables

Blossom Laminar family

𝑡𝑡 ̅𝑡𝑡

 Laminar family of blossoms Λ = 𝐻𝐻

₁

, 𝐻𝐻

₂

, … , 𝐻𝐻

_𝜆𝜆

 Dual feasibility

(DF1) 𝑝𝑝 𝑢𝑢 + 𝑝𝑝 �𝑢𝑢 = 𝑤𝑤(𝑙𝑙 ) for 𝑙𝑙 = {𝑢𝑢, �𝑢𝑢}

(DF2) 𝑝𝑝 𝑣𝑣 − 𝑝𝑝 𝑢𝑢 ≥ 𝑄𝑄

_{𝑢𝑢𝑢𝑢}

≔ ∑

_𝐻𝐻:𝑢𝑢𝑢𝑢 crosses 𝐻𝐻

𝑞𝑞 (𝐻𝐻) if 𝐶𝐶

_{𝑢𝑢𝑢𝑢}

≠ 0 (DF3) 𝑝𝑝 𝑣𝑣 − 𝑝𝑝 𝑢𝑢 = 𝑞𝑞 (𝐻𝐻) if 𝑢𝑢, 𝑣𝑣 are tip of 𝐻𝐻 and its mate

tip mate

𝑢𝑢 𝑣𝑣

 Dual variables



𝑝𝑝: 𝑉𝑉 → 𝐑𝐑



𝑞𝑞 : Λ → 𝐑𝐑

₊

(22)

Primal Dual Algorithm (weighted)

Is B a parity base?

B : a base Initial Solution

NO

YES

Augmentation (Update B)

NO

𝑢𝑢 𝑣𝑣

Augmenting Path

22

(23)

Primal Dual Algorithm (weighted)

Is B a parity base?

NO

YES

NO

𝑢𝑢 𝑣𝑣

Augmenting Path

p, q : feasible dual variables

• Take 𝑝𝑝 with 𝑝𝑝 𝑢𝑢 + 𝑝𝑝 �𝑢𝑢 = 𝑤𝑤 𝑙𝑙

• Let 𝐵𝐵 be a min. weight base w.r.t. 𝑝𝑝

23

(24)

Primal Dual Algorithm (weighted)

Is B a parity base?

NO

YES

𝐹𝐹^∘ = 𝑢𝑢,𝑣𝑣 | 𝐶𝐶_{𝑢𝑢𝑢𝑢} ≠ 0,𝑝𝑝 𝑣𝑣 − 𝑝𝑝 𝑢𝑢 = 𝑄𝑄_{𝑢𝑢𝑢𝑢}

𝑢𝑢 𝑣𝑣

Augmenting Path

tight

NO

24

(25)

Primal Dual Algorithm (weighted)

Is B a parity base?

NO

YES

Update p, q

NO

𝑢𝑢 𝑣𝑣

Augmenting Path

tight

New tight edge NO new tight edge

No feasible Solution 25

(26)

なぜ最適性が保証できるのか？

≠

最適性の証明

(27)

マッチング多面体

5 8 7 10

4 2

14 3

6

1 4

9

27

�

𝑒𝑒∈𝛿𝛿(𝑢𝑢)

𝑥𝑥(𝑒𝑒) = 1

𝑥𝑥(𝑒𝑒) ≥ 0 (𝑒𝑒 ∈ 𝐸𝐸)

完全マッチング多面体

conv 𝜒𝜒

_𝑀𝑀

| 𝑀𝑀 ⊆ 𝐸𝐸 ∶ perfect matching

(𝑣𝑣 ∈ 𝑉𝑉)

�

𝑒𝑒∈𝛿𝛿(𝑍𝑍)

𝑥𝑥(𝑒𝑒) ≥ 1 (𝑍𝑍 ⊆ 𝑉𝑉, |𝑍𝑍|: odd)

(28)

マトロイド交叉多面体

28

𝑥𝑥(𝑒𝑒) ≥ 0 (𝑒𝑒 ∈ 𝑉𝑉)

マトロイド交叉多面体

conv 𝜒𝜒

_𝐼𝐼

| 𝐼𝐼 ⊆ 𝑉𝑉 : common independent set

�

𝑒𝑒∈𝑈𝑈

𝑥𝑥(𝑒𝑒) ≤ 𝑟𝑟

₂

(𝑈𝑈) (𝑈𝑈 ⊆ 𝑉𝑉)

�

𝑒𝑒∈𝑈𝑈

𝑥𝑥(𝑒𝑒) ≤ 𝑟𝑟

₁

(𝑈𝑈)

e

11 00 00

10 11 00

01 01 10

A₁ =

A₂ =

12 34 00

01 30 10

10 42 20

f

e f

(𝑈𝑈 ⊆ 𝑉𝑉)

(29)



完全マッチング多面体を複数（指数個

or

無限個）使った



拡張定式化

で表現することができる

線形マトロイドパリティ多面体？

29

𝑃𝑃 𝐴𝐴 ≔ conv 𝜒𝜒

_𝐼𝐼

| 𝐼𝐼 ⊆ 𝐿𝐿:

^{基をなすラインの集合} ^を

最適性証明のポイント

(30)

横断マトロイドパリティは容易

30

*0 00 00

0* 00 00

00

** 00

00 0*

*0 00 00

**

00 00

*0 00 00 0*

*0 00

*0 0* 0* 00

U V

𝐴𝐴 =

00

*0 0*

U V

𝑤𝑤_𝑙𝑙

(31)

横断マトロイドパリティは容易

31

*0 00 00

0* 00 00

00

** 00

00 0*

*0 00 00

**

00 00

*0 00 00 0*

*0 00

*0 0* 0* 00

U V

𝐴𝐴 =

00

*0 0*

U V’ V

𝑤𝑤_𝑙𝑙

𝑤𝑤_𝑙𝑙 0

0

パリティ基完全マッチング

(32)

32

*0 00 00

0* 00 00

00

** 00

00 0*

*0 00 00

**

00 00

*0 00 00 0*

*0 00

*0 0* 0* 00

U V

𝐴𝐴 =

00

*0 0*

U V’ V

パリティ基完全マッチング

𝑤𝑤_𝑙𝑙

𝑤𝑤_𝑙𝑙 0

0

横断マトロイドパリティは容易

conv 𝜒𝜒

_𝐼𝐼

| 𝐼𝐼 ⊆ 𝐿𝐿:

^{基をなすラインの集合} ^を

完全マッチング多面体の

𝐿𝐿

への射影として表せる

(33)

横断マトロイドは線形マトロイドの緩和

33 10

00 00

01 00 00

00 11 00

00 01 10

00 00 11

00 00 10

00 00 01

10 00 10

01 01 00

U V

A =

00 10 01

の独立集合族

*0 00 00

0* 00 00

00

** 00

00 0*

*0 00 00

**

00 00

*0 00 00 0*

*0 00

*0 0* 0* 00

U V

̂𝐴𝐴 =

00

*0 0*

の独立集合族

⊆

（基族）

(34)

線形マトロイドパリティ多面体

34

𝑃𝑃 𝐴𝐴 ⊆ 𝑃𝑃( ̂𝐴𝐴)

𝑃𝑃 𝐴𝐴 ⊆ �

𝐴𝐴′∼𝐴𝐴

𝑃𝑃 ( 𝐴𝐴𝐴) �

𝐴𝐴𝐴 は 𝐴𝐴 に行変形をして得られる 𝐴𝐴𝐴 の数値情報を無視

𝑃𝑃 𝐴𝐴 ≔ conv 𝜒𝜒

_𝐼𝐼

| 𝐼𝐼 ⊆ 𝐿𝐿:

^{基をなすラインの集合}

(35)

線形マトロイドパリティ多面体

𝐴𝐴 𝑂𝑂

35

𝑍𝑍 𝐼𝐼

V W

𝐴𝐴

_𝑍𝑍

≔

𝐴𝐴 から定義されるマトロイド

=

から定義されるマトロイド

W

縮約

𝑃𝑃 𝐴𝐴 ⊆ �

𝑍𝑍

𝑃𝑃( 𝐴𝐴𝐴 �

_𝑍𝑍

/𝑊𝑊 )

マトロイドの縮約

𝑃𝑃 𝐴𝐴 ⊆ 𝑃𝑃( ̂𝐴𝐴)

𝑃𝑃 𝐴𝐴 ⊆ �

𝐴𝐴′∼𝐴𝐴

𝑃𝑃 ( 𝐴𝐴𝐴) �

𝐴𝐴𝐴 は 𝐴𝐴 に行変形をして得られる

𝐴𝐴𝐴_𝑍𝑍 ∼ 𝐴𝐴_𝑍𝑍

𝐴𝐴𝐴 の数値情報を無視

(36)

線形マトロイドパリティ多面体

36 𝐴𝐴𝐴_𝑍𝑍 は 𝐴𝐴_𝑍𝑍 に行変形をして得られる

数値情報を無視

𝐴𝐴 𝑂𝑂

𝑍𝑍 𝐼𝐼

V W

𝐴𝐴

_𝑍𝑍

≔

𝐴𝐴 から定義されるマトロイド

=

から定義されるマトロイド

W

縮約マトロイドの縮約

完全マッチング多面体の 𝐿𝐿 への射影として表せる

複数の完全マッチング多面体を用いた 𝑃𝑃 𝐴𝐴 の拡張定式化

𝑃𝑃 𝐴𝐴 = �

𝑍𝑍

𝑃𝑃( 𝐴𝐴𝐴 �

_𝑍𝑍

/𝑊𝑊)

定理

(37)

線形マトロイドパリティ多面体

37 𝐴𝐴𝐴_𝑍𝑍 は 𝐴𝐴_𝑍𝑍 に行変形をして得られる

数値情報を無視マトロイドの縮約

𝑃𝑃 𝐴𝐴 = �

𝑍𝑍

𝑃𝑃( 𝐴𝐴𝐴 �

_𝑍𝑍

/𝑊𝑊)

実は，もう少し強く以下が成立

定理

∃𝐴𝐴𝐴

_𝑍𝑍

∼ 𝐴𝐴

_𝑍𝑍^：行変形

min 𝑤𝑤 � 𝑥𝑥 𝑥𝑥 ∈ 𝑃𝑃 𝐴𝐴 } = min 𝑤𝑤 � 𝑥𝑥 𝑥𝑥 ∈ 𝑃𝑃 ( 𝐴𝐴 �

^′_𝑍𝑍

/𝑊𝑊)}

∀𝑤𝑤

^{：重み関数，}

∃𝑍𝑍

^{：付加する行列}，定理

(38)

アルゴリズムの解釈

38

 アルゴリズムで保持しているもの



𝐵𝐵

：基

 追加頂点：𝑍𝑍

,

行変形の情報



Blossom

：

Blossom



𝑝𝑝, 𝑞𝑞

：双対変数

 主双対アルゴリズム＋複雑な双対概念

主問題の緩和解

（tip, mate）

横断マトロイドを扱うときの通常のマッチングの意味での

双対問題の許容解

(39)

線形マトロイドパリティのまとめ

39



マッチングとマトロイド交叉の融合



数値情報を無視する「組合せ緩和」の思想



変数の追加，行列の変形を用いた，多面体の表現

自然な疑問



「多面体的表現」を直接得られないか？



「多面体的表現」からアルゴリズムは得られる？



もっと簡単な表現はある？

→

新たな変数を追加する操作は必要そう

(40)

おわりに

(41)

おわりに

41

 多面体的手法：

組合せ最適化における古典的だが強力な手法

 重み付きの問題を扱う際に必須

 指数サイズ（ or 無限サイズ）の拡張定式化が他の問題に使えるか？

Yusuke Kobayashi:

Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles, IPCO2020.

例：制約付き２マッチング問題

(42)

42

(43)

Appendix ：その他の難しいポイント

(44)

Dual Variables

 Dual variables



𝑝𝑝: 𝑉𝑉 → 𝐑𝐑



𝑞𝑞 : Λ → 𝐑𝐑

₊

Blossom Laminar family

𝑡𝑡 ̅𝑡𝑡

 Laminar family of blossoms Λ = 𝐻𝐻

₁

, 𝐻𝐻

₂

, … , 𝐻𝐻

_𝜆𝜆

 Dual feasibility

(DF1) 𝑝𝑝 𝑢𝑢 + 𝑝𝑝 �𝑢𝑢 = 𝑤𝑤(𝑙𝑙 ) for 𝑙𝑙 = {𝑢𝑢, �𝑢𝑢}

(DF2) 𝑝𝑝 𝑣𝑣 − 𝑝𝑝 𝑢𝑢 ≥ 𝑄𝑄

_{𝑢𝑢𝑢𝑢}

≔ ∑

_𝐻𝐻:𝑢𝑢𝑢𝑢 crosses 𝐻𝐻

𝑞𝑞 (𝐻𝐻) if 𝐶𝐶

_{𝑢𝑢𝑢𝑢}

≠ 0 (DF3) 𝑝𝑝 𝑣𝑣 − 𝑝𝑝 𝑢𝑢 = 𝑞𝑞 (𝐻𝐻) if 𝑢𝑢, 𝑣𝑣 are tip of 𝐻𝐻 and its mate

tip mate

How do we define tips and mates?

44

(45)

Primal Dual Algorithm (weighted)

Is B a parity base?

NO

YES

Update p, q

NO

𝑢𝑢 𝑣𝑣

Augmenting Path

tight

No feasible Solution Def. of dual feasibility

Optimality proof

 Creating blossoms

 Introducing 𝑡𝑡_𝑖𝑖, _𝑖𝑖̅𝑡𝑡

 Validity proof

Bounding iterations

Proof of infeasibility

 Def. of the procedure

 Updating 𝑡𝑡_𝑖𝑖, ̅𝑡𝑡_𝑖𝑖

45

(46)

Primal Dual Algorithm (weighted)

Is B a parity base?

NO

YES

Update p, q

NO

𝑢𝑢 𝑣𝑣

Augmenting Path

tight

No feasible Solution 46

(47)

Primal Dual Algorithm (weighted)

Is B a parity base?

NO

YES

Update p, q

NO

No feasible Solution

𝑂𝑂(𝑛𝑛 ² ) operations

|V|=n, |U|=m

𝑂𝑂(𝑚𝑚) times

𝑂𝑂(𝑛𝑛) times

47

(48)

Conclusion

Our algorithm finds a minimum weight parity base with O(n

³

m) arithmetic operations

Theorem

 If the problem is over a fixed finite field 𝐊𝐊 , then it can be solved in O(n

³

m) time

 If the problem is over the rational field ℚ , then it can be solved in polynomial time

(More arguments are required)

48

重み付き線形マトロイドパリティ

重み付き線形マトロイドパリティ

主結果

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





2

 30

線形マトロイドパリティ問題

線形マトロイドパリティ

U V

A =

𝑙𝑙 = 𝑢𝑢, �𝑢𝑢 ∈ 𝐿𝐿

:

線形マトロイドパリティ

U V

A =

𝑙𝑙 = 𝑢𝑢, �𝑢𝑢 ∈ 𝐿𝐿

:

重み付き線形マトロイドパリティ

U V

A =

𝑙𝑙 = 𝑢𝑢, �𝑢𝑢 ∈ 𝐿𝐿

:

&

w: L → R

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

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

𝑂𝑂

𝑂𝑂

線形マトロイドパリティ問題

応用

• Structural solvability analysis of electric networks

• Pinning down planar skeleton structures

• Feedback vertex set in subcubic graphs

• Maximum genus cellular embedding

• Maximum number of disjoint S -paths

• Approximation algorithm for Steiner Tree

• Weighted disjoint S -paths

• Weighted Feedback vertex set in subcubic graphs

 （重み無し）線形マトロイドパリティ

 重み付き線形マトロイドパリティ

既存アルゴリズム

Authors Running time

Lovász (1978) Polynomial

Gabow & Stallmann (1986) O(nm

) (or O(nm

)) Orlin & Vande Vate (1990) O(nm

) (or O(nm

)) Orlin (2008) O(nm

) (or O(nm

)) Cheung, Lau, Leung (2011) O(nm

) (or O(nm

))

|V|=n, |U|=m

 （重み無し）線形マトロイドパリティ

 重み付き線形マトロイドパリティ

• Camerini, Galbiati, and Maffioli (1992)

• Cheung, Lau, and Leung (2014)

アルゴリズム

提案アルゴリズムの方針・ポイント

:

LP

Augmenting Path Algorithm (unweighted)

Input

U V

A =

Line 𝑙𝑙 = 𝑢𝑢, �𝑢𝑢 ∈ 𝐿𝐿

Parity set: union of lines

Find An independent parity set of maximum size

Augmenting Path Algorithm (unweighted)

Input

U V

A =

Line 𝑙𝑙 = 𝑢𝑢, �𝑢𝑢 ∈ 𝐿𝐿

Parity set: union of lines

Find An independent parity set of maximum size

Augmenting Path Algorithm (unweighted)

Input

U V

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