Before revision:  For the special case when G is a directed acyclic graph (DAG), we show that Max-IP can be solved in polynomial time - in O(mnd_i) where d_i is the maximum indegree of a vertex in G. In the more general problem IP, the goal is to find a collection of  interesting paths such that these paths form an exact cover of E (hence they are edge-disjoint) and the overall sum of interestingness scores of all paths is maximized.
After revision:  For the special case when G is a directed acyclic graph (DAG), we show that Max-IP can be solved in polynomial time - in O(mnd_i) where d_i is the maximum indegree of a vertex in G. In the more general problem IP, the goal is to find a collection of interesting paths such that the overall sum of interestingness scores of all paths is maximized.