For a reference concerning this problem, see [Cattell et al, "On computing graph minor obstruction sets", Theor. Comput. Sci. 2000][1].

I think the answer to your specific question is that it's recursively enumerable (one can test all graphs using P to see whether they belong to E) but not recursive (without further information there is no way of knowing that one has found all obstructions).


  [1]: http://dx.doi.org/10.1016/S0304-3975(97)00300-9