<p>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?</p>

CC BY-SA 4.0
2023-11-04T16:34:20.020Z
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$.
Jake
CC BY-SA 4.0
2023-11-04T17:09:29.930Z
@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.
Laakeri
CC BY-SA 4.0
2023-11-04T17:11:39.290Z
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$.
Laakeri
CC BY-SA 4.0
2023-11-04T17:15:26.533Z
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.
Laakeri
<graph-theory><hamiltonian-paths>
Name for a cyclic path in a graph that visits every vertex while minimizing the maximum number of times a given vertex is revisited?
aellab
# Name for a cyclic path in a graph that visits every vertex while minimizing the maximum number of times a given vertex is revisited?

(Asked by: username_0 on 2023-11-04)

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?

**Tags:** graph-theory, hamiltonian-paths

> **Comments:**
> **username_1**: 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$.  
> **username_2**: @username_1 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.  
> **username_2**: 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$.  
> **username_2**: 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.  

---

## 0 answers

