Enumerating connected subgraphs
As explained in enumerating all connected induced subgraphs (on TCS.SE), there is an algorithm whose running time is polynomial in the number of connected subgraphs.  Therefore, if you know that the number of connected subgraphs is polynomial in the input size, there is an algorithm that is polynomial in the size of the input.  The polynomial might be fairly high degree, so I don't know whether the algorithm will be efficient in practice, but you could try it out and see.

See also https://stackoverflow.com/q/15658245/781723.