Local Ce i ica ion o Reachabili y
Oli e Bach le , Tim Be gne , and S en O. K umke
Depa men o Ma hema ics
TU Kaise slau e n
In e na ional Ne wo k Op imiza ion Con e ence, 2022
Mo i a ion
In essence: wan o e i y ha a g aph has a ce ain p ope y.
Bu : we only see a local iew a ound e e y e ex. ⇒limi ed in o ma ion
BA
B
A B
A
AB
A
B A
B
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 1 / 18
Mo i a ion
In essence: wan o e i y ha a g aph has a ce ain p ope y.
Bu : we only see a local iew a ound e e y e ex.
⇒limi ed in o ma ion
BA
B
A B
A
AB
A
B A
B
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 1 / 18
Mo i a ion
In essence: wan o e i y ha a g aph has a ce ain p ope y.
Bu : we only see a local iew a ound e e y e ex. ⇒limi ed in o ma ion
BA
B
A B
A
AB
A
B A
B
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 1 / 18
Mo i a ion
In essence: wan o e i y ha a g aph has a ce ain p ope y.
Bu : we only see a local iew a ound e e y e ex. ⇒limi ed in o ma ion
BA
B
A B
A
AB
A
B A
B
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 1 / 18
Mo i a ion
In essence: wan o e i y ha a g aph has a ce ain p ope y.
Bu : we only see a local iew a ound e e y e ex. ⇒limi ed in o ma ion
BA
B
A B
A
AB
A
B A
B
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 1 / 18
Mo i a ion
In essence: wan o e i y ha a g aph has a ce ain p ope y.
Bu : we only see a local iew a ound e e y e ex. ⇒limi ed in o ma ion
BA
B
A B
A
AB
A
B A
B
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 1 / 18
Mo i a ion
In essence: wan o e i y ha a g aph has a ce ain p ope y.
Bu : we only see a local iew a ound e e y e ex. ⇒limi ed in o ma ion
My kingdom
should be cubic.
BA
B
A B
A
AB
A
B A
B
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 1 / 18
Mo i a ion
In essence: wan o e i y ha a g aph has a ce ain p ope y.
Bu : we only see a local iew a ound e e y e ex. ⇒limi ed in o ma ion
My kingdom
should be cubic.
BA
B
A B
A
AB
A
B A
B
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 1 / 18
Mo i a ion
In essence: wan o e i y ha a g aph has a ce ain p ope y.
Bu : we only see a local iew a ound e e y e ex. ⇒limi ed in o ma ion
Looks good.
BA
B
A B
A
AB
A
B A
B
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 1 / 18
Mo i a ion
In essence: wan o e i y ha a g aph has a ce ain p ope y.
Bu : we only see a local iew a ound e e y e ex. ⇒limi ed in o ma ion
This is w ong,
no i y he king!
BA
B
A B
A
AB
A
B A
B
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 1 / 18
Mo i a ion
In essence: wan o e i y ha a g aph has a ce ain p ope y.
Bu : we only see a local iew a ound e e y e ex. ⇒limi ed in o ma ion
I also wan my
kingdom o be
bipa i e.
BA
B
A B
A
AB
A
B A
B
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 1 / 18
Mo i a ion
In essence: wan o e i y ha a g aph has a ce ain p ope y.
Bu : we only see a local iew a ound e e y e ex. ⇒limi ed in o ma ion
I also wan my
kingdom o be
bipa i e.
BA
B
A B
A
AB
A
B A
B
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 1 / 18
Mo i a ion
In essence: wan o e i y ha a g aph has a ce ain p ope y.
Bu : we only see a local iew a ound e e y e ex. ⇒limi ed in o ma ion
BA
B
A B
A
AB
A
B A
B
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 1 / 18
Mo i a ion
In essence: wan o e i y ha a g aph has a ce ain p ope y.
Bu : we only see a local iew a ound e e y e ex. ⇒limi ed in o ma ion
Is his eally
bipa i e?
BA
B
A B
A
AB
A
B A
B
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 1 / 18
Mo i a ion
In essence: wan o e i y ha a g aph has a ce ain p ope y.
Bu : we only see a local iew a ound e e y e ex. ⇒limi ed in o ma ion
Don’ o ge
you o de s!
BA
B
A B
A
AB
A
B A
B
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 1 / 18
Mo i a ion
In essence: wan o e i y ha a g aph has a ce ain p ope y.
Bu : we only see a local iew a ound e e y e ex. ⇒limi ed in o ma ion
BA
B
A B
A
AB
A
B A
B
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 1 / 18
Mo i a ion
In essence: wan o e i y ha a g aph has a ce ain p ope y.
Bu : we only see a local iew a ound e e y e ex. ⇒limi ed in o ma ion
BA
B
A B
A
AB
A
B A
B
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 1 / 18
Mo i a ion
In essence: wan o e i y ha a g aph has a ce ain p ope y.
Bu : we only see a local iew a ound e e y e ex. ⇒limi ed in o ma ion
O de has been
es ablished!
BA
B
A B
A
AB
A
B A
B
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 1 / 18
The Se ing
▶Gis a class o g aphs (all undi ec ed g aphs).
▶F⊆ G is a subse o Gsa is ying a ce ain p ope y (cubic,bipa i e).
▶Each e ex o a g aph has an iden i y, which a e
▶dis inc o
▶iden ical, in which case he g aph is anonymous.
▶Ve ices also ha e labels, which con ain p oblem-speci ic in o ma ion.
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 4 / 18
The Se ing
▶Gis a class o g aphs (all undi ec ed g aphs).
▶F⊆ G is a subse o Gsa is ying a ce ain p ope y (cubic,bipa i e).
▶Each e ex o a g aph has an iden i y, which a e
▶dis inc o
▶iden ical, in which case he g aph is anonymous.
▶Ve ices also ha e labels, which con ain p oblem-speci ic in o ma ion.
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 4 / 18
The Se ing
▶Gis a class o g aphs (all undi ec ed g aphs).
▶F⊆ G is a subse o Gsa is ying a ce ain p ope y (cubic,bipa i e).
▶Each e ex o a g aph has an iden i y, which a e
▶dis inc o
▶iden ical, in which case he g aph is anonymous.
▶Ve ices also ha e labels, which con ain p oblem-speci ic in o ma ion.
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 4 / 18
P o e s
De ini ion (P o e )
▶Ap o e ( o F) is a unc ion P ha maps G∈ F o a p oo o G.
▶The size o Pis he maximum size o any p oo i assigns o F.
De ini ion (P oo )
▶Ap oo o a g aph Gis a unc ion P:V(G)→ {0,1}∗ ha assigns a
bina y ce i ica e o each e ex o G.
▶The size o a p oo is he leng h o i s longes ce i ica e.
0
1
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 5 / 18
P o e s
De ini ion (P o e )
▶Ap o e ( o F) is a unc ion P ha maps G∈ F o a p oo o G.
▶The size o Pis he maximum size o any p oo i assigns o F.
De ini ion (P oo )
▶Ap oo o a g aph Gis a unc ion P:V(G)→ {0,1}∗ ha assigns a
bina y ce i ica e o each e ex o G.
▶The size o a p oo is he leng h o i s longes ce i ica e.
0
1
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 5 / 18
P o e s
De ini ion (P o e )
▶Ap o e ( o F) is a unc ion P ha maps G∈ F o a p oo o G.
▶The size o Pis he maximum size o any p oo i assigns o F.
De ini ion (P oo )
▶Ap oo o a g aph Gis a unc ion P:V(G)→ {0,1}∗ ha assigns a
bina y ce i ica e o each e ex o G.
▶The size o a p oo is he leng h o i s longes ce i ica e.
0
1
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 5 / 18
P o e s
De ini ion (P o e )
▶Ap o e ( o F) is a unc ion P ha maps G∈ F o a p oo o G.
▶The size o Pis he maximum size o any p oo i assigns o F.
De ini ion (P oo )
▶Ap oo o a g aph Gis a unc ion P:V(G)→ {0,1}∗ ha assigns a
bina y ce i ica e o each e ex o G.
▶The size o a p oo is he leng h o i s longes ce i ica e.
0
1
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 5 / 18
P o e s
De ini ion (P o e )
▶Ap o e ( o F) is a unc ion P ha maps G∈ F o a p oo o G.
▶The size o Pis he maximum size o any p oo i assigns o F.
De ini ion (P oo )
▶Ap oo o a g aph Gis a unc ion P:V(G)→ {0,1}∗ ha assigns a
bina y ce i ica e o each e ex o G.
▶The size o a p oo is he leng h o i s longes ce i ica e.
0
1
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 5 / 18
Ve i ie s
De ini ion (Ve i ie )
▶A e i ie V( o G) is a unc ion ha maps iples (G,P, ) o {0,1}
and sa is ies
V(G,P, ) = V(G[N[ ]],P[N[ ]], ) o all G,P, .
▶Vaccep s a p oo Pa ∈V(G)i V(G,P, ) = 1.
▶Vaccep s a p oo P o a g aph Gi i accep s a all ∈V(G)and
▶V ejec s he p oo o he wise.
0
1
0 1
00
1 0
1
01
1
1
01
1
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 6 / 18
Ve i ie s
De ini ion (Ve i ie )
▶A e i ie V( o G) is a unc ion ha maps iples (G,P, ) o {0,1}
and sa is ies
V(G,P, ) = V(G[N[ ]],P[N[ ]], ) o all G,P, .
▶Vaccep s a p oo Pa ∈V(G)i V(G,P, ) = 1.
▶Vaccep s a p oo P o a g aph Gi i accep s a all ∈V(G)and
▶V ejec s he p oo o he wise.
0
1
0 1
00
1 0
1
01
1
1
01
1
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 6 / 18
Ve i ie s
De ini ion (Ve i ie )
▶A e i ie V( o G) is a unc ion ha maps iples (G,P, ) o {0,1}
and sa is ies
V(G,P, ) = V(G[N[ ]],P[N[ ]], ) o all G,P, .
▶Vaccep s a p oo Pa ∈V(G)i V(G,P, ) = 1.
▶Vaccep s a p oo P o a g aph Gi i accep s a all ∈V(G)and
▶V ejec s he p oo o he wise.
0
1
0 1
00
1 0
1
01
1
1
01
1
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 6 / 18
P oo Labelling Schemes
De ini ion (P oo Labelling Scheme)
▶A pai π= (P,V)is a p oo labelling scheme o F ⊆ G i
▶Vaccep s P(G) o all G∈ F.
▶V ejec s any g aph no in F.
▶The size o πis he size o i s p o e .
0
1
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 7 / 18
P oo Labelling Schemes
De ini ion (P oo Labelling Scheme)
▶A pai π= (P,V)is a p oo labelling scheme o F ⊆ G i
▶Vaccep s P(G) o all G∈ F.
▶V ejec s any g aph no in F.
▶The size o πis he size o i s p o e .
0
1
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 7 / 18
P oo Labelling Schemes
De ini ion (P oo Labelling Scheme)
▶A pai π= (P,V)is a p oo labelling scheme o F ⊆ G i
▶Vaccep s P(G) o all G∈ F.
▶V ejec s any g aph no in F.
▶The size o πis he size o i s p o e .
0
1
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 7 / 18
P oo Labelling Schemes
De ini ion (P oo Labelling Scheme)
▶A pai π= (P,V)is a p oo labelling scheme o F ⊆ G i
▶Vaccep s P(G) o all G∈ F.
▶V ejec s any g aph no in F.
▶The size o πis he size o i s p o e .
0
1
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 7 / 18
Examples
( aken om Göös, Suomela 2016)
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 8 / 18
Back o he Mo i a ion.
Example (Cubic G aphs)
▶No p oo needed: p o e assigns e e y e ex an emp y ce i ica e.
▶The e i ie a checks ha has deg ee 3.
▶Accep s exac ly he cubic g aphs.
⇒A p oo labelling scheme o size 0 exis s o cubic g aphs.
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 9 / 18
Back o he Mo i a ion.
Example (Cubic G aphs)
▶No p oo needed: p o e assigns e e y e ex an emp y ce i ica e.
▶The e i ie a checks ha has deg ee 3.
▶Accep s exac ly he cubic g aphs.
⇒A p oo labelling scheme o size 0 exis s o cubic g aphs.
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 9 / 18
Back o he Mo i a ion.
Example (Cubic G aphs)
▶No p oo needed: p o e assigns e e y e ex an emp y ce i ica e.
▶The e i ie a checks ha has deg ee 3.
▶Accep s exac ly he cubic g aphs.
⇒A p oo labelling scheme o size 0 exis s o cubic g aphs.
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 9 / 18
Back o he Mo i a ion.
Example (Cubic G aphs)
▶No p oo needed: p o e assigns e e y e ex an emp y ce i ica e.
▶The e i ie a checks ha has deg ee 3.
▶Accep s exac ly he cubic g aphs.
⇒A p oo labelling scheme o size 0 exis s o cubic g aphs.
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 9 / 18
Mo e Examples: Reachabili y
De ini ion (s -Reachabili y)
In he
di ec ed
s - eachabili y p oblem
▶Gis he class o all
di ec ed
g aphs wi h a e ex sand .
▶Fcon ains hose g aphs in which is eachable om s.
s s
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 11 / 18
Mo e Examples: Reachabili y
De ini ion (s -Reachabili y)
In he
di ec ed
s - eachabili y p oblem
▶Gis he class o all
di ec ed
g aphs wi h a e ex sand .
▶Fcon ains hose g aphs in which is eachable om s.
s s
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 11 / 18
Mo e Examples: Reachabili y
De ini ion (s -Reachabili y)
In he di ec ed s - eachabili y p oblem
▶Gis he class o all di ec ed g aphs wi h a e ex sand .
▶Fcon ains hose g aphs in which is eachable om s.
s s
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 11 / 18
Mo e Examples: Reachabili y
Example (s -Reachabili y)
▶Use p oo o speci y a sho es pa h: p o e assigns ei he 0 o 1 o
each e ex o indica e whe he i is on a ixed sho es pa h.
▶The e i ie a checks ha has wo neighbou s wi h p oo 1 i i
has p oo 1 (o one i =so = ).
▶Accep s exac ly he g aphs whe e is eachable om s.
⇒A p oo labelling scheme o size 1 exis s o s - eachabili y.
s
1
1
1 1
0 0 0
0
1
1
1
0 0
0
1
0
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 12 / 18
Mo e Examples: Reachabili y
Example (s -Reachabili y)
▶Use p oo o speci y a sho es pa h: p o e assigns ei he 0 o 1 o
each e ex o indica e whe he i is on a ixed sho es pa h.
▶The e i ie a checks ha has wo neighbou s wi h p oo 1 i i
has p oo 1 (o one i =so = ).
▶Accep s exac ly he g aphs whe e is eachable om s.
⇒A p oo labelling scheme o size 1 exis s o s - eachabili y.
s
1
1
1 1
0 0 0
0
1
1
1
0 0
0
1
0
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 12 / 18
Mo e Examples: Reachabili y
Example (s -Reachabili y)
▶Use p oo o speci y a sho es pa h: p o e assigns ei he 0 o 1 o
each e ex o indica e whe he i is on a ixed sho es pa h.
▶The e i ie a checks ha has wo neighbou s wi h p oo 1 i i
has p oo 1 (o one i =so = ).
▶Accep s exac ly he g aphs whe e is eachable om s.
⇒A p oo labelling scheme o size 1 exis s o s - eachabili y.
s
1
1
1 1
0 0 0
0
1
1
1
0 0
0
1
0
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 12 / 18
Mo e Examples: Reachabili y
Example (s -Reachabili y)
▶Use p oo o speci y a sho es pa h: p o e assigns ei he 0 o 1 o
each e ex o indica e whe he i is on a ixed sho es pa h.
▶The e i ie a checks ha has wo neighbou s wi h p oo 1 i i
has p oo 1 (o one i =so = ).
▶Accep s exac ly he g aphs whe e is eachable om s.
⇒A p oo labelling scheme o size 1 exis s o s - eachabili y.
s
1
1
1 1
0 0 0
0
1
1
1
0 0
0
1
0
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 12 / 18
Mo e Examples: Reachabili y
Example (s -Reachabili y)
▶Use p oo o speci y a sho es pa h: p o e assigns ei he 0 o 1 o
each e ex o indica e whe he i is on a ixed sho es pa h.
▶The e i ie a checks ha has wo neighbou s wi h p oo 1 i i
has p oo 1 (o one i =so = ).
▶Accep s exac ly he g aphs whe e is eachable om s.
⇒A p oo labelling scheme o size 1 exis s o s - eachabili y.
s
1
1
1 1
0 0 0
0
1
1
1
0 0
0
1
0
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 12 / 18
Mo e Examples: Reachabili y
Example (Di ec ed s -Reachabili y)
▶Use p oo o speci y a sho es pa h:
p o e assigns each e ex on a
ixed sho es pa h a poin e o i s successo .
▶The e i ie a checks ha i has a poin e , hen one o i s
p edecesso s poin s o i (unless =so = ).
▶Accep s exac ly he di ec ed g aphs whe e is eachable om s.
⇒A p oo labelling scheme o size log(∆) exis s o di . s - eachabili y.
s
1
1 1
1 1
0 0 0
1
1
1
ε ε
ε
εε
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 13 / 18
Mo e Examples: Reachabili y
Example (Di ec ed s -Reachabili y)
▶Use p oo o speci y a sho es pa h:
p o e assigns each e ex on a
ixed sho es pa h a poin e o i s successo .
▶The e i ie a checks ha i has a poin e , hen one o i s
p edecesso s poin s o i (unless =so = ).
▶Accep s exac ly he di ec ed g aphs whe e is eachable om s.
⇒A p oo labelling scheme o size log(∆) exis s o di . s - eachabili y.
s
1
1 1
1 1
0 0 0
1
1
1
ε ε
ε
εε
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 13 / 18
Mo e Examples: Reachabili y
Example (Di ec ed s -Reachabili y)
▶Use p oo o speci y a sho es pa h: p o e assigns each e ex on a
ixed sho es pa h a poin e o i s successo .
▶The e i ie a checks ha i has a poin e , hen one o i s
p edecesso s poin s o i (unless =so = ).
▶Accep s exac ly he di ec ed g aphs whe e is eachable om s.
⇒A p oo labelling scheme o size log(∆) exis s o di . s - eachabili y.
s
1
1 1
1 1
0 0 0
1
1
1
ε ε
ε
ε
ε
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 13 / 18
How Di icul is Ve i ying Reachabili y?
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 14 / 18
Li e a u e
A. Ko man, S. Ku en and D. Peleg
P oo labeling schemes
Dis ibu ed Compu ing, ol. 22, pp. 215–233, 2010.
M. Göös and J. Suomela
Locally Checkable P oo s in Dis ibu ed Compu ing
Theo y o Compu ing, ol. 12, no. 19, pp. 1–33, 2016.
K. Foe s e , T. Luedi, J. Seidel and R. Wa enho e
Local checkabili y, no s ings a ached: (A)cyclici y, eachabili y, loop
ee upda es in SDNs
Theo e ical Compu e Science, ol. 709, pp. 48–63, 2018.
A. Ko man and S. Ku en
Dis ibu ed Ve i ica ion o Minimum Spanning T ees
PODC, 2006.
L. Feuilloley e al.
Compac Dis ibu ed Ce i ica ion o Plana G aphs
Algo i hmica, ol. 83, no. 7, pp. 2215–2244, 2021.
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 15 / 18
Di ec ed is Ha de Than Undi ec ed Reachabili y
Goal: we wan o p o e ha
Theo em
No p oo labelling scheme o size o(log(∆)) exis s o di ec ed
s - eachabili y on anonymous g aphs.
Idea:
s
u
s
u
ab
ab
ab
ab
ab
ab
u
u
ab
ab
u
u
Resul : o bids
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 16 / 18
Di ec ed is Ha de Than Undi ec ed Reachabili y
Goal: we wan o p o e ha
Theo em
No p oo labelling scheme o size o(log(∆)) exis s o di ec ed
s - eachabili y on anonymous g aphs.
Idea:
s
u
s
u
ab
ab
ab
ab
ab
ab
u
u
ab
ab
u
u
Resul : o bids
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 16 / 18
Di ec ed is Ha de Than Undi ec ed Reachabili y
Goal: we wan o p o e ha
Theo em
No p oo labelling scheme o size o(log(∆)) exis s o di ec ed
s - eachabili y on anonymous g aphs.
Idea:
s
u
s
u
ab
ab
ab
ab
ab
ab
u
u
ab
ab
u
u
Resul : o bids
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 16 / 18
Di ec ed is Ha de Than Undi ec ed Reachabili y
Goal: we wan o p o e ha
Theo em
No p oo labelling scheme o size o(log(∆)) exis s o di ec ed
s - eachabili y on anonymous g aphs.
Idea:
s
u
s
u
ab
ab
ab
ab
ab
ab
u
u
ab
ab
u
u
Resul : o bids
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 16 / 18
Di ec ed is Ha de Than Undi ec ed Reachabili y
Goal: we wan o p o e ha
Theo em
No p oo labelling scheme o size o(log(∆)) exis s o di ec ed
s - eachabili y on anonymous g aphs.
Idea:
s
u
s
u
ab
ab
ab
ab
ab
ab
u
u
ab
ab
u
u
Resul : o bids
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 16 / 18
Di ec ed is Ha de Than Undi ec ed Reachabili y
Goal: we wan o p o e ha
Theo em
No p oo labelling scheme o size o(log(∆)) exis s o di ec ed
s - eachabili y on anonymous g aphs.
Idea:
s
u
s
u
ab
ab
ab
ab
ab
ab
u
u
ab
ab
u
u
Resul : o bids
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 16 / 18
Di ec ed is Ha de Than Undi ec ed Reachabili y
Goal: we wan o p o e ha
Theo em
No p oo labelling scheme o size o(log(∆)) exis s o di ec ed
s - eachabili y on anonymous g aphs.
Idea:
s
u
s
u
ab
ab
ab
ab
ab
ab
u
u
ab
ab
u
u
Resul : o bids
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 16 / 18
P oo Ske ch
s
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 17 / 18
P oo Ske ch
Plan: add back-edges o o bid pai s
o bidden
s
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 17 / 18
P oo Ske ch
Goal: i e a i ely o bid mo e and mo e pai s
o bidden
s
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 17 / 18
P oo Ske ch
Goal: i e a i ely o bid mo e and mo e pai s
o bidden
s
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 17 / 18
P oo Ske ch
Wan : same colou ed o wa d-edges connec ed by back-edges
and o bidden
s
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 17 / 18
P oo Ske ch
How: use he Pigeon Hole P inciple
s
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 17 / 18
P oo Ske ch
Resul : pai o bidden in all g ey a eas
s
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 17 / 18
P oo Ske ch
Now: plug in ecu si ely o o bid mo e pai s
s
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 17 / 18
Summa y
We ha e:
▶ o mally de ined p oo labelling schemes,
▶illus a ed hese on se e al examples, and
▶showed ha Θ(log(∆)) a e needed o ce i y di ec ed s - eachabili y.
Con ac : bach le @ma hema ik.uni-kl.de
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 18 / 18
Almos all O he Examples
Example (Uni e sal P oo Labelling Scheme)
▶Assume we can decide o a g aph G∈ G whe he G∈ F.
▶Use p oo o speci y he g aph: p o e assigns he adjacency ma ix A
and he co esponding ow o each e ex.
▶The e i ie a checks ha i s neighbou hood is co ec and ha
he g aph gi en by Ais in F.
▶Accep s exac ly he g aphs in F.
⇒The e exis s a uni e sal p oo labelling scheme o size O(n2).
A,7
A,1
A,8
A,2
A,9 A,3
A,10
A,4
A,11
A,5
A,12A,6
A,7
A,1
A,8
A,2
A,9 A,3
A,10
A,4
A,11
A,5
A,12A,6
Bach le , Be gne , K umke (TUK) Ce i ying Reachabili y INOC 2022 1 / 1
