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

• Have you tried showing that your problem is NP-hard? – Yuval Filmus Feb 21 at 19:05
• Are you familiar with max/min flow algorithms (ford-fulkerson, etc)? Sounds similar—they might be helpful – Nick Zuber Feb 21 at 22:52
• I’ll look into that – Zachary Hunter Feb 21 at 22:52

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.