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?
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$– JakeNov 4 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$– LaakeriNov 4 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$– LaakeriNov 4 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$– LaakeriNov 4 at 17:15
Add a comment
|