Seminar 2019-04-11

Date: 2019-04-11​
Time: 11:00-12:00
Speaker: ​​Ciaran McCreesh, University of Glasgow
Title: Are "Hard" Subgraph Problems Hard?​
 

Abstract
The subgraph isomorphism problem is to find a small "pattern" graph inside a larger "target" graph, or to prove that the pattern does not exist. In theory, subgraph isomorphism is NP-hard, and is believed to get exponentially harder as the inputs grow. In practice, modern subgraph isomorphism solvers can quickly handle this kind of problem even with graphs involving tens of thousands of vertices, and exponential scaling is unlikely to occur in practice. However, it is possible to construct inputs involving graphs with only a few hundred vertices which do appear to be "really hard". I'll describe what these inputs look like, and discuss the implications for designing and evaluating algorithms and larger systems built upon these systems.

Bio
Ciaran McCreesh is a postdoc at the University of Glasgow, and the lead author of the Glasgow Subgraph Solver. His research covers the design, evaluation, and implementation of practical, exact algorithms for hard problems, particularly those involving graphs. He was awarded the Association for Constraint Programming Doctoral Research Award 2018 for his PhD thesis.