# A variation of the longest path problem

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 ?

• 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
Commented Oct 6, 2023 at 19:42
• 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 ! Commented Oct 6, 2023 at 20:12

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.