Packing Non-zero 𝑨-paths
via Matroid Matching
Shin-ichi Tanigawa1, Yutaro Yamaguchi2
1. Kyoto University (RIMS), Japan.
2. University of Tokyo, Japan.
ISMP 2015 @Pittsburgh

July 17, 20151

Menger’s Disjoint Paths Problem
Given

𝐺 = (𝑉, 𝐸): Undirected Graph𝑠, 𝑡 ∈ 𝑉: Distinct Terminals

𝑡𝑠

Find

Maximum Number of Disjoint 𝑠–𝑡 paths2

Menger’s Disjoint Paths Problem
Given

𝐺 = (𝑉, 𝐸): Undirected Graph𝑠, 𝑡 ∈ 𝑉: Distinct Terminals

𝑡𝑠

Find

Maximum Number of Disjoint 𝑠–𝑡 paths
Edge or Vertex
3Menger’s Disjoint Paths Problem
Given

𝐺 = (𝑉, 𝐸): Undirected Graph𝑠, 𝑡 ∈ 𝑉: Distinct Terminals

𝑡𝑠

Find

Maximum Number of Disjoint 𝑠–𝑡 paths
Don’t Share Edge
4

Menger’s Disjoint Paths Problem
Given

𝐺 = (𝑉, 𝐸): Undirected Graph𝑠, 𝑡 ∈ 𝑉: Distinct Terminals

𝑡𝑠

Find

Maximum Number of Disjoint 𝑠–𝑡 paths
Don’t Share Vertex
5Menger’s Disjoint Paths Problem
Given

𝐺 = (𝑉, 𝐸): Undirected Graph𝑠, 𝑡 ∈ 𝑉: Distinct Terminals

𝑡𝑠

Find

Maximum Number of Disjoint 𝑠–𝑡 paths
Don’t Share Vertex
6(Non-bipartite) Maximum Matching
Given

𝐺 = (𝑉, 𝐸): Undirected Graph

FindMaximum Matching
7

(Non-bipartite) Maximum Matching
Given

𝐺 = (𝑉, 𝐸): Undirected Graph

FindMaximum Matching Edges
Not Sharing End Vertices
8Overview

Menger’s
Disjoint Paths

Non-bipartite
Matching
9

Overview

Mader’s
Disjoint S-paths[Mader 1978]

Generalized
Menger’s
Disjoint Paths

Non-bipartite
Matching
10

Overview
Packing
Non-zero 𝑨-paths[Chudnovsky, Geelen, Gerards,Goddyn, Lohman, Seymour 2006][Chudnovsky, Cunningham, Geelen 2008]

Generalized
Mader’s
Disjoint S-paths
Menger’s
Disjoint Paths

PackingOdd-Length 𝐴-paths

Non-bipartite
Matching
11

Overview
Packing
Non-zero 𝐴-paths
Matroid
Matching
Mader’s
Disjoint S-paths[Lowler 1976]

Generalized
Menger’s
Disjoint Paths

Non-bipartite
Matching

MatroidIntersection
12

Overview
Packing
Non-zero 𝐴-paths
Reduction[Lovász 1980]

Matroid
Matching

Mader’s
Disjoint S-paths
Menger’s
Disjoint Paths

Non-bipartite
Matching

MatroidIntersection
13

Overview
Packing
Non-zero 𝑨-paths[Tanigawa, Y. 2015][Lovász 1980]

Matroid
Matching

Mader’s
Disjoint S-paths
Menger’s
Disjoint Paths

Non-bipartite
Matching

MatroidIntersection
14

Overview
Packing
Non-zero 𝐴-paths

Mader’s
Disjoint S-paths
Menger’s
Disjoint Paths

Non-bipartiteMatching15

𝐴-paths and S-paths
𝐺 = (𝑉, 𝐸): Undirected Graph𝐴 ⊆ 𝑉: Terminal Set
S = 𝐴1 , 𝐴2 , … , 𝐴𝑘 : Partition of 𝐴
𝐴-paths∈𝐴∉𝐴

NOT 𝐴-paths

16

𝐴-paths and S-paths
𝐺 = (𝑉, 𝐸): Undirected Graph𝐴 ⊆ 𝑉: Terminal Set
S = 𝐴1 , 𝐴2 , … , 𝐴𝑘 : Partition of 𝐴

𝐴2

∈𝐴
∉𝐴

S-pathNOT S-path

𝐴2𝐴1𝐴1𝐴3𝐴317

Mader’s Disjoint S-paths Problem
Given

𝐺 = (𝑉, 𝐸): Undirected Graph𝐴 ⊆ 𝑉: Terminal Set, S : Partition of 𝐴
𝐴2

𝐴1
Find

𝐴3
Maximum Number of
Fully Vertex-Disjoint S-paths

18

Mader’s Disjoint S-paths Problem
Find

Maximum Number of
Fully Vertex-Disjoint S-paths• Min-Max Formula [Mader 1978]

19

Mader’s Disjoint S-paths Problem
Find

Maximum Number of
Fully Vertex-Disjoint S-paths• Min-Max Formula [Mader 1978]• Reduction to Matroid Matching [Lovász 1980]– Alternative Proof for Mader’s Theorem– Polytime Solvability [Lovász 1981]
20

Mader’s Disjoint S-paths Problem
FindMaximum Number of
Fully Vertex-Disjoint S-paths• Min-Max Formula [Mader 1978]• Reduction to Matroid Matching [Lovász 1980]– Alternative Proof for Mader’s Theorem– Polytime Solvability [Lovász 1981]→ Improved via Linear Representation [Schrijver 2003]
21

Overview
Packing
Non-zero 𝑨-paths

Mader’s
Disjoint S-paths
Menger’s
Disjoint Paths

Packing
Odd-Length 𝐴-paths

Non-bipartite
Matching
22

Packing Non-zero 𝐴-paths
𝐺 = (𝑉, 𝐸): Group-Labeled Graph𝐴 ⊆ 𝑉: Terminal Set
𝐙-Labeled GraphGiven

𝐙 = 0, ±1, ±2, …

0101Find23−112∈𝐴∉𝐴

Maximum Number of
Fully Vertex-Disjoint Non-zero 𝐴-paths
23

Packing Non-zero 𝐴-paths
𝐺 = (𝑉, 𝐸): Group-Labeled Graph𝐴 ⊆ 𝑉: Terminal Set
𝐙-Labeled GraphGiven

𝐙 = 0, ±1, ±2, …

0

10

2

𝟏3 + −1 − 1 = 1
Find

𝟑−𝟏12

OK!!

∈𝐴
∉𝐴

Maximum Number of
Fully Vertex-Disjoint Non-zero 𝐴-paths
24

Packing Non-zero 𝐴-paths
𝐺 = (𝑉, 𝐸): Group-Labeled Graph𝐴 ⊆ 𝑉: Terminal Set
𝐙-Labeled GraphGiven

𝐙 = 0, ±1, ±2, …

0102

𝟏𝟑−𝟏121 − −1 − 3 = −1 OK!!
Find

∈𝐴
∉𝐴

Maximum Number ofFully Vertex-Disjoint Non-zero 𝐴-paths
25

Packing Non-zero 𝐴-paths
𝐺 = (𝑉, 𝐸): Group-Labeled Graph𝐴 ⊆ 𝑉: Terminal Set
𝐙-Labeled GraphGiven

𝐙 = 0, ±1, ±2, …

0102

13 + −1 − 2 = 0
Find

𝟑−𝟏1𝟐NG!!

∈𝐴∉𝐴

Maximum Number ofFully Vertex-Disjoint Non-zero 𝐴-paths
26

Packing Non-zero 𝐴-paths
𝐺 = (𝑉, 𝐸): Group-Labeled Graph𝐴 ⊆ 𝑉: Terminal Set
𝐙-Labeled GraphGiven

𝐙 = 0, ±1, ±2, …

0102

12 − −1 − 3 = 0Find

𝟑−𝟏1𝟐NG!!

∈𝐴∉𝐴

Maximum Number of
Fully Vertex-Disjoint Non-zero 𝐴-paths
27

Packing Non-zero 𝐴-paths
𝐺 = (𝑉, 𝐸): Group-Labeled Graph𝐴 ⊆ 𝑉: Terminal Set
𝐙-Labeled GraphGiven

𝐙 = 0, ±1, ±2, …

𝟎𝟏𝟎
1Find

2

𝟑−1

1𝟐

∈𝐴
∉𝐴

Maximum Number of
Fully Vertex-Disjoint Non-zero 𝐴-paths
28

Ex. 1 Mader’s S-paths

Given

S-path𝐴1Find𝐺 = (𝑉, 𝐸): Undirected Graph𝐴 ⊆ 𝑉: Terminal Set, S : Partition of 𝐴
𝐴2NOT S-path

S = 𝐴1 , 𝐴2 , 𝐴3Maximum Number of
Fully Vertex-Disjoint S-paths

𝐴3

∈𝐴
∉𝐴

29

Ex. 1 Mader’s S-paths

𝐺 = (𝑉, 𝐸): Group-Labeled Graph𝐴 ⊆ 𝑉: Terminal Set
𝐙-Labeled Graph
𝐙 = 0, ±1, ±2, …
𝐴2Given

𝟏𝐴1Find𝟏

S = 𝐴1 , 𝐴2 , 𝐴3

𝐴3

∈𝐴
∉𝐴

Maximum Number of
Fully Vertex-Disjoint Non-zero 𝐴-paths
30

Ex. 1 Mader’s S-paths

𝐺 = (𝑉, 𝐸): Group-Labeled Graph𝐴 ⊆ 𝑉: Terminal Set
𝐙-Labeled Graph
𝐙 = 0, ±1, ±2, …
𝐴2𝟐Given

𝟐1𝐴1Find

1

S = 𝐴1 , 𝐴2 , 𝐴3𝐴3

∈𝐴∉𝐴Maximum Number of
Fully Vertex-Disjoint Non-zero 𝐴-paths
31

Ex. 1 Mader’s S-paths

𝐺 = (𝑉, 𝐸): Group-Labeled Graph𝐴 ⊆ 𝑉: Terminal Set
𝐙-Labeled Graph
𝐙 = 0, ±1, ±2, …
𝐴22Given

𝟑21𝐴1Find

1

S = 𝐴1 , 𝐴2 , 𝐴3

𝟑𝟑𝐴3

∈𝐴
∉𝐴

Maximum Number of
Fully Vertex-Disjoint Non-zero 𝐴-paths
32

Ex. 1 Mader’s S-paths

𝐺 = (𝑉, 𝐸): Group-Labeled Graph𝐴 ⊆ 𝑉: Terminal Set
𝐙-Labeled Graph
𝐙 = 0, ±1, ±2, …
𝐴22Given

31𝐴1Find𝟎21

S = 𝐴1 , 𝐴2 , 𝐴3𝟎33𝐴3∈𝐴∉𝐴

Maximum Number of
Fully Vertex-Disjoint Non-zero 𝐴-paths
33

Ex. 1 Mader’s S-paths

𝐺 = (𝑉, 𝐸): Group-Labeled Graph𝐴 ⊆ 𝑉: Terminal Set
𝐙-Labeled Graph
𝐙 = 0, ±1, ±2, …
𝐴22Given

𝟑𝟏𝐴1Find

𝟎𝟐

1

S = 𝐴1 , 𝐴2 , 𝐴3𝟎𝟑

3𝐴3

∈𝐴
∉𝐴S-paths

Maximum Number of
Fully Vertex-Disjoint Non-zero 𝐴-paths
34

Ex. 2 Odd-Length 𝐴-paths
𝐺 = (𝑉, 𝐸): Group-Labeled Graph𝐴 ⊆ 𝑉: Terminal Set
𝐙 -Labeled Graph

Given

21111Find

111𝐙2 = 0, 1

mod 21

1∈𝐴∉𝐴

Maximum Number of
Fully Vertex-Disjoint Non-zero 𝐴-paths
35

Ex. 2 Odd-Length 𝐴-paths
𝐺 = (𝑉, 𝐸): Group-Labeled Graph𝐴 ⊆ 𝑉: Terminal Set
𝐙 -Labeled Graph

Given

2𝟏𝟏

𝟏
1

Find

𝟏

𝟏1

𝐙2 = 0, 1

mod 21∈𝐴∉𝐴

1

Odd-Length

Maximum Number ofFully Vertex-Disjoint Non-zero 𝐴-paths
36

Packing Non-zero 𝐴-paths
Find

Maximum Number of Fully Vertex-Disjoint
Non-zero 𝐴-paths• Min-Max Formula[Chudnovsky, Geelen, Gerards,Goddyn, Lohman, Seymour 2006]• Polytime Algorithm [Chudnovsky, Cunningham, Geelen 2008]37

Packing Non-zero 𝐴-paths
FindMaximum Number of Fully Vertex-Disjoint
Non-zero 𝐴-paths• Min-Max Formula[Chudnovsky, Geelen, Gerards,Goddyn, Lohman, Seymour 2006]• Polytime Algorithm [Chudnovsky, Cunningham, Geelen 2008]• Reduction to Matroid Matching [Tanigawa, Y. 2015]→ Alternative Proofs for Min-Max and Polytime
38Overview
Packing
Non-zero 𝐴-paths[Tanigawa, Y. 2015][Lovász 1980]

Matroid
Matching

Mader’s
Disjoint S-paths
Menger’s
Disjoint Paths

Non-bipartite
MatchingMatroidIntersection
39

Matroid Matching Problem
Given

𝐺 = (𝑉, 𝐸): Undirected Graph
𝐌 = 𝑉, I : Matroid on Vertex Set

Find Maximum Matching with Matroid Constraint40

Matroid Matching Problem
Given

𝐺 = (𝑉, 𝐸): Undirected Graph
𝐌 = 𝑉, I : Matroid on Vertex Set

I ⊆ 2𝑉 (Family of Independent Sets)• ∅∈I• 𝑋⊆𝑌∈I ⟹ 𝑋∈I• 𝑋, 𝑌 ∈ I and 𝑋 < 𝑌⟹ ∃𝑣 ∈ 𝑌 ∖ 𝑋 s.t. 𝑋 + 𝑣 ∈ I

Find Maximum Matching with Matroid Constraint
41

Matroid Matching Problem
Given

𝐺 = (𝑉, 𝐸): Undirected Graph
𝐌 = 𝑉, I : Matroid on Vertex Set∈IFind Maximum Matching with Matroid Constraint
42

Matroid Matching Problem
Given

𝐺 = (𝑉, 𝐸): Undirected Graph
𝐌 = 𝑉, I : Matroid on Vertex Set

Find Maximum Matching
𝐌 = 𝑉, 2𝑉 : Free Matroid ⟹ Maximum Matching43

Matroid Matching Problem
Given (𝑆, 𝑓): 2-polymatroid
def

𝑆: Finite Set, 𝑓: 2𝑆 → 𝐙• 0≤𝑓 𝑋 ≤2𝑋
𝑋⊆𝑆• 𝑓 𝑋 ≤𝑓 𝑌𝑋⊆𝑌⊆𝑆• 𝑓 𝑋 +𝑓 𝑌 ≥𝑓 𝑋∪𝑌 +𝑓 𝑋∩𝑌𝑋, 𝑌 ⊆ 𝑆
Find Maximum Matching
𝑋 ⊆ 𝑆 with 𝑓 𝑋 = 2 𝑋
44

Matroid Matching Problem
Given (𝑆, 𝑓): 2-polymatroid
Find Maximum Matching• In General, NOT Polytime Solvable

45

Matroid Matching Problem
Given (𝑆, 𝑓): 2-polymatroid
Find Maximum Matching• In General, NOT Polytime Solvable

𝑓 𝑋 = rank ∗∗• In Linear Case (or More General Case)
𝑋– Min-Max Formula [Lovász 1980]
𝑆– Polytime Solvable[Lovász 1981]
O 𝑚17 ?
[Gabow, Stallmann 1986]
O 𝑚𝑛3 (Combinatorial)
O 𝑚𝑛2 (Algebraic, w.h.p.) [Cheung, Law, Leung 2011]46

Overview
Packing
Non-zero 𝑨-paths[Tanigawa, Y. 2015][Lovász 1980]

MatroidMatching

Mader’s
Disjoint S-paths

47

Reduction Flow
Packing
Non-zero 𝐴-paths

Matroid
Matching
𝑆, 𝑓 : 2-polymatroid

Solve

Solve

𝑋⊆𝑆with𝑓 𝑋 =2𝑋
48

Reduction Flow
Packing
Non-zero 𝐴-paths

ReduceConstruct

Matroid
Matching
𝑆, 𝑓 : 2-polymatroid
Solve

𝑋⊆𝑆
Reconstruct

with𝑓 𝑋 =2𝑋
49

Reduction Flow
Packing
Non-zero 𝐴-paths

ReduceHow?
Construct

Matroid
Matching
𝑆, 𝑓 : 2-polymatroid
Solve

How?

Reconstruct

𝑋⊆𝑆with𝑓 𝑋 =2𝑋
50

Our 2-polymatroid• We want a Subgraph
𝑋⊆𝑆

Reconstruct

with𝑓 𝑋 =2𝑋

51

Our 2-polymatroid• We want a Subgraph→𝑆 ≔ 𝐸 (Edge Set)
𝑋⊆𝐸

Reconstruct

with𝑓 𝑋 =2𝑋52

Our 2-polymatroid• We want a Subgraph→𝑆 ≔ 𝐸 (Edge Set)
𝑋⊆𝐸Reconstruct

with𝑓 𝑋 =2𝑋• We want Easy Reconstruction

???

53

Our 2-polymatroid• We want a Subgraph→𝑆 ≔ 𝐸 (Edge Set)
𝑋⊆𝐸

Reconstruct

with𝑓 𝑋 =2𝑋• We want Easy Reconstruction
Non-zero⟺𝑓 𝑋 =2𝑋

𝐺 𝑋 : Forest
54

Key Concept in Our Reduction
Non-zero
Frame Matroid

GeneralizedCycle Matroid

Bicircular Matroid55

Key Concept in Our Reduction
Non-zero
Frame Matroid• Extends to 2-polymatroid• Magic for Terminals
Non-zero⟺𝑓 𝑋 =2𝑋

𝐺 𝑋 : Forest56

Maximal Matching𝑓 𝑋 =2𝑋

𝐺𝑋

Non-zero⟺𝑓 𝑋 =2𝑋

𝐺 𝑋 : Forest
57

Maximal Matching
Assume
𝐺: Connected
𝑓 𝑋 =2𝑋

𝐺𝑋

Non-zero⟺𝑓 𝑋 =2𝑋

𝐺 𝑋 : Forest
58

Maximal Matching𝑒Assume
𝐺: Connected
𝑓 𝑋+𝑒 =2 𝑋+𝑒

𝐺 𝑋+𝑒

Non-zero⟺𝑓 𝑋 =2𝑋

𝐺 𝑋 : Forest
59

Maximal Matching𝑒Assume
𝐺: Connected
𝑓 𝑋+𝑒 =2 𝑋+𝑒

𝐺 𝑋+𝑒
𝐺: Connected
Non-zero⟺

𝑋: Maximal
𝑓 𝑋 =2𝑋

𝐺 𝑋 : Forest
60

Maximum Matching
𝑋: Maximal⟹ 𝑋 = 𝑉 − # Connected Components
𝑓 𝑋 =2𝑋
cf. 𝐺 ′ = 𝑉 ′ , 𝐸 ′ : Tree𝐸′ = 𝑉 ′ − 1

𝐺: Connected
Non-zero⟺

𝑋: Maximal
𝑓 𝑋 =2𝑋

𝐺 𝑋 : Forest
61

Maximum Matching
𝑋: Maximal⟹ 𝑋 = 𝑉 − # Connected Components
𝑓 𝑋 =2𝑋
𝐴 − # Non−zero 𝐴−paths

𝐺: Connected
Non-zero⟺

𝑋: Maximal
𝑓 𝑋 =2𝑋

𝐺 𝑋 : Forest
62

Maximum Matching
𝑋: Maximal⟹ 𝑋 = 𝑉 − # Connected Components
𝑓 𝑋 =2𝑋
𝐴 − # Non−zero 𝐴−paths
Non-zero
𝐺: Connected
Non-zero⟺

𝑋: Maximal
𝑓 𝑋 =2𝑋

𝐺 𝑋 : Forest
63

Maximum Matching
𝑋: Maximal⟹ 𝑋 = 𝑉 − 𝐴 + # Non−zero 𝐴−paths
𝑓 𝑋 =2𝑋

𝐺: Connected
Non-zero⟺

𝑋: Maximal
𝑓 𝑋 =2𝑋

𝐺 𝑋 : Forest64

Maximum Matching
𝑋: Maximal⟹ 𝑋 = 𝑉 − 𝐴 + # Non−zero 𝐴−paths
𝑓 𝑋 =2𝑋
Fixed
Maximized⟺

Maximized

𝐺: Connected
Non-zero⟺

𝑋: Maximal
𝑓 𝑋 =2𝑋

𝐺 𝑋 : Forest
65

Conclusion
Packing Non-zero 𝐴-paths reduces to Matroid Matching• Extends Lovász’s Reduction [Lovász 1980]of Mader’s S-paths Problem to Matroid Matching• Alternative Proof for Min-Max Formula[Chudnovsky, Geelen, Gerards,Goddyn, Lohman, Seymour 2006]• Alternative Polytime Algorithm via Matroid Matching[Lovász 1981](cf. Faster Algorithms via Linear Matroid Parity
under Representability Cond. for Group) [Y. 2014]
66

Min-Max Formula for Non-zero 𝐴-paths
𝜇 𝐺, 𝐴 ≔ max # Disjoint Non−zero 𝐴−paths in 𝐺
𝜇 𝐺, 𝐴 ≔ max # Disjoint 𝐴−paths in 𝐺

𝜇 𝐺, 𝐴 ≤ 𝜇 𝐺 − 𝐹, 𝐴𝐹• 𝐹 ⊆ 𝐸 𝐺 Contains NO Non-zero 𝐴-paths• 𝐴𝐹 ≔ 𝐴 ∪ 𝑉 𝐹𝐹Non-zero𝐴-path
𝐺, 𝐴

𝐺 − 𝐹, 𝐴𝐹68

Min-Max Formula for Non-zero 𝐴-paths
𝜇 𝐺, 𝐴 ≔ max # Disjoint Non−zero 𝐴−paths in 𝐺
𝜇 𝐺, 𝐴 ≔ max # Disjoint 𝐴−paths in 𝐺

𝜇 𝐺, 𝐴 ≤ 𝜇 𝐺 − 𝐹, 𝐴𝐹• 𝐹 ⊆ 𝐸 𝐺 Contains NO Non-zero 𝐴-paths• 𝐴𝐹 ≔ 𝐴 ∪ 𝑉 𝐹𝐴𝐹 -path
Non-zero𝐴-path
𝐺, 𝐴

𝐺 − 𝐹, 𝐴𝐹69

Min-Max Formula for Non-zero 𝐴-paths
𝜇 𝐺, 𝐴 ≔ max # Disjoint Non−zero 𝐴−paths in 𝐺
𝜇 𝐺, 𝐴 ≔ max # Disjoint 𝐴−paths in 𝐺

𝜇 𝐺, 𝐴 ≤ 𝜇 𝐺 − 𝐹, 𝐴𝐹≤ 𝜇 𝐺 − 𝐹 − 𝑋, 𝐴𝐹 ∖ 𝑋 + |𝑋|• 𝐹 ⊆ 𝐸 𝐺 Contains NO Non-zero 𝐴-paths• 𝐴𝐹 ≔ 𝐴 ∪ 𝑉 𝐹• 𝑋⊆𝑉 𝐺𝐺 − 𝐹, 𝐴𝐹70

Min-Max Formula for Non-zero 𝐴-paths
𝜇 𝐺, 𝐴 ≔ max # Disjoint Non−zero 𝐴−paths in 𝐺
𝜇 𝐺, 𝐴 ≔ max # Disjoint 𝐴−paths in 𝐺

𝜇 𝐺, 𝐴 ≤ 𝜇 𝐺 − 𝐹, 𝐴𝐹≤ 𝜇 𝐺 − 𝐹 − 𝑋, 𝐴𝐹 ∖ 𝑋 + |𝑋|• 𝐹 ⊆ 𝐸 𝐺 Contains NO Non-zero 𝐴-paths• 𝐴𝐹 ≔ 𝐴 ∪ 𝑉 𝐹• 𝑋⊆𝑉 𝐺𝐺 − 𝐹, 𝐴𝐹𝑋
71

Min-Max Formula for Non-zero 𝐴-paths
𝜇 𝐺, 𝐴 ≔ max # Disjoint Non−zero 𝐴−paths in 𝐺
𝜇 𝐺, 𝐴 ≔ max # Disjoint 𝐴−paths in 𝐺

𝜇 𝐺, 𝐴 ≤ 𝜇 𝐺 − 𝐹, 𝐴𝐹≤ 𝜇 𝐺 − 𝐹 − 𝑋, 𝐴𝐹 ∖ 𝑋 + |𝑋|≤𝐻∈comp 𝐺−𝐹−𝑋

𝑉 𝐻 ∩𝐴𝐹
2+ 𝑋• 𝐹 ⊆ 𝐸 𝐺 Contains NO Non-zero 𝐴-paths• 𝐴𝐹 ≔ 𝐴 ∪ 𝑉 𝐹
𝐻: Conn. Comp.
• 𝑋⊆𝑉 𝐺72

Min-Max Formula for Non-zero 𝐴-paths
𝜇 𝐺, 𝐴 ≔ max # Disjoint Non−zero 𝐴−paths in 𝐺

Thm.
𝜇 𝐺, 𝐴 = min𝐹, 𝑋𝐻∈comp 𝐺−𝐹−𝑋

𝑉 𝐻 ∩ 𝐴𝐹+ 𝑋
2• 𝐹 ⊆ 𝐸 𝐺 Contains NO Non-zero 𝐴-paths• 𝐴𝐹 ≔ 𝐴 ∪ 𝑉 𝐹• 𝑋⊆𝑉 𝐺
[Chudnovsky, Geelen, Gerards,Goddyn, Lohman, Seymour 2006]

73