Shortest Disjoint S-paths
via Weighted Linear Matroid Parity
Yutaro Yamaguchi
Osaka University, JapanISAAC 2016 @Sydney

December 12, 2016

Overview
Find Maximum-Cardinality Feasible Solution

P
Disjoint S-paths

Polytime
via Linear Matroid Parity[Lovász 1980, 1981][Schrijver 2003]

𝑠𝑡

Disjoint
𝑠–𝑡 Paths

Non-bipartite
Matching

Bipartite Matching1

Overview
Find Minimum-Cost Fixed-Cardinality Feasible Solution
Disjoint S-paths

Open for a long timeP
𝑠𝑡

Disjoint
𝑠–𝑡 Paths

Non-bipartiteMatching

Min-cost Flow

Weighted Matching

Assignment Problem Bipartite Matching2

Overview
Find Minimum-Cost Fixed-Cardinality Feasible Solution

P
Disjoint S-paths𝑠𝑡

Disjoint
𝑠–𝑡 Paths

Open for a long time
Polytime
via Weighted L.M.P.

Non-bipartite
Matching

Min-cost Flow

Weighted Matching

Assignment Problem Bipartite Matching3

Successful Scenario

Cardinalityver.

Weightedver.

Disjoint S-paths

Linear Matroid Parity

Polytime

Polytime

Reduce[Lovász 1980][Schrijver 2003]

Polytime?? Reduce?

e.g.,[Lovász 1981][Gabow–Stallmann 1986][Cheung–Lau–Leung 2016]

Polytime?

4

Successful Scenario

Cardinalityver.

Weightedver.

Disjoint S-paths

Linear Matroid Parity

Polytime

PolytimeReduce[Lovász 1980][Schrijver 2003]

Polytime?? Reduce?

e.g.,[Lovász 1981][Gabow–Stallmann 1986][Cheung–Lau–Leung 2016]

Polytime!
Announced by[Iwata 2013][Pap 2013]5

Successful Scenario

Cardinalityver.

Weightedver.

Disjoint S-paths

Linear Matroid Parity

Polytime

Polytime

Reduce[Lovász 1980][Schrijver 2003]

Polytime!

Reduce!

[This Talk]

e.g.,[Lovász 1981][Gabow–Stallmann 1986][Cheung–Lau–Leung 2016]

Polytime
Announced by[Iwata 2013][Pap 2013]6

Outline• Preliminaries– Disjoint S-paths– Linear Matroid Parity– Reduction in Cardinality Case• Result– How to Extend to Weighted Case

• Conclusion
7

Outline• Preliminaries– Disjoint S-paths– Linear Matroid Parity– Reduction in Cardinality Case

• Result– How to Extend to Weighted Case

• Conclusion8

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

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

NOT S-path

𝐴2𝐴1𝐴1𝐴3𝐴310

Disjoint S-paths Problem
Given

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

FindMaximum Number of Vertex-Disjoint S-paths
11

Shortest Disjoint S-paths Problem
Given

𝐺 = 𝑉, 𝐸 : Undirected Graph𝐴 ⊆ 𝑉: Terminal Set, S : Partition of 𝐴ℓ: 𝐸 → 𝐑 ≥0 Edge Length, 𝑘 ∈ 𝐙>0ℓ≡𝟏
𝑘=2

2+2=4<5=2+3

Find

Totally Shortest 𝑘 Vertex-Disjoint S-paths
12Outline• Preliminaries– Disjoint S-paths– Linear Matroid Parity– Reduction in Cardinality Case• Result– How to Extend to Weighted Case

• Conclusion
13

Linear Matroid Parity Problem
Given

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

1000000Find

010000000100000001000000010000000
10000000
10000211Maximum Number ofLinearly Independent Column-Pairs
14Linear Matroid Parity Problem
Given

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

Full Rankrank = 6Find

10000000100000001000000010000000100000001000000010000211

Maximum Number ofLinearly Independent Column-Pairs
15

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

1000000
Find

0
10000000
10000000
10000000
10000000
10000000
10000
211NOT
Full Rank
rank = 3

Maximum Number ofLinearly Independent Column-Pairs
16

Weighted Linear Matroid Parity Problem
𝑍 ∈ 𝐅 𝑟×2𝑚 : Matrix with Pairing of Columns
𝑤: 𝑚 → 𝐑 Weight on Column-Pairs

Given
10000000100000𝟐Find

0010000000
1000

𝟑00001000000010

1000000
10000211−𝟏

4<6100
00000
1
00000

𝟐00
1
00000001000

𝟑00001000000010𝟏00000010000211−1

Max. Linearly Independent Column-Pairs
with Minimum Total Weight17

Outline• Preliminaries– Disjoint S-paths– Linear Matroid Parity– Reduction in Cardinality Case

• Result– How to Extend to Weighted Case

• Conclusion
18

Reduction Sketch[Lovász 1980][Schrijver 2003]

Disjoint S-paths

ReduceLinear Matroid Parity

Construct

Solve

Reconstruct

Full Rank
19

Reduction Sketch[Lovász 1980][Schrijver 2003]

Disjoint S-paths

ReduceLinear Matroid ParityHow?
Construct

Solve
How?
Reconstruct

Full Rank
20

Associated Matrix[Lovász 1980][Schrijver 2003]• We want a Subgraph

Reconstruct

Full Rank

21

Associated Matrix[Lovász 1980][Schrijver 2003]• We want a Subgraph→

Edge ↔ Column-Pair

Reconstruct

Full Rank

22

Associated Matrix[Lovász 1980][Schrijver 2003]• We want a Subgraph→

Edge ↔ Column-Pair

Reconstruct

Full Rank• We want Easy Reconstruction???

23

Associated Matrix[Lovász 1980][Schrijver 2003]• We want a Subgraph→

Edge ↔ Column-Pair

Reconstruct

Full Rank• We want Easy Reconstruction
In each tree
at most one
𝑨-path,⟺which isForest
S-pathFull Rank
24

Summary of Reduction[Lovász 1980][Schrijver 2003]

Disjoint S-paths

Linear Matroid Parity∃Max.-Card. Solution ⊆ ∀Max.-Card. Solution
Cardinality• Uniquever.
• Easy to Extract

ForestIn each tree
at most one𝑨-path,⟺
which isS-path

Full Rank25

What is Difficult to Extend?
Disjoint S-paths

Linear Matroid Parity∃Max.-Card. Solution ⊆ ∀Max.-Card. Solution
Cardinality• Uniquever.
• Easy to Extract

Weightedver.

Differ.-Card. Sols. ⊆ Fixed-Card. Sols.

Extraction does NOT preserve Total Weight

Nontrivial but Possible to Overcome!
26

Outline• Preliminaries– Disjoint S-paths– Linear Matroid Parity– Reduction in Cardinality Case

• Result– How to Extend to Weighted Case

• Conclusion
27

Ideas to Overcome Difficulties• Violation of Cardinality Constraint
Make a Gadget to Convert
All Fixed-Card. Sols. to All Max.-Card. Sols.
cf. ∀Max. Sol. in L.M.P. ⊇ ∃!Max. S-paths• Change of Total Weight by Extraction

Add Dummy Elements of Weight 0 so that
They do NOT affect Original S-paths Problem→ Incentive to Use Dummy Elements in W.L.M.P.
28

Ideas to Overcome Difficulties• Violation of Cardinality Constraint
Make a Gadget to ConvertAll Fixed-Card. Sols. to All Max.-Card. Sols.
cf. ∀Max. Sol. in L.M.P. ⊇ ∃!Max. S-paths• Change of Total Weight by Extraction

Add Dummy Elements of Weight 0 so that
They do NOT affect Original S-paths Problem→ Incentive to Use Dummy Elements in W.L.M.P.
29

Gadget to Convert Solutions• Violation of Cardinality Constraint
Make a Gadget to Convert
All Fixed-Card. Sols. to All Max.-Card. Sols.
𝑘=2cf. ∀Max. Sol. in L.M.P. ⊇ ∃!Max. S-paths30Gadget to Convert Solutions• Violation of Cardinality Constraint
Make a Gadget to Convert
All Fixed-Card. Sols. to All Max.-Card. Sols.
𝑘=2cf. ∀Max. Sol. in L.M.P. ⊇ ∃!Max. S-paths
𝐴 − 2𝑘Extra Terminals

31Gadget to Convert Solutions• Violation of Cardinality Constraint
Make a Gadget to Convert
All Fixed-Card. Sols. to All Max.-Card. Sols.
𝑘=2cf. ∀Max. Sol. in L.M.P. ⊇ ∃!Max. S-paths
𝐴 − 2𝑘Extra Terminals∀Max. S-paths cover
ALL Terminals
32

Ideas to Overcome Difficulties• Violation of Cardinality Constraint
Make a Gadget to Convert
All Fixed-Card. Sols. to All Max.-Card. Sols.
cf. ∀Max. Sol. in L.M.P. ⊇ ∃!Max. S-paths• Change of Total Weight by Extraction

Add Dummy Elements of Weight 0 so that
They do NOT affect Original S-paths Problem→ Incentive to Use Dummy Elements in W.L.M.P.
33

Add Dummy Elements of Weight 0

ForestIn each tree
at most one
𝑨-path,⟺which isS-pathFull Rank∃!Max. S-paths ⊆ ∀Max. Sol. in L.M.P.
BUT “Total Length < Total Weight” due to Dotted Edges

34

Add Dummy Elements of Weight 0Forest

In each tree
at most one
𝑨-path,⟺which isS-pathFull Rank∃!Max. S-paths ⊆ ∀Max. Sol. in L.M.P.
BUT “Total Length < Total Weight” due to Dotted Edges
𝑉∖𝐴

Extra S-pathto Rescue
Unused Non-terminals
35

Summary of Construction• 𝐴 − 2𝑘 Extra Terminals to Rescue Unused Terminals• An Extra S-path to Rescue Unused Non-terminals(ALL Extra Edges are of Length 0)

𝐴𝑉∖𝐴

36

Summary of Construction• 𝐴 − 2𝑘 Extra Terminals to Rescue Unused Terminals• An Extra S-path to Rescue Unused Non-terminals(ALL Extra Edges are of Length 0)

𝐴𝑉∖𝐴

37

Summary of Construction• 𝐴 − 2𝑘 Extra Terminals to Rescue Unused Terminals• An Extra S-path to Rescue Unused Non-terminals(ALL Extra Edges are of Length 0)

𝐴𝑉∖𝐴

38

Summary of Construction• 𝐴 − 2𝑘 Extra Terminals to Rescue Unused Terminals• An Extra S-path to Rescue Unused Non-terminals(ALL Extra Edges are of Length 0)

𝐴𝑉∖𝐴

⟸

Full Rank
Min. Weight39

Summary of Construction• 𝐴 − 2𝑘 Extra Terminals to Rescue Unused Terminals• An Extra S-path to Rescue Unused Non-terminals(ALL Extra Edges are of Length 0)
Extraction Preserves
𝐴
Total Weight
𝑉∖𝐴⟸

Full Rank
Min. Weight

Shortest!
40

Outline• Preliminaries– Disjoint S-paths– Linear Matroid Parity– Reduction in Cardinality Case

• Result– How to Extend to Weighted Case

• Conclusion
41

Conclusion

Cardinalityver.

Weightedver.

Disjoint S-paths

Linear Matroid Parity

Polytime

Polytime

Reduce[Lovász 1980][Schrijver 2003]

Polytime!

Reduce!

[This Talk]

e.g.,[Lovász 1981][Gabow–Stallmann 1986][Cheung–Lau–Leung 2016]

Polytime
Announced by[Iwata 2013][Pap 2013]42

Conclusion
Disjoint S-paths
Cardinalityver.

Weightedver.

O 𝑉 2.38time

𝑟 × 2𝑚Linear Matroid ParityReduce

O 𝑟𝑚1.38 time

[Lovász 1980][Schrijver 2003][Cheung–Lau–Leung 2016]

O 𝑉 5 time Reduce!

O 𝑟𝑚3 time

[This Talk]

Announced by[Iwata 2013]43

Conclusion• Shortest Disjoint S-paths Problem
is solved in O 𝑉 5 time via Weighted L.M.P.
• This result can be extended toPacking Non-zero 𝐴-paths in Group-Labeled Graphs
under some Group Representability Condition [Y. 2016]

Q. More Efficient or Direct Algorithms?
Q. “Non-zero & Weighted” is Generally in P?
44