3
$\begingroup$

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

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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