# Find the k length path that maximize a node associate metric

Let's say I have :

1. a Graph g
2. v vertices. Each vertex is associated to a cost c.
3. A special vertex called the starter vertex or vs.

I want to find the path p of length 10 (for example), that start from vs and that maximize the sum of the 10 seens nodes costs. I need to tell you that my graph represent a road network which means it has a big diamater, and the degree of each node is never above 6 or 7. Here is an example of the kind of a graph that I have. Obviously, I got way more nodes.

• Have you tried dynamic programming? For every vertex, solve your problem for every length which is at most 10. Apr 22, 2021 at 13:25
• @YuvalFilmus I do not have any experience with that but thks for the suggestion Apr 22, 2021 at 13:40
• Can you visit a vertex multiple times? If not, don't expect an efficient algorithm for large $k$ -- solving this problem with $k=n$ and $c=1$ for every vertex is equivalent to finding a Hamiltonian path starting at $vs$, which is NP-complete. Apr 22, 2021 at 14:06
• @j_random_hacker We can visit a vertex multiple times, but we will count its cost c only one time. I'm ok with a solution that is "ok". Do not care if the solution is not the best one. I need something somewhat close. Apr 22, 2021 at 14:11
• Please edit your question to incorporate that information, so it is clear to people encounter it for the first time. We want people to be able to tell what is being asked by reading just the question, without having to read the comments.
– D.W.
Apr 23, 2021 at 0:06

A brute-force approach is to do a backtracking search starting from $$s$$. Something like:

Search($$s$$, $$n$$, $$S$$):

1. If $$n=1$$, yield $$S \cup \{s\}$$ and return. Otherwise:

2. For each vertex $$v$$ that is adjacent to $$s$$, do:

a. Call Search($$v$$, $$n-1$$, $$S \cup \{s\}$$).

If you invoke Search($$vs$$, $$10$$, $$\emptyset$$), this will generate all possible sets of vertices that can arise from a path of length 10; now calculate the cost of each such subset, and keep the largest one.

$$6^{10}$$ is about 60 million, so this might complete within a few seconds on most graphs.

• Thk you @D.W. , I try to understand your approach Apr 23, 2021 at 11:54