0
$\begingroup$

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 ?

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Jake
    Commented Oct 6, 2023 at 19:42
  • $\begingroup$ 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 ! $\endgroup$ Commented Oct 6, 2023 at 20:12

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Commented Oct 7, 2023 at 6:36
  • $\begingroup$ @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. $\endgroup$ Commented Oct 7, 2023 at 22:52
  • $\begingroup$ I guess I can only agree that this problem is at least NP-hard. $\endgroup$ Commented Oct 8, 2023 at 10:34

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.