complexity of games with just doors and keys

Question

(This essentially copies my unaswnered question
from math.stackexchange.com/questions/275685)

I was reading http://arxiv.org/abs/1201.4995, and I thought
back to a game I used to play, which is close to being covered
by Metatheorem 3 (on page 5), but does not have one-way paths.

What is the computational complexity of the following problem?

For an undirected graph G whose vertices have non-negative integer weights,
for vertices s and t, is there a path from s to t such that the sum of the weights
of the vertices (including s) reached at any given point along it is always
greater than the number of distinct edges traversed to get to that point?
(The vertices are not counted with multiplicity either.)

Answer 1

If I understand your question correctly, by path you mean that we build up a tree starting from s by always taking an edge adjacent to our current tree. This problem is NP-complete, the reduction is from SAT.

The main part of the graph will consist of n cycles of length four attached to each other at vertices s=v0, v1, v2, .., vn. So from s we have two paths of length two to v1, from v1 two paths to v2 and so on. From vn there will be a path of length N+1 to t. We will have only enough weights to use one of each pair of paths and depending on which path we use, the value of the variable xi will be true or false. The weight in s is N+2n, where N is some big number.

Each clause is represented by an additional vertex that is connected by a path of length N to the center vertex of the path that corresponds to its literals and it has value N+epsilon (I know we need integers, but we can multiply up and replace each edge by 1/epsilon edges), where 1/epsilon is the number of clauses. So we have to visit every clause-vertex to get to t.