On Applicationsof Weighted Linear Matroid Parity
Yusuke Kobayashi1, Yutaro Yamaguchi2
1. University of Tsukuba, Japan
2. Osaka University, JapanJH 2017 @BudapestMay 22, 2017

Applications of Linear Matroid Parity• Maximum Forests in 3-Uniform Hypergraphs• Maximum Disjoint 𝒮-paths[Lovász 1980][Lovász 1980][Schrijver 2003]• Minimum Pinning-Down Points
to Make Planar Structures Rigid[Lovász 1980]• Minimum Feedback Vertex Sets in (Sub)Cubic Graphs[Ueno–Kajitani–Gotoh 1988]• Maximum-Genus Embedding of Graphs[Furst–Gross–McGeoch 1988]

etc.

Analogy in Weighted Situations?
Some Problem

Linear Matroid Parity

Unweighted(Cardinality)ver.

Polytime

Polytime

Weightedver.

Polytime??

viaReduction???

[Lovász 1978]

Polytime[Iwata–Kobayashi 2017](Also Announced by [Pap 2013])

Outline• Preliminaries• Disjoint 𝒮-paths– Background– Extension Trick• Feedback Vertex Sets in (Sub)Cubic Graphs– Background– Extension Trick• Conclusion

Outline• Preliminaries (What is Difficult?)• Disjoint 𝒮-paths– Background– Extension Trick• Feedback Vertex Sets in (Sub)Cubic Graphs– Background– Extension Trick• ConclusionLinear Matroid Parity Problem
Given 𝑍 ∈ 𝐅 𝑟×2𝑚 : Matrix with Lines (Pairing of Columns)
Find Maximum Number of Linearly Independent Lines
10000000100000001000000010000000100000001000000010000211Column
Full Rank

10000000100000001000000010000000100000001000000010000210

Weighted Linear Matroid Parity Problem
Given 𝑍 ∈ 𝐅 𝑟×2𝑚 : Matrix with Lines (Pairing of Columns)
𝑤: 𝑚 → 𝐑 Weight on Lines
Find Parity Base of Minimum WeightLine Subset consistng of a Basis
010000

𝟐00
1000000
100

𝟑0000
1000000
1

100000100002
1−𝟏

⟺1
00000

Nonsingular4<61000000
10000𝟐00
1000000
100

𝟑000010000001𝟏000001000021−1

Reduction Sketch (Unweighted Case)
Some Problem
Original
Instance

ReduceLinear Matroid Parity

Construct
Solve

Solve

Solution

Reconstruct

ColumnFull Rank

Reduction Sketch (Unweighted Case)
Some Problem
Original
Instance

WhatWeNeed

OptimalSolution

ReduceLinear Matroid Parity

Construct⟸Max. Cardinality

Reconstruct

ColumnFull Rank

General Difficulty• Solution Correspondence may NOT be One-to-One• Weights of Solutions may NOT be Preserved

Original
ProblemOpt.

L.M.P.
Max.
Card.

General Difficulty• Solution Correspondence may NOT be One-to-One• Weights of Solutions may NOT be PreservedOpt.
WeightOriginal
Problem

L.M.P.
Opt.
Weight𝑤Org ≠ 𝑤LMP

Outline• Preliminaries• Disjoint 𝒮-paths– Background– Extension Trick• Feedback Vertex Sets in (Sub)Cubic Graphs– Background– Extension Trick• Conclusion

Overview on Cardinality Maximization
P
Disjoint 𝒮-paths

Solved via L.M.P.
[Lovász 1978, 1980][Schrijver 2003]

𝑠𝑡

Disjoint
𝑠–𝑡 Paths

Non-bipartite
Matching

Bipartite MatchingOverview on Cost Minimization
Disjoint 𝒮-paths

Open for a long timeP𝑠𝑡

Disjoint
𝑠–𝑡 Paths

Non-bipartite
Matching

Min-Cost Flow(Integral)Assignment Problem Bipartite Matching

Weighted MatchingOverview on Cost Minimization
PDisjoint 𝒮-paths𝑠𝑡

Disjoint
𝑠–𝑡 Paths

Solved via
Weighted L.M.P.

Non-bipartiteMatching

Min-Cost Flow(Integral)

Assignment Problem Bipartite Matching

Weighted Matching𝐴-paths and 𝒮-paths
𝐺 = 𝑉, 𝐸 : Undirected Graph𝐴 ⊆ 𝑉: Terminal Set

𝐴-paths∈𝐴∉𝐴

NOT 𝐴-paths

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

𝐴2𝐴1NOT 𝒮-path

𝐴2𝐴1𝐴3𝐴3

Disjoint 𝒮-paths Problem
Given

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

FindMaximum Number of Vertex-Disjoint 𝒮-paths
including Terminals

Shortest Disjoint 𝒮-paths Problem
Given

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

Find

Totally Shortest 𝑘 Vertex-Disjoint 𝒮-paths
Ex. ℓ ≡ 𝟏
𝑘=2

2+2=4<5=2+3

Disjoint 𝒮-paths → Linear Matroid Parity[Lovász 1980][Schrijver 2003]

Disjoint 𝒮-paths

ReduceLinear Matroid ParityConstruct
Solve

Solve

Reconstruct

ColumnFull Rank

Disjoint 𝒮-paths → Linear Matroid Parity[Lovász 1980][Schrijver 2003]

Thm. ∀ 𝐺 = 𝑉, 𝐸 , 𝐴, 𝒮 , ∃ L.M.P. Instance s.t.
• The Line set is the Edge set 𝐸• 𝐹 ⊆ 𝐸 is Feasible if and only if– the Subgraph 𝐺 𝐹 is a Forest, and– each tree has at most one 𝐴-path, which is an 𝒮-path⟺

ColumnFull Rank

Disjoint 𝒮-paths → Linear Matroid Parity[Lovász 1980][Schrijver 2003]

Thm. ∀ 𝐺 = 𝑉, 𝐸 , 𝐴, 𝒮 , ∃ L.M.P. Instance s.t.
• The Line set is the Edge set 𝐸• 𝐹 ⊆ 𝐸 is Feasible if and only if– the Subgraph 𝐺 𝐹 is a Forest, and– each tree has at most one 𝐴-path, which is an 𝒮-path
Max. #(This Type)⟸Max. Card.

⟺

ColumnFull Rank

Disjoint 𝒮-paths → Linear Matroid Parity[Lovász 1980][Schrijver 2003]

Thm. ∀ 𝐺 = 𝑉, 𝐸 , 𝐴, 𝒮 , ∃ L.M.P. Instance s.t.
• The Line set is the Edge set 𝐸• 𝐹 ⊆ 𝐸 is Feasible if and only if– the Subgraph 𝐺 𝐹 is a Forest, and– each tree has at most one 𝐴-path, which is an 𝒮-pathTotal Length of 𝒮-paths & Dotted Edges = Weight⟺

ColumnFull Rank

Outline• Preliminaries• Disjoint 𝒮-paths– Background– Extension Trick (Constructing Auxiliary Instance)• Feedback Vertex Sets in (Sub)Cubic Graphs– Background– Extension Trick• Conclusion

Construction of Auxiliary Graph• 𝐴 − 2𝑘 Extra Terminals to Rescue Unused Terminals(Because we want to Find 𝑘 Vertex-Disjoint 𝒮-paths)• An Extra 𝒮-path to Rescue Unused Non-terminals(ALL Extra Edges are of Length 0)𝐴𝑉∖𝐴Construction of Auxiliary Graph• 𝐴 − 2𝑘 Extra Terminals to Rescue Unused Terminals(Because we want to Find 𝑘 Vertex-Disjoint 𝒮-paths)• An Extra 𝒮-path to Rescue Unused Non-terminals(ALL Extra Edges are of Length 0)𝐴𝑉∖𝐴Construction of Auxiliary Graph• 𝐴 − 2𝑘 Extra Terminals to Rescue Unused Terminals(Because we want to Find 𝑘 Vertex-Disjoint 𝒮-paths)• An Extra 𝒮-path to Rescue Unused Non-terminals(ALL Extra Edges are of Length 0)𝐴𝑉∖𝐴Construction of Auxiliary Graph• 𝐴 − 2𝑘 Extra Terminals to Rescue Unused Terminals(Because we want to Find 𝑘 Vertex-Disjoint 𝒮-paths)• An Extra 𝒮-path to Rescue Unused Non-terminals(ALL Extra Edges are of Length 0)𝐴𝑉∖𝐴⟸

NonsingularMin. WeightConstruction of Auxiliary Graph• 𝐴 − 2𝑘 Extra Terminals to Rescue Unused Terminals(Because we want to Find 𝑘 Vertex-Disjoint 𝒮-paths)• An Extra 𝒮-path to Rescue Unused Non-terminals(ALL Extra Edges are of Length 0)
𝐴𝑉∖𝐴

Min. Total Lengthof 𝒮-paths⟸Nonsingular=Min. WeightSummary on Disjoint 𝒮-paths
Constructing Auxiliary Instance(by Adding Weight-0 Elements)• Shortest Disjoint 𝒮-paths Problem
is solved in Polytime 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]

Outline• Preliminaries• Disjoint 𝒮-paths– Background– Extension Trick• Feedback Vertex Sets in (Sub)Cubic Graphs– Background– Extension Trick• Conclusion

Feedback Vertex Set Problem
Given

𝐺 = 𝑉, 𝐸 : Undirected GraphFindFeedback Vertex Set of Minimum Cardinality𝑋 ⊆ 𝑉 s.t. 𝐺 − 𝑋 is a ForestMinimum-Weight F.V.S. Problem
Given

𝐺 = 𝑉, 𝐸 : Undirected Graph
𝑤: 𝑉 → 𝐑 ≥0 Weight on Vertices

FindFeedback Vertex Set of Minimum Weight

Ex. 𝑤 ≡ 𝑑𝐺 (Degree of Vertices)

3 + 3 + 4 = 10 < 11 = 7 + 4

Minimum-Weight F.V.S. Problem
Given

𝐺 = 𝑉, 𝐸 : Undirected Graph, 𝑤: 𝑉 → 𝐑 ≥0FindFeedback Vertex Set of Minimum Weight• NP-Hard even when
‒ 𝑤 ≡ 𝟏 (Unweighted), and‒ 𝐺 is Planar with 𝑑𝐺 ≤ 𝟒[Garey–Johnson 1977]• Polytime via L.M.P. when 𝑤 ≡ 𝟏 and 𝑑𝐺 ≤ 𝟑 (Subcubic)[Ueno–Kajitani–Gotoh 1988]• Polytime 2-Approximation in General[Bafna‒Berman‒Fujito 1999]

F.V.S. in (Sub)Cubic Graphs → L.M.P.
𝑑𝐺 ≡ 𝟑
F.V.S. in Cubic Graphs[Ueno–Kajitani–Gotoh 1988]

ReduceLinear Matroid Parity

Construct
Solve

Solve

Reconstruct

ColumnFull Rank

F.V.S. in (Sub)Cubic Graphs → L.M.P.
[Ueno–Kajitani–Gotoh 1988]

Thm. ∀𝐺 = 𝑉, 𝐸 : Cubic, ∃ L.M.P. Instance s.t.
• The Line set is the Vertex set 𝑉• If 𝑌 ⊆ 𝑉 is Optimal, then– each 2-(edge)-conn. comp. of 𝐺 − 𝑌 is a Cycle,– min 𝑋 ∣ 𝑋: F.V.S. in 𝐺 = 𝑌 + # Cycles in 𝐺 − 𝑌Max. Card.

⟸Column
Full Rank

F.V.S. in (Sub)Cubic Graphs → L.M.P.
[Ueno–Kajitani–Gotoh 1988]

Thm. ∀𝐺 = 𝑉, 𝐸 : Cubic, ∃ L.M.P. Instance s.t.
• The Line set is the Vertex set 𝑉• If 𝑌 ⊆ 𝑉 is Optimal, then– each 2-(edge)-conn. comp. of 𝐺 − 𝑌 is a Cycle,– min 𝑋 ∣ 𝑋: F.V.S. in 𝐺 = 𝑌 + # Cycles in 𝐺 − 𝑌
Min.-Card. F.V.S.

Max. Card.
Reconstruct⟸Column
Full Rank

Outline• Preliminaries• Disjoint 𝒮-paths– Background– Extension Trick• Feedback Vertex Sets in (Sub)Cubic Graphs– Background– Extension Trick (Using Alternative Formulations)• Conclusion

Alternative Characterization[Ueno–Kajitani–Gotoh 1988]

Thm. ∀𝐺 = 𝑉, 𝐸 : Cubic, ∃ L.M.P. Instance s.t.
• The Line set is the Vertex set 𝑉• If 𝑌 ⊆ 𝑉 is Optimal, then– each 2-(edge)-conn. comp. of 𝐺 − 𝑌 is a Cycle,– min 𝑋 ∣ 𝑋: F.V.S. in 𝐺 = 𝑌 + # Cycles in 𝐺 − 𝑌Max. Card.

⟸ColumnFull Rank

Alternative Characterization[Ueno–Kajitani–Gotoh 1988]

Obs. ∀𝐺 = 𝑉, 𝐸 : Cubic, ∃ L.M.P. Instance s.t.
• The Line set is the Vertex set 𝑉• 𝑋 ⊆ 𝑉 is a F.V.S. in 𝐺 ⟺ 𝑋 is a Spanning Line Subset
Contains a Base (NOT necessarily Parity Base)⟺Row
Full Rank

Alternative Characterization[Ueno–Kajitani–Gotoh 1988]

Obs. ∀𝐺 = 𝑉, 𝐸 : Cubic, ∃ L.M.P. Instance s.t.
• The Line set is the Vertex set 𝑉• 𝑋 ⊆ 𝑉 is a F.V.S. in 𝐺 ⟺ 𝑋 is a Spanning Line Subset
Contains a Base (NOT necessarily Parity Base)⟺ 𝑉 − 𝑋 is Independent in the Dual Matroid⟺

Row
Full Rank

Alternative CharacterizationObs. ∀𝐺 = 𝑉, 𝐸 : Cubic, ∃ L.M.P. Instance s.t.
• The Line set is the Vertex set 𝑉• 𝑋 ⊆ 𝑉 is a F.V.S. in 𝐺 ⟺ 𝑉 − 𝑋 is Feasible
Fact. Dual of 𝐅-representable Matroid is 𝐅-representable
Min.-Weight. F.V.S.

⟸

Max. Weight⟺

ColumnFull Rank

Equivalent Formulations of Weighted L.M.P.
Given 𝑍 ∈ 𝐅 𝑟×2𝑚 : Matrix with Lines (Pairing of Columns)
𝑤: 𝑚 → 𝐑 Weight on Lines

Negating&Duplicating
Max.-Weight
Indep. Lines

Min.-Weight
Parity BaseDual Matroids

Lifting up
by Suff. Large Const.
Min.-Weight
Spanning Lines

Equivalent Formulations of Weighted L.M.P.
Given 𝑍 ∈ 𝐅 𝑟×2𝑚 : Matrix with Lines (Pairing of Columns)
𝑤: 𝑚 → 𝐑 Weight on Lines

Negating&Lifting up
Max.-Weight
Indep. Lines

Min.-Weight
Parity Base

Duplicating
Dual Matroids

Min.-Weight
Spanning Lines

Summary on F.V.S. in (Sub)Cubic Graphs
Using Alternative Formulationsof Weighted Linear Matroid Parity• Minimum-Weight F.V.S. Problem in Subcubic Graphs
is solved in Polytime via Weighted L.M.P.
• In fact, our reduction can be regarded asFinding Maximum Forests in 3-Uniform Hypergraphs,
which reduces to L.M.P. in Unweighted case [Lovász 1980]

Outline• Preliminaries• Disjoint 𝒮-paths– Background– Extension Trick• Feedback Vertex Sets in (Sub)Cubic Graphs– Background– Extension Trick• Conclusion

Conclusion• Weighted L.M.P. is Very Powerful to show Tractability• Two General Strategies
to Extend Applications of L.M.P. to Weighted Situations– Construct Auxiliary Instance (with Weight-0 Elements)– Use Alternative Formulations of Weighted L.M.P.
• Some Tricky or Other-type Applications??
– Like, e.g., Shortest Path & 𝑇-join → Weighted Matching?
– Derive Min-Max Duality or Polyhedral Property?

Appendix

Duplicating of L.M.P. Instance𝑧1 𝑧2𝟎 𝟎𝑧1 𝟎𝑧2 𝟎𝟎 𝟎𝑧1 𝑧2𝟎 𝑧1𝟎 𝑧2𝑧1 𝑧2𝑤

𝑤

Original

Feasible × 2⟸Spanning × 2⟸0 or 2𝑤

Duplicated InstanceRestriction ofParity BaseParity Base