Finding a Path in Group-Labeled Graphswith Two Labels Forbidden
Yasushi Kawase1, Yusuke Kobayashi2
Yutaro Yamaguchi3
1. Tokyo Institute of Technology, Japan.
2. University of Tsukuba, Japan.
3. University of Tokyo, Japan.
ICALP 2015 @Kyoto

July 9, 2015
1

Parity of Length𝑠𝑡• Odd → ???
• Even → ???

2

Parity of Length𝑠𝑡• Odd → YES• Even → ???

3

Parity of Length𝑠𝑡Bipartite• Odd → YES• Even → NO4

Parity of Length𝑠𝑡
Bipartite• Odd → YES• Even → NO

Easy to test!

Parity of 𝑠–𝑡 paths = Odd5

Possible Labels
0𝑠

1−100

mod 320
1−2−10𝑡

1−10• 0 → ???
• 1 → ???
• 2 → ???
6

Possible Labels
𝟎𝑠

𝟏−100

mod 3
𝟐0
1−2−100• 0 → YES
• 1 → ???
• 2 → ???

𝑡1−11+0+2=3≡07

Possible Labels
0𝑠

1−1𝟎0

mod 3
20
1−2−1𝟎0• 0 → YES
• 1 → YES
• 2 → ???

𝑡𝟏−10+0+1=1

8

Possible Labels
0𝑠

1−100

mod 3
20
1−2−10𝑡

1−10• 0 → YES• 1 → YES• 2 → NOLabels of 𝑠–𝑡 paths = 0, 19

Our Problem
Group-Labeled
Graph

Given𝑠Γ∋𝛾𝛾 −1𝑡
Γ: GroupFind

Possible Labels of 𝑠–𝑡 paths

10Our Problem
Group-Labeled
Graph

Given𝑠Γ∋𝛾𝑡
Γ: Group

Find

Possible Labels of 𝑠–𝑡 paths

11Our Problem
Group-Labeled
Graph

Given𝑠Γ∋𝛾𝑡
Γ: Group

Find

Possible Labels of 𝑠–𝑡 paths → Difficult• 𝑙 = 𝛼 : Polytime• 𝑙 ⊇ 𝛼 : NP-hard (Hamiltonian Path)• 𝑙 = 𝛼, 𝛽 : ???

12

Our Problem
Group-Labeled
Graph

Given𝑠Γ∋𝛾𝑡
Γ: GroupFindPossible Labels of 𝑠–𝑡 paths → Difficult• 𝑙 = 𝛼 : Polytime• 𝑙 ⊇ 𝛼 : NP-hard (Hamiltonian Path)• 𝑙 = 𝛼, 𝛽 : Polytime!!

13

Example 1𝐙-Labeled Graph
𝐙 = 0, ±1, ±2, …

𝟏0

𝑠𝑡𝟎

𝑙 = 0, 1
14

Example 1
𝐙-Labeled Graph
𝐙 = 0, ±1, ±2, …

𝟏0

𝑠𝑡𝟎

𝑙 = 0, 1
15

Example 2
𝐙-Labeled Graph
𝐙 = 0, ±1, ±2, …

𝟏0𝟎0

𝑠000𝟏

𝑡0𝟎
𝑙 = 0, 1
16

Example 2
𝐙-Labeled Graph
𝐙 = 0, ±1, ±2, …

𝟏0𝟎0𝑠000𝟏𝑡0𝟎𝑙 = 0, 1
17

Example 3
𝟏𝐙-Labeled Graph
𝐙 = 0, ±1, ±2, …

𝑡𝑠0
Embedded𝑙 = 0, 118

Example 3
𝟏𝐙-Labeled Graph
𝐙 = 0, ±1, ±2, …

𝑡𝑠0
Embedded𝑙 = 0, 1
19

Example 3
𝟏−1𝑠

𝐙-Labeled Graph
𝐙 = 0, ±1, ±2, …

𝑡−1 + 1 = 0

0
Embedded𝑙 = 0, 120

Example 3
𝟏−1𝑠

𝐙-Labeled Graph
𝐙 = 0, ±1, ±2, …

𝑡−1 + 1 = 00
Embedded𝑙 = 0, 121

Our Result (Characterization)Thm.

𝑙 = 𝛼, 𝛽Reducible to one of them
[K.–K.–Y. 2015]

Essential

22

Our Result (Characterization)Thm.

𝑙 = 𝛼, 𝛽Reducible to one of them
[K.–K.–Y. 2015]

Polytime Testable• NOT Depends on Group• Assume Constant-time Group Operations(e.g. Addition, Comparison, …)
23

Overview
Finding an 𝑠–𝑡 pathwith 2 Labels Forbidden𝑠

Polytime[K.–K.–Y. 2015]

Characterizationfor
2 Possible Labels𝑙 = 𝛼, 𝛽∉ 𝛼, 𝛽𝑡

Polytime Testable• NOT Depends on Group• Assume Constant-time Group Operations(e.g. Addition, Comparison, …)
24

Overview
Characterizationfor
2 Possible Labels

Finding an 𝑠–𝑡 pathwith 2 Labels Forbidden𝑠Polytime[K.–K.–Y. 2015]∉ 𝛼, 𝛽𝑡𝑠1

Generalized𝑠2

Generalized

𝑡1

𝑡22-disjoint Paths Problem
Polytime𝑙 = 𝛼, 𝛽[Seymour 1980,
Shiloach 1980,
Thomassen 1980]

Characterization
for2-disjoint Paths
25

Generalizing 2-disjoint Paths
Undirected Graph

𝑠1𝑡2

𝑡1

𝑠2

26

Generalizing 2-disjoint Paths
Undirected Graph

𝑠1

𝑡1

𝑡2

𝑠22-disjoint paths
27Generalizing 2-disjoint Paths
𝐙3 -Labeled Graph
𝐙3 = −1, 0, 1

Undirected Graph𝑠1𝑡1𝑠 = 𝑠1 0000𝑡10𝑠20𝑡2𝑠2𝑡 = 𝑡2028Generalizing 2-disjoint Paths
𝐙3 -Labeled Graph
𝐙3 = −1, 0, 1

Undirected Graph𝑠1𝑡1𝑠 = 𝑠1 0000𝑡2𝑠2

𝑡 = 𝑡200𝑡1

1−10𝑠229

Generalizing 2-disjoint Paths
𝐙3 -Labeled Graph
𝐙3 = −1, 0, 1

Undirected Graph𝑠1𝑠 = 𝑠1 0𝑡10000𝑡2𝑠22-disjoint paths𝑡 = 𝑡2⟺0𝑡1−10𝑠2

Label −130

Generalizing 2-disjoint Paths
𝐙3 -Labeled Graph
𝐙3 = −1, 0, 1

Undirected Graph𝑠1𝑠 = 𝑠1 0𝑡10000𝑡2

𝑠22-disjoint paths𝑡 = 𝑡2⟺⟺0𝑡1−10Label −1
Neither 0 nor 1𝑠231

Overview
Finding an 𝑠–𝑡 pathwith 2 Labels Forbidden𝑠∉ 𝛼, 𝛽𝑡𝑠1

Generalized𝑠2𝑡1𝑡22-disjoint Paths Problem32

Overview
Characterization
for2 Possible Labels𝑙 = 𝛼, 𝛽Generalized
Characterizationfor
2-disjoint Paths
33

Our Result (Characterization)Thm.

𝑙 = 𝛼, 𝛽Reducible to one of them
[K.–K.–Y. 2015]

Essential34

Characterization for 2-disjoint Paths
Thm. NO disjoint 𝑠1 –𝑡1 , 𝑠2 –𝑡2 paths
Reducible so that Planar Embeddable[Seymour 1980]

𝑠2𝑡1Essential

𝑠1𝑡235

Characterization for 2-disjoint Paths
Thm. NO disjoint 𝑠1 –𝑡1 , 𝑠2 –𝑡2 paths
Reducible so that Planar Embeddable[Seymour 1980]

𝑠2𝑡1
Essential

𝑠1𝑡236

Characterization for 2-disjoint Paths
Thm. NO disjoint 𝑠1 –𝑡1 , 𝑠2 –𝑡2 paths
Reducible so that Planar Embeddable
1𝑠2[Seymour 1980]

𝑡10
𝑠1

𝑡2

𝑙 = 0, 137

Characterization for 2-disjoint Paths
Thm. NO disjoint 𝑠1 –𝑡1 , 𝑠2 –𝑡2 paths
Reducible so that Planar Embeddable[Seymour 1980]

Contraction of 2-cut𝑥NOterminal𝑦→𝑦𝑥
38Characterization for 2-disjoint Paths
Thm. NO disjoint 𝑠1 –𝑡1 , 𝑠2 –𝑡2 paths
Reducible so that Planar Embeddable[Seymour 1980]

Contraction of 3-cut𝑥NOterminal𝑧𝑦→𝑦𝑥𝑧

39

Contrast between Two Characterizations
NO 2-disjoint Paths

Exactly 2 Possible Labels[Seymour 1980][K.–K.–Y. 2015]

Contraction of 2-cut

ReducingOperations→Contraction of 3-cut→

Planar Embeddable

EssentialCases
40

Contrast between Two Characterizations
NO 2-disjoint Paths

Exactly 2 Possible Labels[Seymour 1980][K.–K.–Y. 2015]

Contraction of 2-cut

ReducingOperations→

Contraction of 3-cut→

Planar Embeddable

Essential
Cases
41

Contrast between Two Characterizations

ReducingOperations

NO 2-disjoint Paths

Exactly 2 Possible Labels[Seymour 1980][K.–K.–Y. 2015]

Contraction of 2-cut

2-contraction→

Contraction of 3-cut
→

𝛼→

𝛼

3-contraction𝛼→𝛼Planar Embeddable

Essential
Cases
42

Our Result (Algorithm)
Finding an 𝑠–𝑡 pathwith 2 Labels Forbidden𝑠∉ 𝛼, 𝛽𝑡

Polytime [K.–K.–Y. 2015]

Characterization
for2 Possible Labels𝑙 = 𝛼, 𝛽43Our Result (Algorithm)
Finding an 𝑠–𝑡 pathwith 2 Labels Forbidden𝑠∉ 𝛼, 𝛽𝑡

Polytime [K.–K.–Y. 2015]

Characterizationfor
2 Possible Labels𝑙 = 𝛼, 𝛽• Test "𝑙 ⊆ 𝛼, 𝛽 or NOT" (Based on Our Char.)cf. 𝑙 = 𝛼 is Easy

44

Our Result (Algorithm)
Finding an 𝑠–𝑡 pathwith 2 Labels Forbidden𝑠∉ 𝛼, 𝛽𝑡Characterizationfor
2 Possible Labels

Polytime [K.–K.–Y. 2015]

𝑙 = 𝛼, 𝛽• Test "𝑙 ⊆ 𝛼, 𝛽 or NOT" (Based on Our Char.)• 𝑙 ⊆ 𝛼, 𝛽 → Certification for “NO”

45

Our Result (Algorithm)
Finding an 𝑠–𝑡 pathwith 2 Labels Forbidden𝑠∉ 𝛼, 𝛽𝑡Characterizationfor
2 Possible Labels

Polytime [K.–K.–Y. 2015]

𝑙 = 𝛼, 𝛽• Test "𝑙 ⊆ 𝛼, 𝛽 or NOT" (Based on Our Char.)• 𝑙 ⊆ 𝛼, 𝛽 → Certification for “NO”
• 𝑙 ⊈ 𝛼, 𝛽 → ∃𝛾 ∈ 𝑙 ∖ 𝛼, 𝛽46

Our Result (Algorithm)
Finding an 𝑠–𝑡 pathwith 2 Labels Forbidden𝑠∉ 𝛼, 𝛽𝑡Characterizationfor
2 Possible Labels

Polytime [K.–K.–Y. 2015]

𝑙 = 𝛼, 𝛽• Test "𝑙 ⊆ 𝛼, 𝛽 or NOT" (Based on Our Char.)• 𝑙 ⊆ 𝛼, 𝛽 → Certification for “NO”
• 𝑙 ⊈ 𝛼, 𝛽 → ∃𝛾 ∈ 𝑙 ∖ 𝛼, 𝛽– 𝑙 ≤ 2 → Paths of ALL Possible Labels– 𝑙 ≥ 3 → Paths of 3 Distinct Labels
47

Our Result (Algorithm)
Finding an 𝑠–𝑡 pathwith 2 Labels Forbidden𝑠∉ 𝛼, 𝛽𝑡Characterization
for2 Possible Labels

Polytime [K.–K.–Y. 2015]

𝑙 = 𝛼, 𝛽• Test "𝑙 ⊆ 𝛼, 𝛽 or NOT" (Based on Our Char.)• 𝑙 ⊆ 𝛼, 𝛽 → Certification for “NO”
• 𝑙 ⊈ 𝛼, 𝛽 → ∃𝛾 ∈ 𝑙 ∖ 𝛼, 𝛽– 𝑙 ≤ 2 → Paths of ALL Possible Labels– 𝑙 ≥ 3 → Paths of 3 Distinct Labels
48

Finding 𝑠–𝑡 Paths of 3 Distinct Labels
𝑠1𝑠𝑡

𝑠𝑘49

Finding 𝑠–𝑡 Paths of 3 Distinct Labels𝑙 ≤ 2 or ≥ 3𝑠1𝑡𝑠𝑘50

Finding 𝑠–𝑡 Paths of 3 Distinct Labels
𝑠1𝑡𝑠𝑘𝑙 ≤ 2 or ≥ 351

Finding 𝑠–𝑡 Paths of 3 Distinct Labels𝑠𝑖𝑡∃𝑠𝑖 ∈ 𝑁𝐺 𝑠𝑙 ≥352

Finding 𝑠–𝑡 Paths of 3 Distinct Labels𝑠𝑖𝑡∃𝑠𝑖 ∈ 𝑁𝐺 𝑠𝑙 ≥3
Find 3 𝑠𝑖 –𝑡 paths Recursively

53

Finding 𝑠–𝑡 Paths of 3 Distinct Labels

𝑠𝑠𝑖𝑡∃𝑠𝑖 ∈ 𝑁𝐺 𝑠𝑙 ≥3
Find 3 𝑠𝑖 –𝑡 paths Recursively, and Extend them54

Finding 𝑠–𝑡 Paths of 3 Distinct Labels
𝑠1𝑡∀𝑠𝑖 ∈ 𝑁𝐺 𝑠𝑙 ≤2𝑠𝑘55

Finding 𝑠–𝑡 Paths of 3 Distinct Labels
𝑠1𝑡∀𝑠𝑖 ∈ 𝑁𝐺 𝑠𝑙 ≤2𝑠𝑘Get 𝑠𝑖 –𝑡 paths of ALL possible labels
56

Finding 𝑠–𝑡 Paths of 3 Distinct Labels𝑠1𝑠∀𝑠𝑖 ∈ 𝑁𝐺 𝑠𝑙 ≤2𝑡𝑠𝑘

Get 𝑠𝑖 –𝑡 paths of ALL possible labels, Extend and Select57

Conclusion• Characterization for a Group-Labeled Graphwith Exactly 2 Possible Labels of 𝑠–𝑡 paths– Polytime Testable– Extends Char. for 2-disjoint Paths [Seymour 1980]• Algorithm to find an 𝑠–𝑡 path with 2 Labels Forbidden– Polytime– NOT Depends on Group
Non-abelian or Infinite is OK
If Group Operations in Const. time58

2-contraction
2-contraction of 𝑋 ⊆ 𝑉 ∖ 𝑠, 𝑡 with 𝑁𝐺 𝑋 = 𝑥, 𝑦def

• Remove all vertices in 𝑋
• Add an edge from 𝑥 to 𝑦with each label of an 𝑥–𝑦 path through 𝑋𝑦𝑥

𝑋602-contraction
2-contraction of 𝑋 ⊆ 𝑉 ∖ 𝑠, 𝑡 with 𝑁𝐺 𝑋 = 𝑥, 𝑦def

• Remove all vertices in 𝑋
• Add an edge from 𝑥 to 𝑦with each label of an 𝑥–𝑦 path through 𝑋𝑦𝑥

𝑋→𝑦𝑥
61

2-contraction
2-contraction of 𝑋 ⊆ 𝑉 ∖ 𝑠, 𝑡 with 𝑁𝐺 𝑋 = 𝑥, 𝑦def

• Remove all vertices in 𝑋
• Add an edge from 𝑥 to 𝑦with each label of an 𝑥–𝑦 path through 𝑋.

𝑦𝛼𝑥

𝑋

𝛼→𝑦𝑥
62

2-contraction
2-contraction of 𝑋 ⊆ 𝑉 ∖ 𝑠, 𝑡 with 𝑁𝐺 𝑋 = 𝑥, 𝑦def

• Remove all vertices in 𝑋
• Add an edge from 𝑥 to 𝑦with each label of an 𝑥–𝑦 path through 𝑋.

𝑦𝑥

𝛽

𝑋

𝛼→𝑥𝑦𝛽
63

3-contraction
3-contraction of 𝑋 ⊆ 𝑉 ∖ 𝑠, 𝑡 with 𝑁𝐺 𝑋 = 3(𝐺 𝑋 is connected and 𝐺 𝑋 is balanced)
def• Remove all vertices in 𝑋
• Add an edge 𝑥𝑦 w. label 𝑙 𝐺 𝑋 ; 𝑥, 𝑦

∀𝑥, 𝑦 ∈ 𝑁𝐺 𝑋

𝐺 𝑋 balanced

𝑋conn.

64

3-contraction
3-contraction of 𝑋 ⊆ 𝑉 ∖ 𝑠, 𝑡 with 𝑁𝐺 𝑋 = 3(𝐺 𝑋 is connected and 𝐺 𝑋 is balanced)
def• Remove all vertices in 𝑋
• Add an edge 𝑥𝑦 w. label 𝑙 𝐺 𝑋 ; 𝑥, 𝑦

∀𝑥, 𝑦 ∈ 𝑁𝐺 𝑋

𝑋→65

3-contraction
3-contraction of 𝑋 ⊆ 𝑉 ∖ 𝑠, 𝑡 with 𝑁𝐺 𝑋 = 3(𝐺 𝑋 is connected and 𝐺 𝑋 is balanced)
def• Remove all vertices in 𝑋
• Add an edge 𝑥𝑦 w. label 𝑙 𝐺 𝑋 ; 𝑥, 𝑦𝑋𝛼𝑥∀𝑥, 𝑦 ∈ 𝑁𝐺 𝑋

𝐺 𝑋 balanced ⟺ 𝛼 is unique
𝛼𝑦𝑦→𝑥66