How to Make a Bipartite Graph
DM-irreducible by Adding Edges
Satoru Iwata1, Jun Kato2, Yutaro Yamaguchi3
1. University of Tokyo, Japan.
2. TOYOTA Motor Corporation, Japan.
3. Osaka University, Japan.
JCCA2016 @Kyoto

May 24, 2016

Dulmage–Mendelsohn Decomposition[Dulmage–Mendelsohn 1958,59]

Given
𝑉0𝑉1
𝑉2

𝐺 = 𝑉 + , 𝑉 − ; 𝐸 : Bipartite Graph• 𝑉0+ < 𝑉0− or 𝑉0 = ∅• 𝑉𝑖+ = 𝑉𝑖−𝑖 ≠ 0, ∞• 𝑉∞+ > 𝑉∞− or 𝑉∞ = ∅𝑉∞Unique Partition of Vertex Set
reflecting Structure of Maximum Matchings2Dulmage–Mendelsohn Decomposition[Dulmage–Mendelsohn 1958,59]

Given
𝑉0𝑉1𝑉2𝑉∞

𝐺 = 𝑉 + , 𝑉 − ; 𝐸 : Bipartite Graph• 𝑉0+ < 𝑉0− or 𝑉0 = ∅• 𝑉𝑖+ = 𝑉𝑖−𝑖 ≠ 0, ∞• 𝑉∞+ > 𝑉∞− or 𝑉∞ = ∅• ∀Max. Matching in 𝐺 is a union of
Perfect Matchings in 𝐺 𝑉𝑖
Unique Partition of Vertex Set
reflecting Structure of Maximum Matchings3Dulmage–Mendelsohn Decomposition[Dulmage–Mendelsohn 1958,59]

Given
𝑉0𝑉1
𝑉2

𝐺 = 𝑉 + , 𝑉 − ; 𝐸 : Bipartite Graph• ∀Max. Matching in 𝐺 is a union of
Perfect Matchings in 𝐺 𝑉𝑖→ Edges between 𝑉𝑖 and 𝑉𝑗 𝑖 ≠ 𝑗canNOT be used.

𝑉∞
Unique Partition of Vertex Set
reflecting Structure of Maximum Matchings4Dulmage–Mendelsohn Decomposition[Dulmage–Mendelsohn 1958,59]

Given
𝑉0

𝐺 = 𝑉 + , 𝑉 − ; 𝐸 : Bipartite Graph

𝑉2• ∀Max. Matching in 𝐺 is a union of
Perfect Matchings in 𝐺 𝑉𝑖
→ Edges between 𝑉𝑖 and 𝑉𝑗 𝑖 ≠ 𝑗canNOT be used.

𝑉∞• ∀𝑒: Edge in 𝐺 𝑉𝑖 ,∃Perfect Matching in 𝐺 𝑉𝑖 using 𝑒

𝑉1

Unique Partition of Vertex Set
reflecting Structure of Maximum Matchings5DM-irreducibility
Def.

A bipartite graph is DM-irreducible

The DM-decomposition consists of a single component

𝑉∞
𝑉0Obs.

𝑉1A bipartite graph 𝐺 is DM-irreducible∀𝑒: Edge in 𝐺, ∃Perfect Matching in 𝐺 using 𝑒
6DM-irreducibility
Obs.

Complete bipartite graphs are DM-irreducible.
• Connected• Every Edge is in some Perfect Matching

𝑉∞
𝑉0𝑉1

7

DM-irreducibility
Obs.

Complete bipartite graphs are DM-irreducible.
• Connected• Every Edge is in some Perfect Matching

𝑉∞
𝑉0𝑉1⟹ DM-irreducible
Complete ⟸/How many additional edges are necessaryto make a bipartite graph DM-irreducible?

8Our Problem
Given
𝑉0𝑉1

𝐺 = 𝑉 + , 𝑉 − ; 𝐸 : Bipartite Graph

𝑉1𝑉2𝑉2
𝑉3𝑉∞

𝑉∞

Find

Minimum Number of Additional Edges
to Make 𝐺 DM-irreducible
9

Our Problem
Given

𝐺 = 𝑉 + , 𝑉 − ; 𝐸 : Bipartite Graph

𝑉1

𝑉∞
Find

Minimum Number of Additional Edges
to Make 𝐺 DM-irreducible
10

BackgroundCovering a Bisupermodular Function
by Directed Edges• Min-Max Duality• Polytime by Ellipsoid[Frank–Jordán 1995]• Pseudopolytime Algo.
[Végh–Benczúr 2008]

Our Problem

Making a Digraph
Strongly Connected• Min-Max Duality• Linear-time Algo.
[Eswaran–Tarjan 1976]11

Our Results
Covering a Bisupermodular Function
by Directed Edges• Min-Max Duality• Polytime by Ellipsoid[Frank–Jordán 1995]• Pseudopolytime Algo.
[Végh–Benczúr 2008]

Our Problem• Simple Polytime Algo.
• Constructive Proof for Min-Max[I.–K.–Y. 2016]

Making a Digraph
Strongly Connected• Min-Max Duality• Linear-time Algo.
[Eswaran–Tarjan 1976]

12

Outline• Preliminaries: How to Compute DM-decomposition– Find a Maximum Matching in a Bipartite Graph– Decompose a Digraph into Strongly Connected Components• Result: How to Make a Bipartite Graph DM-irreducible– Make a Digraph Strongly Connected [Eswaran–Tarjan 1976]– Find Edge-Disjoint 𝑠–𝑡 Paths in a Digraph• Conclusion

13

Outline• Preliminaries: How to Compute DM-decomposition– Find a Maximum Matching in a Bipartite Graph– Decompose a Digraph into Strongly Connected Components

14How to Compute DM-decomposition
Given

𝑉+

𝐺 = 𝑉 + , 𝑉 − ; 𝐸 : Bipartite Graph

𝑉−15

How to Compute DM-decomposition
Given

𝐺 = 𝑉 + , 𝑉 − ; 𝐸 : Bipartite Graph• Find a Maximum Matching 𝑀 in 𝐺𝑉+𝑉−
16

How to Compute DM-decomposition
Given

𝐺 = 𝑉 + , 𝑉 − ; 𝐸 : Bipartite Graph• Find a Maximum Matching 𝑀 in 𝐺
• Orient Edges so that𝑀 ⟹ Both Directions
𝐸 ∖ 𝑀 ⟹ Left to Right

𝑉+

↔
→

𝑉−17

How to Compute DM-decomposition
Given

𝐺 = 𝑉 + , 𝑉 − ; 𝐸 : Bipartite Graph• Find a Maximum Matching 𝑀 in 𝐺

𝑉0

• Orient Edges so that𝑀 ⟹ Both Directions
𝐸 ∖ 𝑀 ⟹ Left to Right↔
→• 𝑉0 : Reachable to 𝑉 − ∖ 𝜕 − 𝑀
𝑉∞• 𝑉∞ : Reachable from 𝑉 + ∖ 𝜕 + 𝑀
𝑉+𝑉−18

How to Compute DM-decomposition
Given

𝐺 = 𝑉 + , 𝑉 − ; 𝐸 : Bipartite Graph• Find a Maximum Matching 𝑀 in 𝐺

𝑉1𝑉2

• Orient Edges so that𝑀 ⟹ Both Directions
𝐸 ∖ 𝑀 ⟹ Left to Right↔
→• 𝑉0 : Reachable to 𝑉 − ∖ 𝜕 − 𝑀• 𝑉∞ : Reachable from 𝑉 + ∖ 𝜕 + 𝑀• 𝑉𝑖 : Strongly Connected Componentof 𝐺 − 𝑉0 − 𝑉∞19

Outline• Result: How to Make a Bipartite Graph DM-irreducible– Make a Digraph Strongly Connected [Eswaran–Tarjan 1976]– Find Edge-Disjoint 𝑠–𝑡 Paths in a Digraph

20

Our Problem (Reminder)
Given𝐺 = 𝑉 + , 𝑉 − ; 𝐸 : Bipartite Graph

𝑉0𝑉1𝑉2𝑉1→𝑉∞Find

Minimum Number of Additional Edges
to Make 𝐺 DM-irreducible21Unbalanced Case → Balanced Case
𝑉+ ≠ 𝑉−𝑉+ = 𝑉−→

𝐺𝐺′

Fact 𝐺 is DM-irreducible ⟺ 𝐺 ′ is DM-irreducible
22Unbalanced Case → Balanced Case
𝑉+ ≠ 𝑉−𝑉+ = 𝑉−

𝑉0
𝑉1→

𝐺𝐺′

Fact 𝐺 is DM-irreducible ⟺ 𝐺 ′ is DM-irreducible
23

Case Analysis
Assumption

𝐺 = 𝑉 + , 𝑉 − ; 𝐸 is Balanced

Case 1. When 𝐺 has a perfect matching.

𝑉0Case 2. When 𝐺 has NO perfect matching.
𝑉∞
24

Case Analysis
Assumption

𝐺 = 𝑉 + , 𝑉 − ; 𝐸 is Balanced

Case 1. When 𝐺 has a perfect matching.

𝑉0Case 2. When 𝐺 has NO perfect matching.
𝑉∞
25

Case 1. Perfectly Matchable
𝑉1

𝑉1

𝑉2

𝑉2

𝑉3

𝑉3

𝑉4

𝑉4

DM-decomposition = Strg. Conn. Comps.

26

Case 1. Perfectly Matchable
𝑉1

𝑉1

𝑉2

𝑉2

𝑉3

𝑉3

𝑉4

𝑉4

𝑉1

DM-decomposition = Strg. Conn. Comps. →Make it Strg. Conn.
by Adding Edges

Obs.
DM-irreducibility is Equivalent toStrong Connectivity of the Oriented Graph
27

How to Make a Digraph Strongly Connected
Given

𝐺 = 𝑉, 𝐸 : Directed Graph

Find

Minimum Number of Additional Edges
to Make 𝐺 Strongly Connected: Strg. Conn. Comp.

28

How to Make a Digraph Strongly Connected
Given

𝐺 = 𝑉, 𝐸 : Directed Graph: Strg. Conn. Comp.

Each Source needs an Entering Edge

Find

Minimum Number of Additional Edges
to Make 𝐺 Strongly Connected29How to Make a Digraph Strongly Connected
Given

𝐺 = 𝑉, 𝐸 : Directed Graph: Strg. Conn. Comp.

Each Source needs an Entering Edge

Each Sink needs a Leaving Edge

Find

Minimum Number of Additional Edges
to Make 𝐺 Strongly Connected30How to Make a Digraph Strongly Connected
Given

𝐺 = 𝑉, 𝐸 : Directed Graph NOT Strg. Conn.

Find

Minimum Number of Additional Edges
to Make 𝐺 Strongly Connected

Obs. max # of Sources, # of Sinks edges are Necessary.

31How to Make a Digraph Strongly Connected
Given

𝐺 = 𝑉, 𝐸 : Directed Graph NOT Strg. Conn.

Find

Minimum Number of Additional Edges
to Make 𝐺 Strongly Connected

Obs. max # of Sources, # of Sinks edges are Necessary.

Thm. max # of Sources, # of Sinks edges are Sufficient.
One can find such Additional Edges in Linear Time.
[Eswaran–Tarjan 1976]→ Case 1 is Solved in Linear Time.
32

Case Analysis
Assumption

𝐺 = 𝑉 + , 𝑉 − ; 𝐸 is Balanced

Case 1. When 𝐺 has a perfect matching.

𝑉0Case 2. When 𝐺 has NO perfect matching.
𝑉∞
33

Case 2. NO Perfect Matching
𝑉0Maximum Matching

𝑉1
𝑉2
𝑉∞
DM-decomposition34

Case 2. NO Perfect Matching
𝑉0

Maximum Matching

𝑉1𝑉2+Perfect Matching𝑉∞
DM-decomposition

Idea
Connect Exposed Vertices to Reduce to Case 135

Case 2. NO Perfect Matching
Maximum Matching

𝑉1
𝑉2

DM-decomposition+Perfect Matching
Each 𝑉𝑖 𝑖 ≠ 0, ∞remains as it wasIdea
Connect Exposed Vertices to Reduce to Case 136

From the Viewpoint of Oriented Graphs
Idea
Connect Exposed Vertices to Reduce to Case 1𝑉0𝑉𝑖→
𝑉∞

37

From the Viewpoint of Oriented Graphs
Idea
Connect Exposed Vertices to Reduce to Case 1
𝑉0
𝑉𝑖→
𝑉∞

𝑉+ − 𝑀max # of Sources, # of Sinks# of Additional Edges
38

From the Viewpoint of Oriented Graphs
Idea
Connect Exposed Vertices to Reduce to Case 1𝑉0𝑉𝑖→
𝑉∞

𝑉+ − 𝑀max # of Sources, # of Sinks
Const. # of Additional Edges
Depending on 𝑀
39

Sources and Sinks in Resulting Digraph
𝑉0

𝑉∞
Choice of 𝑀
𝑉0𝑉∞
40

Sources and Sinks in Resulting Digraph
𝑉1
𝑉4→ 𝑉
3

𝑉0

𝑉∞

𝑉2
𝑉3

𝑉4

𝑉2
Choice of 𝑀

Orientation

𝑉0
𝑉∞

𝑉1

→

𝑉1
𝑉4
𝑉2
𝑉3

Simplified
𝑉1
𝑉2
𝑉3

𝑉4
41

Sources and Sinks in Resulting Digraph
𝑉0

𝑉0

𝑉∞

𝑉∞
Choice of 𝑀
𝑉0
𝑉∞

𝑉1
𝑉3

Strg. Conn. Comps.

𝑉4

Simplified
𝑉1

𝑉0

→
𝑉∞

𝑉2

→𝑉2
𝑉3

𝑉4
42

Sources and Sinks in Resulting Digraph
𝑉0

𝑉∞

𝑉0
𝑉∞

Want to Minimize
𝑉1𝑉2→𝑉3

𝑉4

Want to Minimize

Obs.
# of Resulting Sources = # of Sources in 𝑉0 + const.
# of Resulting Sinks = # of Sinks in 𝑉∞ + const.
43

Sources and Sinks in Resulting Digraph
𝑉0𝑉0

Want to Minimize
𝑉1

→𝑉∞

𝑉2
𝑉3

𝑉∞

𝑉4

Want to Minimize

Obs.
# of Sources in 𝑉0 and # of Sinks in 𝑉∞ vary Indep.
by choices of Perfect Matchings in 𝐺 𝑉0 and 𝐺 𝑉∞ .
44

How to Minimize # of Sinks in 𝑉∞
Lem.

# of Sinks in 𝑉∞ is NOT Minimized∃Edge-disjoint Paths from ∃: Exposed: Sink: S.C.C.

to ∃ 𝑎1 ,𝑎2[I.–K.–Y. 2016]

Flipping𝑉∞

45

Summary of Case 2
Case 2. 𝐺 has NO Perfect Matching• Connect Exposed Vertices to Make Perfect Matching→ Reduce to Case 1
OPT = max # of Sources, # of Sinks
𝑉0
𝑉∞

𝑉1
𝑉4→ 𝑉3

𝑉1
𝑉2
𝑉3

𝑉4

𝑉246

Summary of Case 2
Case 2. 𝐺 has NO Perfect Matching• Connect Exposed Vertices to Make Perfect Matching→ Reduce to Case 1
OPT = max # of Sources, # of Sinks• Minimize # of Sources in 𝑉0 and # of Sinks in 𝑉∞ ,in Advance, by finding Edge-disjoint Paths repeatedly.

47

Summary of Case 2
Case 2. 𝐺 has NO Perfect Matching• Connect Exposed Vertices to Make Perfect Matching→ Reduce to Case 1
OPT = max # of Sources, # of Sinks• Minimize # of Sources in 𝑉0 and # of Sinks in 𝑉∞ ,in Advance, by finding Edge-disjoint Paths repeatedly.
Thm. One can find an optimal solution by this strategy.
→ Constructive Proof for Min-Max Duality[I.–K.–Y. 2016]48

Outline• Conclusion

49

Conclusion• We propose a simple Polytime Algorithm
for finding a minimum number of Additional Edges
to make a Bipartite Graph DM-irreducible• Our Algorithm is based on two elementary techniques:– Find Edge-disjoint 𝑠–𝑡 Paths in a Directed Graph– Make a Digraph Strongly Connected by Adding Edges• The Halting Condition of Our Algorithm
implies Min-Max Duality extending [Eswaran–Tarjan 1976]
50