Skip to content
Preprint

The Complexity of Hamiltonian Cycles and Paths with Prescribed Walk Lengths

Oct 2026 · 0 citations · 10 references
Computer Science

TL;DR

This work proves NP-completeness for every finite nonempty set of odd lengths, resolving an open problem posed by Amarilli, Lombardo, and Monet (WG 2026).

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.

View source

Similar papers

Preprint Nov 2026

A Dichotomy for Terminal Cyclability

Given an undirected graph $G$ and a set $R \subseteq V(G)$ of terminals, Terminal Cyclability asks whether $G$ contains a simple cycle visiting every vertex of $R$. We establish a complexity dichotomy for this problem on red-minor-closed classes of annotated graphs. In particular, we show that Terminal Cyclability is p...

Matthias Bentert, Dario Cavallaro, Sebastian Wiederrecht · 0 citations
Preprint Nov 2026

On the Complexity of Extending Prescribed Linear Forests to Hamiltonian Cycles in Hypercubes

Let $Q_n$ be the $n$-dimensional hypercube, and let $P\subseteq E(Q_n)$ be a set of prescribed edges. It is known that, for $n\ge 2$, every such set $P$ with $|P|\leq 2n-3$ whose edges form a linear forest is contained in a Hamiltonian cycle of $Q_n$. This bound is sharp for general linear forests. The computational co...

Hua-Zhong Lu, Ting-Zeng Wu · 0 citations
Preprint Nov 2026

Two-block paths in oriented graphs under the Ore-type condition

Stein conjectured that for every positive integer $k$, every oriented graph with minimum semi-degree greater than $k/2$ contains every oriented path of length $k$ [Springer Optim.Appl. 165 (2020), 459--486]. For directed paths this is a classical result of Jackson (1981). The two-block case of the conjecture was establ...

Ke Zhao, Jia Zhou, Yun-Shu Gao · 0 citations
Preprint Oct 2026

Coefficientwise Extremality and Rigidity for Independent Sets in Bipartite Graph Covers

Let $G$ be a finite bipartite graph and let $\widetilde G$ be an $M$-fold cover. We compare independent sets of $\widetilde G$ with those of the trivial cover, consisting of $M$ disjoint copies of $G$, after prescribing how many vertices are selected above each vertex of $G$. A conjecture from 2011, motivated by the Be...

Yusuke Watanabe · 0 citations
Sep 2026

Breaking the 2n barrier for directed hamiltonicity

We give a randomized algorithm for Directed Hamiltonian Cycle on $n$-vertex directed graphs that runs in $O^*(1.9133^n)$ time. For general directed graphs, this is the first improvement in the exponential base over the classical $O(2^n n^2)$-time algorithms of Bellman and Held--Karp (1962). To obtain this improvement,...

Tomohiro Koana, Soh Kumabe · 0 citations
Preprint Oct 2026

Unranking $S$-avoiding permutations with two forbidden offsets

Given a finite family of combinatorial objects with a total order, ranking asks for the position of a given object, and unranking asks for the object occupying a given position. Both provide algorithmic access to families too large to enumerate. Kagey gave a polynomial-time algorithm for several position-restricted fam...

Antônio Augusto Tavares Ribeiro André · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.