What is the best exact algorithm to compute the core of a graph? A graph H is a core if any homomorphism from H to itself is a bijection. A subgraph H of G is a core of G if H is a core and there is a homomorphism from G to H. 
http://en.wikipedia.org/wiki/Core_%28graph_theory%29

Given a graph G, what is the best known exact algorithm to find its core?
Computing the core of a graph is hard: even deciding if a given 3-colourable graph is a core is co-NP-complete, see Hell and Nesetril.  There are settings where core computation can be done efficiently, see Efficient Core Computation in Data Exchange by Georg Gottlob and Alan Nash for a database setting; here some reasonable restrictions on the kinds of constraints in the database schema allow cores to be computed efficiently.

Edit: Other than the Gottlob/Nash work mentioned above, I am not aware of any other attempts to provide efficient algorithms for core computation.  Pointers to any algorithms better than brute force (exact or otherwise) would be welcome.