Résumé: For a graph G, OALG asks whether or not an input graph H together with a partial map g :S?G, SV(H), admits a homomorphism f :H?G such that f|S=g. We show that for connected graphs G1, G2, OAL G1×G2 is in P if G1 and G2 are trees and NP-complete otherwise.

Langue: Anglais