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

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ Have you tried showing that your problem is NP-hard? $\endgroup$ – Yuval Filmus Feb 21 '19 at 19:05
  • $\begingroup$ Are you familiar with max/min flow algorithms (ford-fulkerson, etc)? Sounds similar—they might be helpful $\endgroup$ – Nick Zuber Feb 21 '19 at 22:52
  • $\begingroup$ I’ll look into that $\endgroup$ – Zachary Hunter Feb 21 '19 at 22:52
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.

| cite | improve this answer | |
$\endgroup$

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.