Longest simple walk below a certain weight Given a directed graph G and a starting vertex $v$ and a cutoff weight $w$, I want to find a simple walk with net weight &lt; $w$ that visits as many nodes as possible. Currently, I have a recursive function which is incredibly slow, is there some sort of heuristic function for such a problem?

For my particular purposes, I am looking at superpermutation graphs for k letters, $S_k$, with only 1-edges and 2-edges. $S_k$ is vertex transitive, with each vertex having one 1-edge (weight 0) and one 2-edge (weight 1).
Without the "vertex-transitive" restriction, the problem is NP-hard, by reduction from Hamiltonian path.

Without the "vertex-transitive" or "number of neighbors" restrictions, the reduction is easy: set $w$ equal to the number of vertices minus one, and assign weight 1 to all edges.  To accommodate the restriction on the number of neighbors, replace each node with a network of nodes shaped like two trees connected at their roots; each in-edge connects to a leaf of the first tree, and each out-edge connects to a leaf of the second tree, and put weight 0 on all the tree edges.

I don't know if this reduction can be extended to handle the case of vertex-transitive graphs as well.