arXiv preprint ·
The Complexity of Hamiltonian Cycles and Paths with Prescribed Walk Lengths
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Fix a set $S$ of positive integers. An $S$-Hamiltonian cycle is a cyclic ordering of all vertices of a graph such that each consecutive pair is joined by a walk whose length belongs to $S$. We study the complexity of deciding whether an input graph admits such an ordering, together with the corresponding path variants with prescribed or unrestricted endpoints. We complete the complexity classification for undirected graphs. In particular, we prove NP-completeness for every finite nonempty set of odd lengths, resolving an open problem posed by Amarilli, Lombardo, and Monet (WG 2026). For digraphs, all three problems are NP-complete for every fixed finite nonempty $S$ and admit linear-time algorithms when $S$ is cofinite. For other fixed infinite sets $S$, we establish NP-complete and undecidable cases, with undecidability occurring even when $S$ is recursive.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Improved Combinatorial Auctions with and without Samples
Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs
Certifying Capacity and Gaps of the Rank-Dependent Gain-Sharing Framework for Ranking
Approximation Algorithms for Emergency Vertex Cover with Few Stations and Fault-Tolerant Coverage
Query Complexity of Densest Sub(hyper)graph Problems
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.