School of Computer Science PGR Seminar Joseph Loughney

Joseph Loughney will present Symmetry Breaking in the Subgraph Isomorphism Problem, and Why It Isn't Straightforward

Abstract: The Subgraph Isomorphism Problem (SIP) asks whether a given graph occurs within another. Despite being theoretically difficult, SIP can be solved quickly in practice using constraint techniques. In principle, we should be able to make use of symmetries in the input graphs to further speed up solving; however, in practice, symmetry elimination techniques interfere heavily with other finely-tuned parts of the solving process. In this talk we will examine why this is the case and explore strategies that can reduce or avoid this problem altogether.

Short Bio: I am Joe, a final year PhD student at St Andrews supervised by Ruth Hoffmann and Mun See Chang. My research is focused on using properties from graph theory and group theory to improve the efficiency of algorithms which solve theoretically difficult combinatorial search problems.