2024/05/25 by Liu, Brian, Sheffield, Nathan S., Westover, Alek
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2405.16270
We study the following generalization of the Hamiltonian cycle problem: Given integers a,b and graph G, does there exist a closed walk in G that visits every vertex at least a times and at most b times? Equivalently, does there exist a connected [2a,2b] factor of 2b ⋅ G with all degrees even? This problem is NP-hard for any constants 1 ≤ a ≤ b. However, the graphs produced by known reductions have maximum degree growing linearly in b. The case a = b = 1 -- i.e. Hamiltonicity -- remains NP-hard even in 3-regular graphs; a natural question is whether this is true for other a, b. In this work, we study which a, b permit polynomial time algorithms and which lead to NP-hardness in graphs with constrained degrees. We give tight characterizations for regular graphs and graphs of bounded max-degree, both directed and undirected.