Packing Non-zero 𝑨-paths
via Linear Matroid Parity
Yutaro Yamaguchi
Department of Mathematical Informatics
University of Tokyo
CWCO 2015 @Cargèse

September 17, 2015

Overview

Menger’s
Disjoint Paths

Non-bipartite
Matching2

Overview

Mader’s
Disjoint S-paths[Mader 1978]

Generalized
Menger’s
Disjoint Paths

Non-bipartite
Matching
3

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

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

Packing
Odd-Length 𝐴-paths

Non-bipartite
Matching
4

Overview
Packing
Non-zero 𝐴-paths

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

O 𝑉 5 -time Algorithm[Chudnovsky, Cunningham, Geelen 2008]

O 𝑉 2.373 -time Algorithm
via Linear Matroid Parity[Schrijver 2003][Cheung, Law, Leung 2014]

Non-bipartite
Matching
5Overview
Packing
Non-zero 𝐴-paths

O 𝑉 5 -time Algorithm[Chudnovsky, Cunningham, Geelen 2008]

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

O 𝑉 2.373 -time Algorithm
via Linear Matroid Parity[Schrijver 2003][Cheung, Law, Leung 2014]

Non-bipartite
Matching
6OverviewPacking
Non-zero 𝐴-paths

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

Non-bipartiteMatching7

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

NOT 𝐴-paths8

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

𝐴2

∈𝐴
∉𝐴S-path

NOT S-path

𝐴2𝐴1𝐴1𝐴3𝐴39

Mader’s Disjoint S-paths ProblemGiven

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

𝐴1
Find

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

10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

11Mader’s Disjoint S-paths Problem
Find

Maximum Number of
Fully Vertex-Disjoint S-paths• Min-Max Duality[Mader 1978]• Polytime via Matroid Matching[Lovász 1980, 1981]

12

Mader’s Disjoint S-paths Problem
Find

Maximum Number ofFully Vertex-Disjoint S-paths• Min-Max Duality[Mader 1978]• Polytime via Matroid Matching [Lovász 1980, 1981][Schrijver 2003]→ Linear Representation→ O 𝑉 𝜔 -time Algorithm via Linear Matroid Parity[Cheung, Law, Leung 2014]𝜔 < 2.373
13

Overview
Packing
Non-zero 𝑨-paths

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

Packing
Odd-Length 𝐴-paths

Non-bipartite
Matching
14

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
15

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

𝐙 = 0, ±1, ±2, …

0

10

2

𝟏3 + −1 − 1 = 1Find

𝟑−𝟏12

OK!!

∈𝐴
∉𝐴

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

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

𝐙 = 0, ±1, ±2, …

0102

13 + −1 − 2 = 0Find

𝟑−𝟏1𝟐NG!!

∈𝐴∉𝐴

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

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

𝐙 = 0, ±1, ±2, …

0102

12 − −1 − 3 = 0
Find

𝟑−𝟏1𝟐NG!!

∈𝐴∉𝐴

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

Ex. 1 Mader’s S-paths

Given

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

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

𝐴3

∈𝐴
∉𝐴

19

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
20

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
21

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
22

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
23

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
24

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

Given

21111Find11
1

𝐙2 = 0, 1

mod 2

11

∈𝐴
∉𝐴

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

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

Given

2

𝟏

𝟏

𝟏
1Find

𝟏

𝟏
1

𝐙2 = 0, 1

mod 2

1

∈𝐴
∉𝐴

1

Odd-Length

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

Packing Non-zero 𝐴-paths
Find

Maximum Number of Fully Vertex-Disjoint
Non-zero 𝐴-paths• Min-Max Duality[Chudnovsky, Geelen, Gerards,Goddyn, Lohman, Seymour 2006]• O 𝑉 5 -time Algorithm [Chudnovsky, Cunningham, Geelen 2008]27

Packing Non-zero 𝐴-paths
FindMaximum Number of Fully Vertex-Disjoint
Non-zero 𝐴-paths• Min-Max Duality[Chudnovsky, Geelen, Gerards,Goddyn, Lohman, Seymour 2006]• O 𝑉 5 -time Algorithm [Chudnovsky, Cunningham, Geelen 2008]→ Improvable??
28

Overview
Packing
Non-zero 𝐴-paths

O 𝑉 5 -time Algorithm[Chudnovsky, Cunningham, Geelen 2008]

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

O 𝑉 2.373 -time Algorithm
via Linear Matroid Parity[Schrijver 2003][Cheung, Law, Leung 2014]

Non-bipartite
Matching29Linear Matroid Parity Problem
Given

𝑍 ∈ 𝐅 𝑛×2𝑚 : Matrix with Pairing of Columns

1000000
Find

01000000010000000
100000001
0000000
10000000
10000211

Maximum Number ofLinearly Independent Column-Pairs
30

Linear Matroid Parity Problem
Given

𝑍 ∈ 𝐅 𝑛×2𝑚 : Matrix with Pairing of Columns

Full Rank
rank = 6Find

10000000100000001000000010000000100000001000000010000211

Maximum Number ofLinearly Independent Column-Pairs
31

Linear Matroid Parity Problem
Given𝑍 ∈ 𝐅 𝑛×2𝑚 : Matrix with Pairing of Columns

1000000
Find

010000000
10000000
10000000100000001000000010000211NOTFull Rank
rank = 3

Maximum Number ofLinearly Independent Column-Pairs
32

Linear Matroid Parity Problem
FindMaximum Number ofLinearly Independent Column-Pairs• Min-Max Duality𝑛-Dim.

Full Rank[Lovász 1980]• Polytime Solvable(First Polytime)
O 𝑚17 ?
(Deterministic)
O 𝑚𝑛𝜔
(Randomized)
O 𝑚𝑛𝜔−1𝑚 Pairs[Lovász 1981][Gabow, Stallmann 1986][Cheung, Law, Leung 2014](𝜔 < 2.373: Matrix Multiplication Exponent)
33

Reduction Flow
Packing
Non-zero 𝐴-paths

Solve

Linear Matroid Parity

Solve
Full Rank
34

Reduction Flow
Packing
Non-zero 𝐴-paths

ReduceLinear Matroid Parity

ConstructSolve

ReconstructFull Rank
35

Reduction Flow
Packing
Non-zero 𝐴-paths

ReduceLinear Matroid Parity

How?
Construct
SolveHow?
Reconstruct

Full Rank
36

Associated Matrix• We want a Subgraph

Reconstruct

Full Rank

37

Associated Matrix• We want a Subgraph→

Edge ↔ Column-Pair

Reconstruct

Full Rank

38

Associated Matrix• We want a Subgraph→

Edge ↔ Column-Pair

Reconstruct

Full Rank• We want Easy Reconstruction

???

39

Associated Matrix• We want a Subgraph→

Edge ↔ Column-Pair

Reconstruct

Full Rank• We want Easy Reconstruction
Uniqueand⟺ Full Rank
Non-zero40Sufficient Condition
Γ: Group, 𝐅: Field, 𝜌: Γ → GL 2, 𝐅 Homomorphics.t. 𝜌 𝛼 10 ∥ 10 ⇔ 𝛼 = 1Γ∃Associated Matrix

GL 2, 𝐅 : Set of All Nonsingular 2 × 2 Matrices over 𝐅Uniqueand⟺ Full Rank
Non-zero41

Sufficient Condition
Γ: Group, 𝐅: Field, 𝜌: Γ → GL 2, 𝐅 Homomorphics.t. 𝜌 𝛼 10 ∥ 10 ⇔ 𝛼 = 1Γ∃Associated Matrix

GL 2, 𝐅 : Set of All Nonsingular 2 × 2 Matrices over 𝐅𝜌 𝛼𝛼 ∈ Γ ∖ 1Γ⟹101042

Intuitive Idea
Γ: Group, 𝐅: Field, 𝜌: Γ → GL 2, 𝐅 Homomorphics.t. 𝜌 𝛼 10 ∥ 10 ⇔ 𝛼 = 1Γ• Terminals in 𝐴 are associated with 10• Edges carry vectors with acting

𝛼1𝛼2𝛼𝑘101043

Intuitive Idea
Γ: Group, 𝐅: Field, 𝜌: Γ → GL 2, 𝐅 Homomorphics.t. 𝜌 𝛼 10 ∥ 10 ⇔ 𝛼 = 1Γ• Terminals in 𝐴 are associated with 10• Edges carry vectors with acting
𝜌 𝛼1𝛼1𝛼210𝛼𝑘1044

Intuitive Idea
Γ: Group, 𝐅: Field, 𝜌: Γ → GL 2, 𝐅 Homomorphic
s.t. 𝜌 𝛼 10 ∥ 10 ⇔ 𝛼 = 1Γ• Terminals in 𝐴 are associated with 10• Edges carry vectors with acting

𝛼1𝛼𝑘𝛼210

𝜌 𝛼2 𝜌 𝛼11045

Intuitive Idea
Γ: Group, 𝐅: Field, 𝜌: Γ → GL 2, 𝐅 Homomorphics.t. 𝜌 𝛼 10 ∥ 10 ⇔ 𝛼 = 1Γ• Terminals in 𝐴 are associated with 10• Edges carry vectors with acting

𝛼1𝛼𝑘𝛼210

𝜌 𝛼2 𝛼11046

Intuitive Idea
Γ: Group, 𝐅: Field, 𝜌: Γ → GL 2, 𝐅 Homomorphic
s.t. 𝜌 𝛼 10 ∥ 10 ⇔ 𝛼 = 1Γ• Terminals in 𝐴 are associated with 10• Edges carry vectors with acting

𝛼1𝛼2𝛼𝑘10𝜌 𝛼𝑘 ⋯ 𝛼2 𝛼11047

Intuitive Idea
Γ: Group, 𝐅: Field, 𝜌: Γ → GL 2, 𝐅 Homomorphic
s.t. 𝜌 𝛼 10 ∥ 10 ⇔ 𝛼 = 1Γ

𝜌 𝛼𝑘 ⋯ 𝛼2 𝛼1 10 ∦ 10
Linearly Independent𝛼1𝛼2⇔ 𝛼𝑘 ⋯ 𝛼2 𝛼1 ≠ 1ΓNon-zero𝛼𝑘
10

𝜌 𝛼𝑘 ⋯ 𝛼2 𝛼11048

Matrix Construction (Step 1)
Γ: Group, 𝐅: Field, 𝜌: Γ → GL 2, 𝐅 Homomorphic
s.t. 𝜌 𝛼 10 ∥ 10 ⇔ 𝛼 = 1Γ• Based on the Incidence Matrix𝑒𝑣

𝛼𝑢∈𝐴𝑢𝑒𝑣𝟎1𝟎−1𝟎49

Matrix Construction (Step 1)
Γ: Group, 𝐅: Field, 𝜌: Γ → GL 2, 𝐅 Homomorphic
s.t. 𝜌 𝛼 10 ∥ 10 ⇔ 𝛼 = 1Γ• Based on the Incidence Matrix• Replace ±1 with 𝐼2 and −𝜌 𝛼𝑣

𝛼𝑢∈𝐴𝑢𝑒𝑒𝑒𝑣𝟎1𝟎−1𝟎→𝑢𝑣

𝑂𝐼2𝑂−𝜌 𝛼𝑂
Paired50

Matrix Construction (Step 2)
Γ: Group, 𝐅: Field, 𝜌: Γ → GL 2, 𝐅 Homomorphic
s.t. 𝜌 𝛼 10 ∥ 10 ⇔ 𝛼 = 1Γ
• 𝑄 ≔ 𝑥 ∈ 𝐅 2 𝑉 𝑥𝑢 ∥10𝑢 ∈ 𝐴 , 𝑥𝑣 = 𝟎 𝑣 ∉ 𝐴• Linear Independence in 𝐅 2 𝑉 /𝑄𝑒𝑣
𝑂𝐼2𝑢𝛼10𝑒𝑢∈𝐴𝑣

𝑂−𝜌 𝛼𝑂𝑢𝟎10⋮𝟎⋮Begin with
Basis of 𝑄
51

Matrix Construction (Step 2)
Γ: Group, 𝐅: Field, 𝜌: Γ → GL 2, 𝐅 Homomorphics.t. 𝜌 𝛼 10 ∥ 10 ⇔ 𝛼 = 1Γ
• 𝑄 ≔ 𝑥 ∈ 𝐅 2 𝑉 𝑥𝑢 ∥10𝑢 ∈ 𝐴 , 𝑥𝑣 = 𝟎 𝑣 ∉ 𝐴• Linear Independence in 𝐅 2 𝑉 /𝑄𝑒𝑣
𝑂𝐼2𝑢𝛼10𝑒𝑢∈𝐴𝑣

𝑂−𝜌 𝛼𝑂𝑢𝟎10⋮𝟎⋮

Eliminate in advance

Begin with
Basis of 𝑄
52

Ex. 1 Mader's S-paths

Γ: Group, 𝐅: Field, 𝜌: Γ → GL 2, 𝐅 Homomorphics.t. 𝜌 𝛼 10 ∥ 10 ⇔ 𝛼 = 1Γ
Γ = 𝐙 = 0, ±1, ±2, …

𝐴𝑖

𝑖−𝑖𝑗00−𝑗𝐴𝑗

S-paths
Non-zero53

Ex. 1 Mader's S-paths

Γ: Group, 𝐅: Field, 𝜌: Γ → GL 2, 𝐅 Homomorphics.t. 𝜌 𝛼 10 ∥ 10 ⇔ 𝛼 = 1Γ
Γ = 𝐙 = 0, ±1, ±2, … , 𝐅 = 𝐐: Rational Field1𝜌 𝑘 =𝑘𝜌 𝑘𝐴𝑖

1
0=011𝑘𝑖−𝑖∥𝑘∈𝐙
10𝑗00−𝑗⇔ 𝑘=0
𝐴𝑗

S-paths
Non-zero54

Ex. 2 Odd-Length 𝐴-paths
Γ: Group, 𝐅: Field, 𝜌: Γ → GL 2, 𝐅 Homomorphics.t. 𝜌 𝛼 10 ∥ 10 ⇔ 𝛼 = 1Γ
Γ = 𝐙2 = 0, 1

mod 21
11

111

Odd-Length
Non-zero55

Ex. 2 Odd-Length 𝐴-paths
Γ: Group, 𝐅: Field, 𝜌: Γ → GL 2, 𝐅 Homomorphic
s.t. 𝜌 𝛼 10 ∥ 10 ⇔ 𝛼 = 1Γ
Γ = 𝐙2 = 0, 11
𝜌 0 =0𝜌 0

10=10

mod 2 , 𝐅: Arbitrary Field
0,
11,0

∥0
𝜌 1 =1
𝜌 1

1
1

1

1

1
110

=100
1

∦

10

Odd-Length
Non-zero56

Sufficient Condition
Γ: Group, 𝐅: Field, 𝜌: Γ → GL 2, 𝐅 Homomorphic
s.t. 𝜌 𝛼 10 ∥ 10 ⇔ 𝛼 = 1ΓReducible to Linear Matroid Parity

GL 2, 𝐅 : Set of All Nonsingular 2 × 2 Matrices over 𝐅57

Sufficient Condition
Γ: Group, 𝐅: Field, 𝜌: Γ → PGL 2, 𝐅 Homomorphics.t. 𝜌 𝛼 10 ∥ 10 ⇔ 𝛼 = 1ΓReducible to Linear Matroid Parity

GL 2, 𝐅 : Set of All Nonsingular 2 × 2 Matrices over 𝐅𝑘 0
PGL 2, 𝐅 ≔ GL 2, 𝐅 /∣𝑘 ∈𝐅∖ 00 𝑘
∀𝑍 ∈ GL 2, 𝐅 , ∀𝑘 ∈ 𝐅 ∖ 0 ,𝑍 ∼ 𝑘𝑍58

Necessary and Sufficient Condition
Γ: Group, 𝐅: Field, 𝜌: Γ → PGL 2, 𝐅 Homomorphics.t. 𝜌 𝛼 10 ∥ 10 ⇔ 𝛼 = 1ΓReducible to L.M.P. with Coherent Representation𝑒 = 𝑢𝑣 ∈ 𝐸𝑢𝑣

𝑂∗
𝑂∗𝑂
Paired ∗: 2 × 2 MatrixNon-zero⇒ Full Rank

⇒ NOT Full RankZero59

Conclusion• Packing Non-zero 𝑨-paths
is efficiently solvable via Linear Matroid Parity
under some Group Representability condition.
O 𝑉 5 -time

O 𝑉 2.373 -time[Chudnovsky, Cunningham, Geelen 2008][Cheung, Law, Leung 2014]• The same condition is also Necessaryfor Reasonable Reduction to L.M.P.
60

Extension
Our Result is Extendable to the following cases• Subgroup-Forbidden ModelΓ ′ : Proper Subgroup of Γ, Set of Forbidden Labels
Idea 𝜌 𝛼10∥10

⇔ 𝛼 = 1Γ 𝛼 ∈ Γ ′• Weighted Setting → Weighted Linear Matroid Parity[Iwata 2013] [Pap 2013]
𝑐: 𝐸 → 𝐑 (Edge Cost), 𝑘 ∈ 𝐙+
Finding Minimum Cost 𝑘 Disjoint Non-zero 𝐴-paths
Idea Add Dummy Terminals (cf. Weighted Matching)61