Finding Structure(s) in Graphs of Bounded Path-Width
Full text
Finding Structure(s) in Graphs of Bounded Path-Width Oliver Bachtler and Irene Heinrich Department of Mathematics TU Kaiserslautern and Department of Mathematics TU Darmstadt Future Research in Combinatorial Optimization, 2022
Motivation Conjecture Every graph in Gsatisfies property π. Now: Find such “tame” structures and collect them in a set U. Want: Every cubic graph of path-width at most khas a subgraph in U. ⇒The conjecture holds for all cubic graphs of path-width at most k. Question: Does every cubic graph of path-width at most kcontain a subgraph in U? O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 1 / 14
Motivation Conjecture Every graph in Gsatisfies property π. Now: Find such “tame” structures and collect them in a set U. Want: Every cubic graph of path-width at most khas a subgraph in U. ⇒The conjecture holds for all cubic graphs of path-width at most k. Question: Does every cubic graph of path-width at most kcontain a subgraph in U? O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 1 / 14
Motivation Conjecture Every graph in G cubic graph satisfies property π. Now: Find such “tame” structures and collect them in a set U. Want: Every cubic graph of path-width at most khas a subgraph in U. ⇒The conjecture holds for all cubic graphs of path-width at most k. Question: Does every cubic graph of path-width at most kcontain a subgraph in U? O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 1 / 14
Motivation Conjecture Every graph in G cubic graph satisfies property π. Now: Find such “tame” structures and collect them in a set U. Want: Every cubic graph of path-width at most khas a subgraph in U. ⇒The conjecture holds for all cubic graphs of path-width at most k. Question: Does every cubic graph of path-width at most kcontain a subgraph in U? O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 1 / 14
Motivation Conjecture Every graph in G cubic graph satisfies property π. Now: Find such “tame” structures and collect them in a set U. Want: Every cubic graph of path-width at most khas a subgraph in U. ⇒The conjecture holds for all cubic graphs of path-width at most k. Question: Does every cubic graph of path-width at most kcontain a subgraph in U? O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 1 / 14
Motivation Conjecture Every graph in G cubic graph satisfies property π. Now: Find such “tame” structures and collect them in a set U. Want: Every cubic graph of path-width at most khas a subgraph in U. ⇒The conjecture holds for all cubic graphs of path-width at most k. Question: Does every cubic graph of path-width at most kcontain a subgraph in U? O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 1 / 14
Motivation Conjecture Every graph in G cubic graph satisfies property π. Now: Find such “tame” structures and collect them in a set U. Want: Every cubic graph of path-width at most khas a subgraph in U. ⇒The conjecture holds for all cubic graphs of path-width at most k. Question: Does every cubic graph of path-width at most kcontain a subgraph in U? O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 1 / 14
Motivation Conjecture Every graph in G cubic graph satisfies property π. Now: Find such “tame” structures and collect them in a set U. Want: Every cubic graph of path-width at most khas a subgraph in U. ⇒The conjecture holds for all cubic graphs of path-width at most k. Question: Does every cubic graph of path-width at most kcontain a subgraph in U? O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 1 / 14
Answering the Question Q: Does every cubic graph of path-width at most 3contain a K2,3? O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 3 / 14
Answering the Question Q: Does every cubic graph of path-width at most 3contain a K2,3? O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 3 / 14
Answering the Question Q: Does every cubic graph of path-width at most 3contain a K2,3? O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 3 / 14
Answering the Question Q: Does every cubic graph of path-width at most 3contain a K2,3? O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 3 / 14
Answering the Question Q: Does every cubic graph of path-width at most 3contain a K2,3? O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 3 / 14
Answering the Question Q: Does every cubic graph of path-width at most 3contain a K2,3? O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 3 / 14
Answering the Question Q: Does every cubic graph of path-width at most 3contain a K2,3? O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 3 / 14
Answering the Question Q: Does every cubic graph of path-width at most 3contain a K2,3? O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 3 / 14
Answering the Question Q: Does every cubic graph of path-width at most 3contain a K2,3? O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 3 / 14
Answering the Question Q: Does every cubic graph of path-width at most 3contain a K2,3? O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 3 / 14
Answering the Question Q: Does every cubic graph of path-width at most 3contain a K2,3? A: No! O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 3 / 14
Answering the Question Q: Does every cubic graph of path-width at most 3contain a K2,3or a ∆? O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 3 / 14
Answering the Question Q: Does every cubic graph of path-width at most 3contain a K2,3or a ∆? O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 3 / 14
Answering the Question Q: Does every cubic graph of path-width at most 3contain a K2,3or a ∆? O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 3 / 14
Answering the Question Q: Does every cubic graph of path-width at most 3contain a K2,3or a ∆? O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 3 / 14
Answering the Question Q: Does every cubic graph of path-width at most 3contain a K2,3or a ∆? A: Yes! O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 3 / 14
Outline Obtaining an Algorithm Speeding It Up Does It Even Terminate? O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 4 / 14
Obtaining an Algorithm O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 5 / 14
Developing an algorithm def FindStructures(G,U,k): Initialise a queue Qwith Ek+1 while Q=∅do G←Q.dequeue() foreach vibrant vertex u∈Gdo foreach choice of edges Fat udo G′←G+F+v,uis dulled if G′contains a subgraph in Uthen continue if G′contains a counterexample Hthen return H Q.append(G′) G ′ = O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 6 / 14
Developing an algorithm def FindStructures(G,U,k): Initialise a queue Qwith Ek+1 while Q=∅do G←Q.dequeue() foreach vibrant vertex u∈Gdo foreach choice of edges Fat udo G′←G+F+v,uis dulled if G′contains a subgraph in Uthen continue if G′contains a counterexample Hthen return H Q.append(G′) Q= G ′ = O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 6 / 14
Developing an algorithm def FindStructures(G,U,k): Initialise a queue Qwith Ek+1 while Q=∅do G←Q.dequeue() foreach vibrant vertex u∈Gdo foreach choice of edges Fat udo G′←G+F+v,uis dulled if G′contains a subgraph in Uthen continue if G′contains a counterexample Hthen return H Q.append(G′) Q=G′= O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 6 / 14
Developing an algorithm def FindStructures(G,U,k): Initialise a queue Qwith Ek+1 while Q=∅do G←Q.dequeue() foreach vibrant vertex u∈Gdo foreach choice of edges Fat udo G′←G+F+v,uis dulled if G′contains a subgraph in Uthen continue if G′contains a counterexample Hthen return H Q.append(G′) Q=G′= O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 6 / 14
Developing an algorithm def FindStructures(G,U,k): Initialise a queue Qwith Ek+1 while Q=∅do G←Q.dequeue() foreach vibrant vertex u∈Gdo foreach choice of edges Fat udo G′←G+F+v,uis dulled if G′contains a subgraph in Uthen continue if G′contains a counterexample Hthen return H Q.append(G′) Q=G′= O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 6 / 14
Developing an algorithm def FindStructures(G,U,k): Initialise a queue Qwith Ek+1 while Q=∅do G←Q.dequeue() foreach vibrant vertex u∈Gdo foreach choice of edges Fat udo G′←G+F+v,uis dulled if G′contains a subgraph in Uthen continue if G′contains a counterexample Hthen return H Q.append(G′) Q= G ′ = O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 6 / 14
Developing an algorithm def FindStructures(G,U,k): Initialise a queue Qwith Ek+1 while Q=∅do G←Q.dequeue() foreach vibrant vertex u∈Gdo foreach choice of edges Fat udo G′←G+F+v,uis dulled if G′contains a subgraph in Uthen continue if G′contains a counterexample Hthen return H Q.append(G′) Q=G ′ = O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 6 / 14
Developing an algorithm def FindStructures(G,U,k): Initialise a queue Qwith Ek+1 while Q=∅do G←Q.dequeue() foreach vibrant vertex u∈Gdo foreach choice of edges Fat udo G′←G+F+v,uis dulled if G′contains a subgraph in Uthen continue if G′contains a counterexample Hthen return H Q.append(G′) Q=G ′ = u O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 6 / 14
Developing an algorithm def FindStructures(G,U,k): Initialise a queue Qwith Ek+1 while Q=∅do G←Q.dequeue() foreach vibrant vertex u∈Gdo foreach choice of edges Fat udo G′←G+F+v,uis dulled if G′contains a subgraph in Uthen continue if G′contains a counterexample Hthen return H Q.append(G′) Q=G ′ = u F O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 6 / 14
Speeding It Up O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 7 / 14
How slow is this actually? Example: 5 graphs. Algorithm: 45 graphs. x4 O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 8 / 14
How slow is this actually? Example: 5 graphs. Algorithm: 45 graphs. x4 O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 8 / 14
Teaching the algorithm to recognise symmetries Definition Avibrant automorphism φof a graph Gis ▶an automorphism φ ▶that maps 7→ and 7→ Using vibrant isomorphisms ▶foreach vibrant vertex u∈Gdo ▶foreach choice of edges Fat udo x4 O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 9 / 14
Teaching the algorithm to recognise symmetries Definition Avibrant automorphism φof a graph Gis ▶an automorphism φ ▶that maps 7→ and 7→ Using vibrant isomorphisms ▶foreach vibrant vertex u∈Gdo ▶foreach choice of edges Fat udo x4 O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 9 / 14
Teaching the algorithm to recognise symmetries Definition Avibrant automorphism φof a graph Gis ▶an automorphism φ ▶that maps 7→ and 7→ Using vibrant isomorphisms ▶foreach vibrant vertex u∈Gdo ▶foreach choice of edges Fat udo x4 O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 9 / 14
Teaching the algorithm to recognise symmetries Definition Avibrant automorphism φof a graph Gis ▶an automorphism φ ▶that maps 7→ and 7→ Using vibrant isomorphisms ▶foreach vibrant vertex u∈Gdo ▶foreach choice of edges Fat udo x4 O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 9 / 14
Teaching the algorithm to recognise symmetries Definition Avibrant automorphism φof a graph Gis ▶an automorphism φ ▶that maps 7→ and 7→ Using vibrant isomorphisms ▶foreach vibrant vertex u∈Gdo ▶foreach choice of edges Fat udo x4 O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 9 / 14
Teaching the algorithm to recognise symmetries Definition Avibrant automorphism φof a graph Gis ▶an automorphism φ ▶that maps 7→ and 7→ Using vibrant isomorphisms ▶foreach vibrant vertex u∈Gdo ▶foreach choice of edges Fat udo x4 O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 9 / 14
Teaching the algorithm to recognise symmetries Definition Avibrant automorphism φof a graph Gis ▶an automorphism φ ▶that maps 7→ and 7→ Using vibrant isomorphisms ▶foreach vibrant vertex u∈Gdo ▶foreach choice of edges Fat udo x4 O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 9 / 14
Teaching the algorithm to recognise symmetries Definition Avibrant automorphism φof a graph Gis ▶an automorphism φ ▶that maps 7→ and 7→ Using vibrant isomorphisms ▶foreach vibrant vertex u∈Gdo ▶foreach choice of edges Fat udo x4 O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 9 / 14
Teaching the algorithm to recognise symmetries Definition Avibrant automorphism φof a graph Gis ▶an automorphism φ ▶that maps 7→ and 7→ Using vibrant isomorphisms ▶foreach vibrant vertex u∈Gdo ▶foreach choice of edges Fat udo x4 O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 9 / 14
Teaching the algorithm to recognise symmetries Definition Avibrant automorphism φof a graph Gis ▶an automorphism φ ▶that maps 7→ and 7→ Using vibrant isomorphisms ▶foreach vibrant vertex u∈Gdo ▶foreach choice of edges Fat udo x4 O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 9 / 14
What’s the worst that could happen? ▶If a counterexample exists, then the algorithm finds (a smallest) one. ▶Otherwise, we might be in trouble. For example, let Gcontain the following graphs: We can construct these as follows: The triangle appears arbitrarily late! Lemma Determining whether every graph in Ghas a subgraph in Uis undecidable. O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 11 / 14
What’s the worst that could happen? ▶If a counterexample exists, then the algorithm finds (a smallest) one. ▶Otherwise, we might be in trouble. For example, let Gcontain the following graphs: We can construct these as follows: The triangle appears arbitrarily late! Lemma Determining whether every graph in Ghas a subgraph in Uis undecidable. O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 11 / 14
What’s the worst that could happen? ▶If a counterexample exists, then the algorithm finds (a smallest) one. ▶Otherwise, we might be in trouble. For example, let Gcontain the following graphs: We can construct these as follows: The triangle appears arbitrarily late! Lemma Determining whether every graph in Ghas a subgraph in Uis undecidable. O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 11 / 14
What’s the worst that could happen? ▶If a counterexample exists, then the algorithm finds (a smallest) one. ▶Otherwise, we might be in trouble. For example, let Gcontain the following graphs: We can construct these as follows: The triangle appears arbitrarily late! Lemma Determining whether every graph in Ghas a subgraph in Uis undecidable. O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 11 / 14
What’s the worst that could happen? ▶If a counterexample exists, then the algorithm finds (a smallest) one. ▶Otherwise, we might be in trouble. For example, let Gcontain the following graphs: We can construct these as follows: The triangle appears arbitrarily late! Lemma Determining whether every graph in Ghas a subgraph in Uis undecidable. O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 11 / 14
What’s the worst that could happen? ▶If a counterexample exists, then the algorithm finds (a smallest) one. ▶Otherwise, we might be in trouble. For example, let Gcontain the following graphs: We can construct these as follows: The triangle appears arbitrarily late! Lemma Determining whether every graph in Ghas a subgraph in Uis undecidable. O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 11 / 14
What’s the worst that could happen? ▶If a counterexample exists, then the algorithm finds (a smallest) one. ▶Otherwise, we might be in trouble. For example, let Gcontain the following graphs: We can construct these as follows: The triangle appears arbitrarily late! Lemma Determining whether every graph in Ghas a subgraph in Uis undecidable. O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 11 / 14
What’s the worst that could happen? ▶If a counterexample exists, then the algorithm finds (a smallest) one. ▶Otherwise, we might be in trouble. For example, let Gcontain the following graphs: We can construct these as follows: The triangle appears arbitrarily late! Lemma Determining whether every graph in Ghas a subgraph in Uis undecidable. O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 11 / 14
What’s the worst that could happen? ▶If a counterexample exists, then the algorithm finds (a smallest) one. ▶Otherwise, we might be in trouble. For example, let Gcontain the following graphs: We can construct these as follows: The triangle appears arbitrarily late! Lemma Determining whether every graph in Ghas a subgraph in Uis undecidable. O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 11 / 14
What’s the worst that could happen? ▶If a counterexample exists, then the algorithm finds (a smallest) one. ▶Otherwise, we might be in trouble. For example, let Gcontain the following graphs: We can construct these as follows: The triangle appears arbitrarily late! Lemma Determining whether every graph in Ghas a subgraph in Uis undecidable. O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 11 / 14
What’s the worst that could happen? ▶If a counterexample exists, then the algorithm finds (a smallest) one. ▶Otherwise, we might be in trouble. For example, let Gcontain the following graphs: We can construct these as follows: The triangle appears arbitrarily late! Lemma Determining whether every graph in Ghas a subgraph in Uis undecidable. O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 11 / 14
What’s the worst that could happen? ▶If a counterexample exists, then the algorithm finds (a smallest) one. ▶Otherwise, we might be in trouble. For example, let Gcontain the following graphs: We can construct these as follows: The triangle appears arbitrarily late! Lemma Determining whether every graph in Ghas a subgraph in Uis undecidable. O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 11 / 14
What’s the worst that could happen? ▶If a counterexample exists, then the algorithm finds (a smallest) one. ▶Otherwise, we might be in trouble. For example, let Gcontain the following graphs: We can construct these as follows: The triangle appears arbitrarily late! Lemma Determining whether every graph in Ghas a subgraph in Uis undecidable. O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 11 / 14
What’s the worst that could happen? ▶If a counterexample exists, then the algorithm finds (a smallest) one. ▶Otherwise, we might be in trouble. For example, let Gcontain the following graphs: We can construct these as follows: The triangle appears arbitrarily late! Lemma Determining whether every graph in Ghas a subgraph in Uis undecidable. O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 11 / 14
What’s the worst that could happen? ▶If a counterexample exists, then the algorithm finds (a smallest) one. ▶Otherwise, we might be in trouble. For example, let Gcontain the following graphs: We can construct these as follows: The triangle appears arbitrarily late! Lemma Determining whether every graph in Ghas a subgraph in Uis undecidable. O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 11 / 14
The good news Theorem The algorithm can be modified such that it terminates for the cubic case if Ucontains connected graphs. Idea. ▶Discard more graphs. ▶Take care that not all counterexamples are lost. This is small! O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 12 / 14
The good news Theorem The algorithm can be modified such that it terminates for the cubic case if Ucontains connected graphs. Idea. ▶Discard more graphs. ▶Take care that not all counterexamples are lost. This is small! O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 12 / 14
The good news Theorem The algorithm can be modified such that it terminates for the cubic case if Ucontains connected graphs. Idea. ▶Discard more graphs. ▶Take care that not all counterexamples are lost. This is small! O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 12 / 14
The good news Theorem The algorithm can be modified such that it terminates for the cubic case if Ucontains connected graphs. Idea. ▶Discard more graphs. ▶Take care that not all counterexamples are lost. This is small! O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 12 / 14
The good news Theorem The algorithm can be modified such that it terminates for the cubic case if Ucontains connected graphs. Idea. ▶Discard more graphs. ▶Take care that not all counterexamples are lost. This is small! O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 12 / 14
The good news Theorem The algorithm can be modified such that it terminates for the cubic case if Ucontains connected graphs. Idea. ▶Discard more graphs. ▶Take care that not all counterexamples are lost. This is small! O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 12 / 14
The good news Theorem The algorithm can be modified such that it terminates for the cubic case if Ucontains connected graphs. Idea. ▶Discard more graphs. ▶Take care that not all counterexamples are lost. This is small! O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 12 / 14
The good news Theorem The algorithm can be modified such that it terminates for the cubic case if Ucontains connected graphs. Idea. ▶Discard more graphs. ▶Take care that not all counterexamples are lost. This is small! O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 12 / 14
Even better news Theorem The algorithm can be modified such that it terminates when ▶Gis “locally certifiable”, ▶Ghas bounded maximum degree, and ▶Uis a finite set of connected graphs. O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 13 / 14
Even better news Theorem The algorithm can be modified such that it terminates when ▶Gis “locally certifiable”, ▶Ghas bounded maximum degree, and ▶Uis a finite set of connected graphs. O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 13 / 14
Summary We have: ▶developed an algorithm that checks whether every graph in Gof path-width at most kcontain a subgraph in U. ▶incorporated symmetries to speed up the algorithm, and ▶showed that we can achieve termination in special cases. For the sceptics: a formal version is in the arXiv. Contact: [email protected] O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 14 / 14
Summary We have: ▶developed an algorithm that checks whether every graph in Gof path-width at most kcontain a subgraph in U. ▶incorporated symmetries to speed up the algorithm, and ▶showed that we can achieve termination in special cases. For the sceptics: a formal version is in the arXiv. Contact: [email protected] O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 14 / 14
Summary We have: ▶developed an algorithm that checks whether every graph in Gof path-width at most kcontain a subgraph in U. ▶incorporated symmetries to speed up the algorithm, and ▶showed that we can achieve termination in special cases. For the sceptics: a formal version is in the arXiv. Contact: [email protected] O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 14 / 14
Fortune telling: someone will ask about . . . PCP x1=0,x2=01,x3=110 y1=100,y2=00,y3=11 (1,2,3): 001110 1000011 (3,2,3,1): 110011100 110011100 k3 3 4 5 5 6 6 7 U U3U4U4U4U5U5U6U6 Result K3,3None None Petersen None Heawood None None Base 6 5 81 12484 3841 – – – Cubic 3 2 3 7 5 15 9 19 O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 1 / 2
References lit O. Bachtler and I. Heinrich Finding Structure(s) in Graphs FRICO 2022 2 / 2