Shortest Path in a Graph with Interacting Edge Weights

Question

Suppose we have a graph $G = (V,E)$.

Every edge $e \in E$ has a unary cost $f(e) > 0$.

Also, for every two edges $e_1,e_2 \in E$ we have a binary reward function $g(e_1,e_2) \geq 0$.

Given two vertices $s$ and $t$, is it possible to find the path that minimizes the following objective function efficiently?

$ \sum_{e \in \text{Path}} f(e) - \sum_{e_1 \in \text{Path}} \sum_{e_2 \in \text{Path}} g(e_1,e_2) $

---

Update:

According to @xavierm02's answer this problem seems to be NP-hard. But is there any heuristic that can at least partially deal with this? If it helps, this is the context for which I want to use this problem.

This shortest path simply represents a sequence of curves for a piecewise curve fitting as in the paper: http://www.mit.edu/~ibaran/curves/ .

The final goal is to fit a sequence of curves to a bunch of points. As we cannot fit just one curve, we also have to decide where the transitions occur. In this approach, we basically fit every possible curve. Then, we construct a graph, where each curve is associated with an edge, and the points to be fitted are the vertices (not exactly the same as the paper). The weight of each edge is basically its error in the least square fit. We then find the shortest path from the first point, to the last, which in turn tells us the best sequence of curves.

What I am trying to do is to use this reward function to encourage certain curve pairs to be inside the final selected sequence of curves. For example, the ones that are symmetric.

---

Further updates:

$g$ has very few non-zero values, and we can safely assume $g(e_1,e_2)<f(e_1)$ and $g(e_1,e_2)<f(e_2)$. The graph has cycles, and we might have $s=t$.

Answer 1

It's NP-hard.

We reduce 3SAT to your problem (where $f$ is constant). Let $c_1,\dots ,c_m$ be an instance of 3SAT. Let $v_1,\dots,v_n$ be the variable in the clauses. For each clause $c_i$, call $l_{i,j}$ the $j^\text{th}$ literal of $c_i$. Now, build this graph:

(Note that we allow several edges between the two same nodes, but if you don't want to, you can just add dummy nodes)

Now, if we look at paths from $0$ to $n+m$ in this graph, clearly, they will pick a value per variable (true if it picks $v_i$ and false if it picks $\lnot v_i$), and a literal per clause. Set $f:=e\mapsto 1$ to be constant. Now set $g((l,c),l)=1$ and $g(e,e')=0$ in all other cases, i.e. reward taking a literal in a clause that's been made true by the valuation defined by the first $n$ edges. Note that the cost of a path from $0$ to $n+m$ is $\le n$ (or equivalently $=n$) if and only if the initial formula is satisfiable (because the cost due to $f$ is $n+m$ and the reward due to $g$ is the number of satisfied clauses). So the problem "Is there a path of cost $\le n$" is NP-hard.