On Algo i hmic Ce i ica ion o G aph S uc u es
Oli e Bach le
Depa men o Ma hema ics
RPTU in Kaise slau e n
30.03.2023
Mo i a ion
Fou Colou Theo em (in o mal e sion)
E e y map can be colou ed wi h a mos ou colou s.
Fou Colou Theo em
E e y plana g aph is 4-colou able.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 1 / 25
Mo i a ion
Fou Colou Theo em (in o mal e sion)
E e y map can be colou ed wi h a mos ou colou s.
Fou Colou Theo em
E e y plana g aph is 4-colou able.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 1 / 25
Mo i a ion
Fou Colou Theo em (in o mal e sion)
E e y map can be colou ed wi h a mos ou colou s.
Fou Colou Theo em
E e y plana g aph is 4-colou able.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 1 / 25
Mo i a ion
Fou Colou Theo em (in o mal e sion)
E e y map can be colou ed wi h a mos ou colou s.
Fou Colou Theo em
E e y plana g aph is 4-colou able.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 1 / 25
Mo i a ion
Fou Colou Theo em (in o mal e sion)
E e y map can be colou ed wi h a mos ou colou s.
Fou Colou Theo em
E e y plana g aph is 4-colou able.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 1 / 25
Mo i a ion
Fou Colou Theo em (in o mal e sion)
E e y map can be colou ed wi h a mos ou colou s.
Fou Colou Theo em
E e y plana g aph is 4-colou able.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 1 / 25
P o ing he Fou Colou Theo em
Find a se o con igu a ions ha is
▶ educible and
▶checked by a compu e
▶una oidable.
▶by hand, 400 pages
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 2 / 25
P o ing he Fou Colou Theo em
Find a se o con igu a ions ha is
▶ educible and
▶checked by a compu e
▶una oidable.
▶by hand, 400 pages
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 2 / 25
P o ing he Fou Colou Theo em
Find a se o con igu a ions ha is
▶ educible and
▶checked by a compu e
▶una oidable.
▶by hand, 400 pages
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 2 / 25
P o ing he Fou Colou Theo em
Find a se o con igu a ions ha is
▶ educible and
▶checked by a compu e
▶una oidable.
▶by hand, 400 pages
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 2 / 25
P o ing he Fou Colou Theo em
Find a se o con igu a ions ha is
▶ educible and
▶checked by a compu e
▶una oidable.
▶by hand, 400 pages
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 2 / 25
Ou line
The 3-Decomposi ion Conjec u e
In oduc ion
Reducible Con igu a ions
Una oidable S uc u es
Au oma ion Fo Una oidable S uc u es
Ob aining an Algo i hm
Speeding I Up
Does I E en Te mina e
Thesis O e iew
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 3 / 25
The 3-Decomposi ion Conjec u e
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 4 / 25
3-Decomposi ions o G aphs
De ini ion
A g aph is cubic i e e y e ex has deg ee 3.
De ini ion
A3-decomposi ion o a connec ed cubic g aph Gconsis s o
▶aspanning ee T,
▶aunion o cycles C, and
▶ama ching M
such ha E(G)is he disjoin union E(T)∪E(C)∪M.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 5 / 25
3-Decomposi ions o G aphs
De ini ion
A g aph is cubic i e e y e ex has deg ee 3.
De ini ion
A3-decomposi ion o a connec ed cubic g aph Gconsis s o
▶aspanning ee T,
▶aunion o cycles C, and
▶ama ching M
such ha E(G)is he disjoin union E(T)∪E(C)∪M.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 5 / 25
3-Decomposi ions o G aphs
De ini ion
A g aph is cubic i e e y e ex has deg ee 3.
De ini ion
A3-decomposi ion o a connec ed cubic g aph Gconsis s o
▶aspanning ee T,
▶aunion o cycles C, and
▶ama ching M
such ha E(G)is he disjoin union E(T)∪E(C)∪M.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 5 / 25
An Example G aph
▶Gi en: connec ed cubic g aph.
▶Take a spanning ee.
▶The emaining edges o m
cycles and pa hs.
▶Wan pa hs o leng h 1.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 6 / 25
An Example G aph
▶Gi en: connec ed cubic g aph.
▶Take a spanning ee.
▶The emaining edges o m
cycles and pa hs.
▶Wan pa hs o leng h 1.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 6 / 25
The 3-Decomposi ion Conjec u e
De ini ion
A3-decomposi ion o a connec ed cubic g aph Gconsis s o
▶aspanning ee T,
▶aunion o cycles C, and
▶ama ching M
such ha E(G)is he disjoin union E(T)∪E(C)∪M.
3-Decomposi ion Conjec u e
E e y connec ed cubic g aph has a 3-decomposi ion.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 7 / 25
Li e a u e O e iew
▶Hamil onian
▶ aceable
▶3-conn. plana , p ojec i e plane
▶‘3 cycles’
▶‘cac i-ish’
▶‘s a -like’
▶3-connec ed To us, Klein Bo le
▶plana
▶claw- ee
▶3-connec ed ee-wid h 3
▶3-connec ed pa h-wid h 4
2011 2015 2016 2018 2019 2020 2021 2022
[Ho 11]
[AJS15] [Abd+16] [LL20] [Bo +21] [BK22]
[OY16] [XZZ20]
[Cam11]
[Bac15] [HKO18] [Hei19] [HLY20] [BH21]
[AAA18]
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 8 / 25
Li e a u e O e iew
▶Hamil onian
▶ aceable
▶3-conn. plana , p ojec i e plane
▶‘3 cycles’
▶‘cac i-ish’
▶‘s a -like’
▶3-connec ed To us, Klein Bo le
▶plana
▶claw- ee
▶3-connec ed ee-wid h 3
▶3-connec ed pa h-wid h 4
2011 2015 2016 2018 2019 2020 2021 2022
[Ho 11] [AJS15]
[Abd+16] [LL20] [Bo +21] [BK22]
[OY16] [XZZ20]
[Cam11]
[Bac15] [HKO18] [Hei19] [HLY20] [BH21]
[AAA18]
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 8 / 25
Li e a u e O e iew
▶Hamil onian
▶ aceable
▶3-conn. plana , p ojec i e plane
▶‘3 cycles’
▶‘cac i-ish’
▶‘s a -like’
▶3-connec ed To us, Klein Bo le
▶plana
▶claw- ee
▶3-connec ed ee-wid h 3
▶3-connec ed pa h-wid h 4
2011 2015 2016 2018 2019 2020 2021 2022
[Ho 11] [AJS15] [Abd+16] [LL20]
[Bo +21] [BK22]
[OY16] [XZZ20]
[Cam11]
[Bac15] [HKO18] [Hei19] [HLY20] [BH21]
[AAA18]
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 8 / 25
Li e a u e O e iew
▶Hamil onian
▶ aceable
▶3-conn. plana , p ojec i e plane
▶‘3 cycles’
▶‘cac i-ish’
▶‘s a -like’
▶3-connec ed To us, Klein Bo le
▶plana
▶claw- ee
▶3-connec ed ee-wid h 3
▶3-connec ed pa h-wid h 4
2011 2015 2016 2018 2019 2020 2021 2022
[Ho 11] [AJS15] [Abd+16] [LL20]
[Bo +21] [BK22]
[OY16]
[XZZ20]
[Cam11]
[Bac15] [HKO18] [Hei19] [HLY20] [BH21]
[AAA18]
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 8 / 25
Li e a u e O e iew
▶Hamil onian
▶ aceable
▶3-conn. plana , p ojec i e plane
▶‘3 cycles’
▶‘cac i-ish’
▶‘s a -like’
▶3-connec ed To us, Klein Bo le
▶plana
▶claw- ee
▶3-connec ed ee-wid h 3
▶3-connec ed pa h-wid h 4
2011 2015 2016 2018 2019 2020 2021 2022
[Ho 11] [AJS15] [Abd+16] [LL20]
[Bo +21] [BK22]
[OY16] [XZZ20]
[Cam11]
[Bac15] [HKO18] [Hei19] [HLY20] [BH21]
[AAA18]
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 8 / 25
Li e a u e O e iew
▶Hamil onian
▶ aceable
▶3-conn. plana , p ojec i e plane
▶‘3 cycles’
▶‘cac i-ish’
▶‘s a -like’
▶3-connec ed To us, Klein Bo le
▶plana
▶claw- ee
▶3-connec ed ee-wid h 3
▶3-connec ed pa h-wid h 4
2011 2015 2016 2018 2019 2020 2021 2022
[Ho 11] [AJS15] [Abd+16] [LL20] [Bo +21]
[BK22]
[OY16] [XZZ20]
[Cam11]
[Bac15] [HKO18] [Hei19] [HLY20] [BH21]
[AAA18]
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 8 / 25
Li e a u e O e iew
▶Hamil onian
▶ aceable
▶3-conn. plana , p ojec i e plane
▶‘3 cycles’
▶‘cac i-ish’
▶‘s a -like’
▶3-connec ed To us, Klein Bo le
▶plana
▶claw- ee
▶3-connec ed ee-wid h 3
▶3-connec ed pa h-wid h 4
2011 2015 2016 2018 2019 2020 2021 2022
[Ho 11] [AJS15] [Abd+16] [LL20] [Bo +21] [BK22]
[OY16] [XZZ20]
[Cam11]
[Bac15] [HKO18] [Hei19] [HLY20] [BH21]
[AAA18]
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 8 / 25
Li e a u e O e iew
▶Hamil onian
▶ aceable
▶3-conn. plana , p ojec i e plane
▶‘3 cycles’
▶‘cac i-ish’
▶‘s a -like’
▶3-connec ed To us, Klein Bo le
▶plana
▶claw- ee
▶3-connec ed ee-wid h 3
▶3-connec ed pa h-wid h 4
2011 2015 2016 2018 2019 2020 2021 2022
[Ho 11] [AJS15] [Abd+16] [LL20] [Bo +21] [BK22]
[OY16] [XZZ20]
[Cam11] [Bac15]
[HKO18] [Hei19] [HLY20] [BH21]
[AAA18]
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 8 / 25
Li e a u e O e iew
▶Hamil onian
▶ aceable
▶3-conn. plana , p ojec i e plane
▶‘3 cycles’
▶‘cac i-ish’
▶‘s a -like’
▶3-connec ed To us, Klein Bo le
▶plana
▶claw- ee
▶3-connec ed ee-wid h 3
▶3-connec ed pa h-wid h 4
2011 2015 2016 2018 2019 2020 2021 2022
[Ho 11] [AJS15] [Abd+16] [LL20] [Bo +21] [BK22]
[OY16] [XZZ20]
[Cam11] [Bac15] [HKO18]
[Hei19] [HLY20] [BH21]
[AAA18]
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 8 / 25
Reducible Con igu a ions
De ini ion
A educible con igu a ion is a g aph ha is no pa o a (3-connec ed)
minimum coun e example o he 3-decomposi ion conjec u e.
Example
The iangle is educible.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 9 / 25
Reducible Con igu a ions
De ini ion
A educible con igu a ion is a g aph ha is no pa o a (3-connec ed)
minimum coun e example o he 3-decomposi ion conjec u e.
Example
The iangle is educible.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 9 / 25
Reducible Con igu a ions
De ini ion
A educible con igu a ion is a g aph ha is no pa o a (3-connec ed)
minimum coun e example o he 3-decomposi ion conjec u e.
Example
The iangle is educible.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 9 / 25
Reducible Con igu a ions
De ini ion
A educible con igu a ion is a g aph ha is no pa o a (3-connec ed)
minimum coun e example o he 3-decomposi ion conjec u e.
Example
The iangle is educible.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 9 / 25
A Bigge Example
Example
The claw-squa e is educible.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 10 / 25
A Bigge Example
Example
The claw-squa e is educible.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 10 / 25
A Lis o Reducible Con igu a ions
Theo em
The g aphs below a e educible con igu a ions.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 11 / 25
Una oidable S uc u es
Ques ion: A e hese educible con igu a ions una oidable?
Answe : No (sadly).
Solu ion: Res ic he class o cubic g aphs o make hem una oidable.
⇒Bound he pa h-wid h.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 12 / 25
Una oidable S uc u es
Ques ion: A e hese educible con igu a ions una oidable?
Answe : No (sadly).
Solu ion: Res ic he class o cubic g aphs o make hem una oidable.
⇒Bound he pa h-wid h.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 12 / 25
Una oidable S uc u es
Ques ion: A e hese educible con igu a ions una oidable?
Answe : No (sadly).
Solu ion: Res ic he class o cubic g aphs o make hem una oidable.
⇒Bound he pa h-wid h.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 12 / 25
Bounding he Pa h-Wid h
Theo em
Cubic g aphs o pa h-wid h a mos 4con ain a educible con igu a ion.
Co olla y
E e y (3-connec ed) cubic g aph o pa h-wid h a mos 4sa is ies he
3-decomposi ion conjec u e.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 14 / 25
Bounding he Pa h-Wid h
Theo em
Cubic g aphs o pa h-wid h a mos 4con ain a educible con igu a ion.
Co olla y
E e y (3-connec ed) cubic g aph o pa h-wid h a mos 4sa is ies he
3-decomposi ion conjec u e.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 14 / 25
Au oma ion Fo Una oidable S uc u es
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 15 / 25
Finding Una oidable S uc u es o Bounded Pa h-Wid h
3-Decomposi ion Conjec u e
E e y connec ed cubic g aph has a
3-decomposi ion.
Fou Colou Theo em
E e y plana g aph is 4-colou able.
Conjec u e
E e y g aph in Gsa is ies p ope y π.
Ques ion:
Does e e y g aph in Go pa h-wid h a mos kcon ain a subg aph in U?
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 16 / 25
Finding Una oidable S uc u es o Bounded Pa h-Wid h
3-Decomposi ion Conjec u e
E e y connec ed cubic g aph has a
3-decomposi ion.
Fou Colou Theo em
E e y plana g aph is 4-colou able.
Conjec u e
E e y g aph in Gsa is ies p ope y π.
Ques ion:
Does e e y g aph in Go pa h-wid h a mos kcon ain a subg aph in U?
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 16 / 25
Finding Una oidable S uc u es o Bounded Pa h-Wid h
3-Decomposi ion Conjec u e
E e y connec ed cubic g aph has a
3-decomposi ion.
Fou Colou Theo em
E e y plana g aph is 4-colou able.
Conjec u e
E e y g aph in Gsa is ies p ope y π.
Ques ion:
Does e e y g aph in Go pa h-wid h a mos kcon ain a subg aph in U?
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 16 / 25
Finding Una oidable S uc u es o Bounded Pa h-Wid h
3-Decomposi ion Conjec u e
E e y connec ed cubic g aph has a
3-decomposi ion.
Fou Colou Theo em
E e y plana g aph is 4-colou able.
Conjec u e
E e y g aph in Gsa is ies p ope y π.
Ques ion:
Does e e y g aph in Go pa h-wid h a mos kcon ain a subg aph in U?
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 16 / 25
Finding Una oidable S uc u es o Bounded Pa h-Wid h
3-Decomposi ion Conjec u e
E e y connec ed cubic g aph has a
3-decomposi ion.
Fou Colou Theo em
E e y plana g aph is 4-colou able.
Conjec u e
E e y cubic g aph sa is ies p ope y π.
Ques ion:
Does e e y cubic g aph o pa h-wid h a mos kcon ain a subg aph in U?
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 16 / 25
Answe ing he Ques ion
Q: Does e e y cubic g aph o pa h-wid h a mos 3con ain a ?
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 17 / 25
Answe ing he Ques ion
Q: Does e e y cubic g aph o pa h-wid h a mos 3con ain a ?
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 17 / 25
Answe ing he Ques ion
Q: Does e e y cubic g aph o pa h-wid h a mos 3con ain a ?
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 17 / 25
Answe ing he Ques ion
Q: Does e e y cubic g aph o pa h-wid h a mos 3con ain a ?
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 17 / 25
Answe ing he Ques ion
Q: Does e e y cubic g aph o pa h-wid h a mos 3con ain a ?
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 17 / 25
Answe ing he Ques ion
Q: Does e e y cubic g aph o pa h-wid h a mos 3con ain a ?
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 17 / 25
Answe ing he Ques ion
Q: Does e e y cubic g aph o pa h-wid h a mos 3con ain a ?
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 17 / 25
Answe ing he Ques ion
Q: Does e e y cubic g aph o pa h-wid h a mos 3con ain a ?
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 17 / 25
Answe ing he Ques ion
Q: Does e e y cubic g aph o pa h-wid h a mos 3con ain a ?
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 17 / 25
Answe ing he Ques ion
Q: Does e e y cubic g aph o pa h-wid h a mos 3con ain a ?
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 17 / 25
Answe ing he Ques ion
Q: Does e e y cubic g aph o pa h-wid h a mos 3con ain a ?
A: No!
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 17 / 25
Answe ing he Ques ion
Q: Does e e y cubic g aph o pa h-wid h a mos 3con ain a o a ∆?
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 17 / 25
De eloping an Algo i hm
de FindS uc u es(U,k):
Ini ialise a queue Qwi h Ek+1
while Q=∅do
G←Q.dequeue()
o each ib an e ex u∈Gdo
o each choice o edges Fa udo
G′←G+F+ ,uis dulled
i G′con ains a subg aph in U hen con inue
i G′yields a coun e example H hen e u n H
Q.append(G′)
Q=G
′
=
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 18 / 25
De eloping an Algo i hm
de FindS uc u es(U,k):
Ini ialise a queue Qwi h Ek+1
while Q=∅do
G←Q.dequeue()
o each ib an e ex u∈Gdo
o each choice o edges Fa udo
G′←G+F+ ,uis dulled
i G′con ains a subg aph in U hen con inue
i G′yields a coun e example H hen e u n H
Q.append(G′)
Q=G
′
=
u
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 18 / 25
De eloping an Algo i hm
de FindS uc u es(U,k):
Ini ialise a queue Qwi h Ek+1
while Q=∅do
G←Q.dequeue()
o each ib an e ex u∈Gdo
o each choice o edges Fa udo
G′←G+F+ ,uis dulled
i G′con ains a subg aph in U hen con inue
i G′yields a coun e example H hen e u n H
Q.append(G′)
Q=G
′
=
u
F
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 18 / 25
De eloping an Algo i hm
de FindS uc u es(U,k):
Ini ialise a queue Qwi h Ek+1
while Q=∅do
G←Q.dequeue()
o each ib an e ex u∈Gdo
o each choice o edges Fa udo
G′←G+F+ ,uis dulled
i G′con ains a subg aph in U hen con inue
i G′yields a coun e example H hen e u n H
Q.append(G′)
Q=G
′
=
u
F
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 18 / 25
De eloping an Algo i hm
de FindS uc u es(U,k):
Ini ialise a queue Qwi h Ek+1
while Q=∅do
G←Q.dequeue()
o each ib an e ex u∈Gdo
o each choice o edges Fa udo
G′←G+F+ ,uis dulled
i G′con ains a subg aph in U hen con inue
i G′yields a coun e example H hen e u n H
Q.append(G′)
Q=G
′
=
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 18 / 25
De eloping an Algo i hm
de FindS uc u es(U,k):
Ini ialise a queue Qwi h Ek+1
while Q=∅do
G←Q.dequeue()
o each ib an e ex u∈Gdo
o each choice o edges Fa udo
G′←G+F+ ,uis dulled
i G′con ains a subg aph in U hen con inue
i G′yields a coun e example H hen e u n H
Q.append(G′)
Q=G
′
=
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 18 / 25
De eloping an Algo i hm
de FindS uc u es(U,k):
Ini ialise a queue Qwi h Ek+1
while Q=∅do
G←Q.dequeue()
o each ib an e ex u∈Gdo
o each choice o edges Fa udo
G′←G+F+ ,uis dulled
i G′con ains a subg aph in U hen con inue
i G′yields a coun e example H hen e u n H
Q.append(G′)
Q=G′=
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 18 / 25
De eloping an Algo i hm
de FindS uc u es(U,k):
Ini ialise a queue Qwi h Ek+1
while Q=∅do
G←Q.dequeue()
o each ib an e ex u∈Gdo
o each choice o edges Fa udo
G′←G+F+ ,uis dulled
i G′con ains a subg aph in U hen con inue
i G′yields a coun e example H hen e u n H
Q.append(G′)
Q=G′=
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 18 / 25
De eloping an Algo i hm
de FindS uc u es(U,k):
Ini ialise a queue Qwi h Ek+1
while Q=∅do
G←Q.dequeue()
o each ib an e ex u∈Gdo
o each choice o edges Fa udo
G′←G+F+ ,uis dulled
i G′con ains a subg aph in U hen con inue
i G′yields a coun e example H hen e u n H
Q.append(G′)
Q=G′=
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 18 / 25
De eloping an Algo i hm
de FindS uc u es(U,k):
Ini ialise a queue Qwi h Ek+1
while Q=∅do
G←Q.dequeue()
o each ib an e ex u∈Gdo
o each choice o edges Fa udo
G′←G+F+ ,uis dulled
i G′con ains a subg aph in U hen con inue
i G′yields a coun e example H hen e u n H
Q.append(G′)
Q=
G
′
=
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 18 / 25
How Slow Is This Ac ually?
Example: 5 g aphs.
Algo i hm: 45 g aphs.
x4
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 19 / 25
How Slow Is This Ac ually?
Example: 5 g aphs.
Algo i hm:
45 g aphs.
x4
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 19 / 25
How Slow Is This Ac ually?
Example: 5 g aphs.
Algo i hm:
45 g aphs.
x4
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 19 / 25
How Slow Is This Ac ually?
Example: 5 g aphs.
Algo i hm:
45 g aphs.
x4
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 19 / 25
How Slow Is This Ac ually?
Example: 5 g aphs.
Algo i hm: 45 g aphs.
x4
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 19 / 25
Teaching he Algo i hm o Recognise Symme ies
De ini ion
A ib an au omo phism φo a g aph Gis
▶an au omo phism φ
▶ ha maps 7→ and 7→
Using ib an au omo phisms
▶ o each ib an e ex u∈Gdo
▶ o each choice o edges Fa udo
x4
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 20 / 25
Teaching he Algo i hm o Recognise Symme ies
De ini ion
A ib an au omo phism φo a g aph Gis
▶an au omo phism φ
▶ ha maps 7→ and 7→
Using ib an au omo phisms
▶ o each ib an e ex u∈Gdo
▶ o each choice o edges Fa udo
x4
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 20 / 25
Teaching he Algo i hm o Recognise Symme ies
De ini ion
A ib an au omo phism φo a g aph Gis
▶an au omo phism φ
▶ ha maps 7→ and 7→
Using ib an au omo phisms
▶ o each ib an e ex u∈Gdo
▶ o each choice o edges Fa udo x4
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 20 / 25
Teaching he Algo i hm o Recognise Symme ies
De ini ion
A ib an au omo phism φo a g aph Gis
▶an au omo phism φ
▶ ha maps 7→ and 7→
Using ib an au omo phisms
▶ o each ib an e ex u∈Gdo
▶ o each choice o edges Fa udo x4
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 20 / 25
Teaching he Algo i hm o Recognise Symme ies
De ini ion
A ib an au omo phism φo a g aph Gis
▶an au omo phism φ
▶ ha maps 7→ and 7→
Using ib an au omo phisms
▶ o each ib an e ex u∈Gdo
▶ o each choice o edges Fa udo x4
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 20 / 25
Teaching he Algo i hm o Recognise Symme ies
De ini ion
A ib an au omo phism φo a g aph Gis
▶an au omo phism φ
▶ ha maps 7→ and 7→
Using ib an au omo phisms
▶ o each ib an e ex u∈Gdo
▶ o each choice o edges Fa udo x4
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 20 / 25
Teaching he Algo i hm o Recognise Symme ies
De ini ion
A ib an au omo phism φo a g aph Gis
▶an au omo phism φ
▶ ha maps 7→ and 7→
Using ib an au omo phisms
▶ o each ib an e ex u∈Gdo
▶ o each choice o edges Fa udo x4
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 20 / 25
Teaching he Algo i hm o Recognise Symme ies
De ini ion
A ib an au omo phism φo a g aph Gis
▶an au omo phism φ
▶ ha maps 7→ and 7→
Using ib an au omo phisms
▶ o each ib an e ex u∈Gdo
▶ o each choice o edges Fa udo x4
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 20 / 25
Does I E en Te mina e?
▶I a coun e example exis s, hen he algo i hm inds (a smalles ) one.
▶O he wise, we migh be in ouble.
Fo example, le Gcon ain he ollowing g aphs:
We can cons uc hese as ollows:
The iangle appea s a bi a ily la e!
Lemma ([BH20])
In gene al, de e mining whe he Uis una oidable o Gis undecidable.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 21 / 25
Does I E en Te mina e?
▶I a coun e example exis s, hen he algo i hm inds (a smalles ) one.
▶O he wise, we migh be in ouble.
Fo example, le Gcon ain he ollowing g aphs:
We can cons uc hese as ollows:
The iangle appea s a bi a ily la e!
Lemma ([BH20])
In gene al, de e mining whe he Uis una oidable o Gis undecidable.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 21 / 25
Does I E en Te mina e?
▶I a coun e example exis s, hen he algo i hm inds (a smalles ) one.
▶O he wise, we migh be in ouble.
Fo example, le Gcon ain he ollowing g aphs:
We can cons uc hese as ollows:
The iangle appea s a bi a ily la e!
Lemma ([BH20])
In gene al, de e mining whe he Uis una oidable o Gis undecidable.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 21 / 25
Does I E en Te mina e?
▶I a coun e example exis s, hen he algo i hm inds (a smalles ) one.
▶O he wise, we migh be in ouble.
Fo example, le Gcon ain he ollowing g aphs:
We can cons uc hese as ollows:
The iangle appea s a bi a ily la e!
Lemma ([BH20])
In gene al, de e mining whe he Uis una oidable o Gis undecidable.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 21 / 25
Does I E en Te mina e?
▶I a coun e example exis s, hen he algo i hm inds (a smalles ) one.
▶O he wise, we migh be in ouble.
Fo example, le Gcon ain he ollowing g aphs:
We can cons uc hese as ollows:
The iangle appea s a bi a ily la e!
Lemma ([BH20])
In gene al, de e mining whe he Uis una oidable o Gis undecidable.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 21 / 25
Does I E en Te mina e?
▶I a coun e example exis s, hen he algo i hm inds (a smalles ) one.
▶O he wise, we migh be in ouble.
Fo example, le Gcon ain he ollowing g aphs:
We can cons uc hese as ollows:
The iangle appea s a bi a ily la e!
Lemma ([BH20])
In gene al, de e mining whe he Uis una oidable o Gis undecidable.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 21 / 25
Does I E en Te mina e?
▶I a coun e example exis s, hen he algo i hm inds (a smalles ) one.
▶O he wise, we migh be in ouble.
Fo example, le Gcon ain he ollowing g aphs:
We can cons uc hese as ollows:
The iangle appea s a bi a ily la e!
Lemma ([BH20])
In gene al, de e mining whe he Uis una oidable o Gis undecidable.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 21 / 25
Does I E en Te mina e?
▶I a coun e example exis s, hen he algo i hm inds (a smalles ) one.
▶O he wise, we migh be in ouble.
Fo example, le Gcon ain he ollowing g aphs:
We can cons uc hese as ollows:
The iangle appea s a bi a ily la e!
Lemma ([BH20])
In gene al, de e mining whe he Uis una oidable o Gis undecidable.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 21 / 25
Does I E en Te mina e?
▶I a coun e example exis s, hen he algo i hm inds (a smalles ) one.
▶O he wise, we migh be in ouble.
Fo example, le Gcon ain he ollowing g aphs:
We can cons uc hese as ollows:
The iangle appea s a bi a ily la e!
Lemma ([BH20])
In gene al, de e mining whe he Uis una oidable o Gis undecidable.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 21 / 25
Does I E en Te mina e?
▶I a coun e example exis s, hen he algo i hm inds (a smalles ) one.
▶O he wise, we migh be in ouble.
Fo example, le Gcon ain he ollowing g aphs:
We can cons uc hese as ollows:
The iangle appea s a bi a ily la e!
Lemma ([BH20])
In gene al, de e mining whe he Uis una oidable o Gis undecidable.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 21 / 25
Does I E en Te mina e?
▶I a coun e example exis s, hen he algo i hm inds (a smalles ) one.
▶O he wise, we migh be in ouble.
Fo example, le Gcon ain he ollowing g aphs:
We can cons uc hese as ollows:
The iangle appea s a bi a ily la e!
Lemma ([BH20])
In gene al, de e mining whe he Uis una oidable o Gis undecidable.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 21 / 25
Does I E en Te mina e?
▶I a coun e example exis s, hen he algo i hm inds (a smalles ) one.
▶O he wise, we migh be in ouble.
Fo example, le Gcon ain he ollowing g aphs:
We can cons uc hese as ollows:
The iangle appea s a bi a ily la e!
Lemma ([BH20])
In gene al, de e mining whe he Uis una oidable o Gis undecidable.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 21 / 25
Does I E en Te mina e?
▶I a coun e example exis s, hen he algo i hm inds (a smalles ) one.
▶O he wise, we migh be in ouble.
Fo example, le Gcon ain he ollowing g aphs:
We can cons uc hese as ollows:
The iangle appea s a bi a ily la e!
Lemma ([BH20])
In gene al, de e mining whe he Uis una oidable o Gis undecidable.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 21 / 25
Does I E en Te mina e?
▶I a coun e example exis s, hen he algo i hm inds (a smalles ) one.
▶O he wise, we migh be in ouble.
Fo example, le Gcon ain he ollowing g aphs:
We can cons uc hese as ollows:
The iangle appea s a bi a ily la e!
Lemma ([BH20])
In gene al, de e mining whe he Uis una oidable o Gis undecidable.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 21 / 25
Does I E en Te mina e?
▶I a coun e example exis s, hen he algo i hm inds (a smalles ) one.
▶O he wise, we migh be in ouble.
Fo example, le Gcon ain he ollowing g aphs:
We can cons uc hese as ollows:
The iangle appea s a bi a ily la e!
Lemma ([BH20])
In gene al, de e mining whe he Uis una oidable o Gis undecidable.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 21 / 25
Does I E en Te mina e?
▶I a coun e example exis s, hen he algo i hm inds (a smalles ) one.
▶O he wise, we migh be in ouble.
Fo example, le Gcon ain he ollowing g aphs:
We can cons uc hese as ollows:
The iangle appea s a bi a ily la e!
Lemma ([BH20])
In gene al, de e mining whe he Uis una oidable o Gis undecidable.
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 21 / 25
The Good News
Theo em ([BH20])
The algo i hm can be modi ied such ha i e mina es o he cubic case i
Uis a ini e se o connec ed g aphs.
Idea
▶Disca d mo e g aphs.
▶Take ca e ha no all coun e examples a e los .
This is small!
Oli e Bach le Algo i hmic Ce i ica ion o G aph S uc u es 30.03.2023 22 / 25
