4
$\begingroup$

Me and my colleague are interested in whether anyone has looked into a generalization of Hamiltonian cycles where vertices can be revisited, but we want to minimize the maximum number of times a given vertex is revisited. Does anyone know of papers considering this problem?

$\endgroup$
4
  • $\begingroup$ It seems that the decision version of this optimization problem -- "given a graph $G$ and a number $k$ in binary, is there a path that visits every node in $G$ at least once but no more than $k$ times" -- isn't even necessarily in NP, since such a path could be as long as the value of $k$, which is exponential in the length of $k$. $\endgroup$
    – Jake
    Nov 4, 2023 at 16:34
  • 2
    $\begingroup$ @Jake If there exists a solution, then there exists a solution of value at most the maximum degree of $G$. This can be shown for example by taking a spanning tree of $G$ and taking the tour naturally given by DFS. $\endgroup$
    – Laakeri
    Nov 4, 2023 at 17:09
  • 1
    $\begingroup$ This brings to another observation: If we are interested in approximation, then this problem seems to be closely related to the problem of finding a spanning tree that minimizes the maximum degree: A spanning tree of max degree $\Delta$ can be turned into a tour that visits each vertex at most $\Delta$ times, and a solution that visits each vertex at most $k$ times can be turned into a spanning tree of max degree $2k$. $\endgroup$
    – Laakeri
    Nov 4, 2023 at 17:11
  • 1
    $\begingroup$ If we are interested in exact solution, then the problem is clearly at least as hard as Hamiltonicity, so no better than $2^n \cdot \text{poly}(n)$ algorithms are known. A perhaps non-trivial observation is that the problem can be solved in $2^n \cdot \text{poly}(n)$ time by using the algorithm of Björklund, Husfeldt, and Taslaman from SODA'12 for finding a cycle through $k$ specified vertices in $2^k \cdot \text{poly}(n)$ time. $\endgroup$
    – Laakeri
    Nov 4, 2023 at 17:15

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.