<p>What are you wondering about this problem? If <span class="math-container">$X$</span> is an input, it is obviously at least as hard as the longest path problem, since it contains the longest path problem as a special case (<span class="math-container">$X=1$</span>). But I think, even for any fixed <span class="math-container">$X \geq 2$</span>, you can reduce the longest path problem to your problem as follows:</p>
<p>Let <span class="math-container">$M$</span> be an upper bound on the length of the longest path in the graph. (For either weighted or unweighted version I believe <span class="math-container">$M$</span> is polysize.) For each vertex in the original graph, attach a cycle of length <span class="math-container">$M$</span>. Then I am pretty sure (but it needs proving) that the maximum length walk that visits each vertex at most X times will be the longest path, plus <span class="math-container">$X-1$</span> walks around each cycle.</p>

CC BY-SA 4.0
2023-10-07T06:36:17.147Z
Thank you.  I stumbled last week on a puzzle that involved a longest path problem and it occurred to me that it could be made significantly harder if multiple visits of a node were allowed.  Then looking a bit around, I did not find anything in the literature about this variation, which seems interesting.  I initially shared your feeling about a potential solution, but I am not sure that cycles would in all cases be covered "in full" by the longest path.
user1454590
CC BY-SA 4.0
2023-10-07T22:52:11.347Z
@user1454590 when you say "I initially shared your feeling about a potential solution, but I am not sure that cycles would in all cases be covered "in full" by the longest path" what do you mean? I did not try to give an algorithm for your variant of the problem, but rather, show that it is "at least as hard" as the longest-path problem (so NP-hard) by showing that if you could solve this variant problem in polynomial time, then you can solve the longest path problem in polynomial time.
NaturalLogZ
CC BY-SA 4.0
2023-10-08T10:34:57.200Z
I guess I can only agree that this problem is at least NP-hard.
user1454590
CC BY-SA 4.0
2023-10-06T21:01:33.283Z
2023-10-06T21:01:33.283Z
NaturalLogZ
<p>What about finding a path of maximum length in a given graph which may contain cycles, with the constraint that a vertex (or an edge) can be visited at most X (say 2 or 3) times ?</p>
<p>EDIT: X would be applicable globally, ie, the same X applies to all nodes of the graph.</p>
<p>What would an algorithm to solve this look like ?</p>

CC BY-SA 4.0
2023-10-06T19:42:10.943Z
How is $X$ given (e.g. binary or unary)? And is it global over the graph, or is there a different $X$ for each node?
Jake
CC BY-SA 4.0
2023-10-06T20:12:58.237Z
It would be the same X over the graph.  But you made it even more interesting by suggesting the possibility to have a specific X for each node !
user1454590
<graph-theory><graph-algorithms>
A variation of the longest path problem
user1454590
# A variation of the longest path problem

(Asked by: username_0 on 2023-10-06)

What about finding a path of maximum length in a given graph which may contain cycles, with the constraint that a vertex (or an edge) can be visited at most X (say 2 or 3) times ?

EDIT: X would be applicable globally, ie, the same X applies to all nodes of the graph.

What would an algorithm to solve this look like ?

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: How is $X$ given (e.g. binary or unary)? And is it global over the graph, or is there a different $X$ for each node?  
> **username_0**: It would be the same X over the graph.  But you made it even more interesting by suggesting the possibility to have a specific X for each node !  

---

## 1 answers

### Answer by username_2 on 2023-10-06. Score: 1

What are you wondering about this problem? If $X$ is an input, it is obviously at least as hard as the longest path problem, since it contains the longest path problem as a special case ($X=1$). But I think, even for any fixed $X \geq 2$, you can reduce the longest path problem to your problem as follows:

Let $M$ be an upper bound on the length of the longest path in the graph. (For either weighted or unweighted version I believe $M$ is polysize.) For each vertex in the original graph, attach a cycle of length $M$. Then I am pretty sure (but it needs proving) that the maximum length walk that visits each vertex at most X times will be the longest path, plus $X-1$ walks around each cycle.

> **Comments:**
> **username_0**: Thank you.  I stumbled last week on a puzzle that involved a longest path problem and it occurred to me that it could be made significantly harder if multiple visits of a node were allowed.  Then looking a bit around, I did not find anything in the literature about this variation, which seems interesting.  I initially shared your feeling about a potential solution, but I am not sure that cycles would in all cases be covered "in full" by the longest path.  
> **username_2**: @user1454590 when you say "I initially shared your feeling about a potential solution, but I am not sure that cycles would in all cases be covered "in full" by the longest path" what do you mean? I did not try to give an algorithm for your variant of the problem, but rather, show that it is "at least as hard" as the longest-path problem (so NP-hard) by showing that if you could solve this variant problem in polynomial time, then you can solve the longest path problem in polynomial time.  
> **username_0**: I guess I can only agree that this problem is at least NP-hard.  

---

