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) $


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$.

  • $\begingroup$ What properties does $g$ have? Very few non-zero values? Symmetric? Also, in the paper, the graphs seem to always be acyclic. Will it always be the case? $\endgroup$ – xavierm02 Jun 24 '17 at 9:27
  • $\begingroup$ @xavierm02 $g$ will have very few non-zero values, also $g(e_1,e_2)<f(e_1)$ and $g(e_1,e_2)<f(e_2)$. I am trying to fit the curves to a closed polygon, so the graph actually has cycles, and I am technically trying to find the shortest cycle. But there are certain vertices that I am confident that are on the shortest cycle. So I am trying to find the shortest path from those vertices to themselves $\endgroup$ – Hashimoto Jun 24 '17 at 19:19

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:

enter image description here

(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.

| cite | improve this answer | |
  • $\begingroup$ I asked on the TeX site why the rightmost labels aren't placed properly: tex.stackexchange.com/questions/376550/… $\endgroup$ – xavierm02 Jun 24 '17 at 2:25
  • $\begingroup$ Thanks for your answer. You saved me from investing too much on this problem. Would you happen to have any suggestions about heuristics for this problem, given the updates that I made to the question? $\endgroup$ – Hashimoto Jun 24 '17 at 6:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.