Graph isomorphism is interesting, in that practical algorithms already exist. It's actually very, very hard to produce difficult instances of the graph isomorph

Graph isomorphism is interesting, in that practical algorithms already exist. It's actually very, very hard to produce difficult instances of the graph isomorphism problem (to be exact, instances where existing algorithms take non-polynomial time). Much of the progress in recent years has come from first finding instances where existing algorithms (in particular, partitioning from Brendan McKay's Nauty) take exponential time, and understanding why.