CS Paper Radar

The Complexity of Hamiltonian Cycles and Paths with Prescribed Walk Lengths

Hitendra Kumar, Mathieu Mari, R. B. Sandeep

cs.DS ·submitted 2026-10-13 12:47 UTC · v2
theory

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.

Comment
added acknowledgement

Closest papers

Nearest neighbours by meaning across the whole index.

The (Parameterized) Complexity of Ordering a Graph While Avoiding a Forbidden Pattern

cs.DS cs.CC ·2026-08-31 ·Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, Martin Nöllenburg +1 more
published similarity 0.70
Abstract · Appears in the Proceedings of the 21st International Symposium on Parameterized and Exact Computation (IPEC 2026); 57 pages, 11 figures, 1 t…

In this paper, we study the Pattern Avoidance problem of determining whether a given graph $G$ admits a linear vertex order which avoids a given pattern $P$, i.e., a vertex sequence with some forced and forbidden edges, on every suborder. Such patterns form a natural ordered counterpart to induced subgraphs in the order-invariant setting, and it is known that Pattern Avoidance captures a broad variety of graph problems including Bandwidth, Vertex Coloring, Queue Number, and extends to vertex-deletion problems such as Odd Cycle Transversal. We show that Pattern Avoidance is $Σ_2^{\textsf{P}}$-complete and furthermore remains intractable (in both the classical and parameterized sense) even under a variety of severe restrictions to both the pattern $P$ and the graph $G$. As our main contributions, we complement these lower bounds with the following tractability results, which provide a unifying framework for recognizing pattern-definable graph classes: - a fixed-parameter algorithm w.r.t. the vertex integrity of $G$ plus $|V(P)|$, - a fixed-parameter algorithm w.r.t. the neighborhood diversity of $G$ plus $|E(P)|$, and - a polynomial algorithm for Pattern Avoidance on forests for almost all constant-sized patterns.

0.54

A Dichotomy for Terminal Cyclability

cs.DS ·2026-11-04 ·Matthias Bentert, Dario Cavallaro, Sebastian Wiederrecht
similarity 0.68
Abstract

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 polynomial-time solvable on every such class excluding any annotated planar graph. The problem is NP-complete whenever the class contains all annotated planar graphs. More precisely, we give an $|G|^{2^{\mathbf{poly}(b)}}$-time algorithm, where $b$ is the bidimensionality of $(G,R)$. Our main technical contribution is the introduction of a weak irrelevant vertex rule. Rather than removing irrelevant vertices until the treewidth becomes constant, we only remove irrelevant vertices until the treewidth is logarithmic in the graph size. Such a weakening is necessary as a parameter-only treewidth threshold for an irrelevant vertex rule in this setting is known to be impossible to realise. Combined with a single-exponential algorithm for Terminal Cyclability parameterized by treewidth, this yields the polynomial-time algorithm for our dichotomy.

0.24

Space Complexity of Reachability in Simple Path Graphs

cs.CC ·2026-10-20 ·Krishnamoorthy Dinesh, Chandana Sasidharan
published similarity 0.68
Abstract · 17 pages, 9 figures

One of the central questions in space complexity is whether nondeterministic logspace computations ($\textsf{NL}$) can be simulated in unambiguous logspace ($\textsf{UL}$). A stronger notion, \emph{reach unambiguity} ($\textsf{RUL} \subseteq \textsf{UL} \cap \textsf{co}\textsf{UL}$), requires every configuration reachable from the start to have exactly one computation path (Buntrock et.al. 91). While directed graph reachability is $\textsf{NL}$-complete, planar graph reachability is in $\textsf{UL}$ and undirected graph reachability is in deterministic logspace ($\textsf{L}$). In this work, we study the space complexity of reachability problem for restricted directed graph families and show the following. - For reach unambiguous graphs (graphs with at most one path from start vertex to every vertex), Lange (Lange 97) showed that reachability is in $\textsf{RUL}$. As our main result, we show that for simple path graphs (introduced in Kannan et.al. 08), which contains reach unambiguous graphs), where each vertex has at most one simple path from the start, we show that the reachability problem lies in $\textsf{UL} \cap \textsf{co}\textsf{UL}$. - Our first result can also be equivalently stated as: the recognition problem for simple path is in $\textsf{UL} \cap \textsf{co}\textsf{UL}$ if and only if the reachability problem restricted to simple path graphs is also in $\textsf{UL} \cap \textsf{co}\textsf{UL}$. Inspired by this, we investigate the complexity of graph recognition versus graph reachability for graph classes. Observe that for any graph class, solving reachability (for the class) also solves the recognition problem for that class. We show that for reach unambiguous graphs, solving recognition is as hard as solving reachability (making both of them $\textsf{RUL}$-complete). (Abstract shortened to meet arXiv limits)

0.62

NP-Hardness of the $H$-Free Edge-Deletion Problem

cs.CC math.CO ·2026-09-09 ·Lior Gishboliner, Ethan Honest
similarity 0.66
Abstract

For a graph $H$, the $H$-freeness edge-deletion problem is the algorithmic problem of finding, for an input graph $G$, the minimum number of edges of $G$ whose deletion turns $G$ into an $H$-free graph. We show that for every graph $H$ containing a cycle, this problem is NP-hard. This proves a conjecture of Gishboliner, Levanzov and Shapira, and completes the characterization of the complexity of the $H$-freeness edge-deletion problem, answering a question of Alon, Shapira and Sudakov.

0.38

Odd Cycle Transversal on $H$-free graphs

cs.DS cs.DMmath.CO ·2026-09-25 ·Esther Galby, Paloma T. de Lima, Andrea Munaro, Amir Nikabadi
similarity 0.66
Abstract

\textsc{Odd Cycle Transversal} is a classic $\mathsf{NP}$-hard graph optimization problem asking for a minimum-weight set of vertices whose deletion makes the input graph bipartite, or equivalently, a maximum-weight induced bipartite subgraph. We show that \textsc{Odd Cycle Transversal} is quasi-polynomial-time solvable on $kP_4$-free graphs, for every fixed $k \in \mathbb{N}$. In fact, we provide an $n^{O_k(\log n)}$-time algorithm for the more general \textsc{Max-Weight List $2$-Colorable Induced Subgraph}, where the notation $O_{k}(\cdot)$ hides factors depending on $k$. Paired with known results from the literature, this allows us to obtain a complete complexity dichotomy for these two problems on $H$-free graphs into cases solvable in quasi-polynomial time and cases which are $\mathsf{NP}$-hard, in particular resolving an open problem of Agrawal, Lima, Lokshtanov, Saurabh, and Sharma [SODA 2024]. Our algorithms are based on a new structural tool that may be of independent interest. We introduce the notion of $H$-amiable family and show that, for every fixed graph $H$ without isolated vertices and every fixed $k\ge2$, every $kH$-free graph admits an $H$-amiable family of quasi-polynomial size that can be constructed in quasi-polynomial time. Besides yielding the aforementioned algorithms, this result gives, for every fixed connected graph $H$ and every fixed $k\ge2$, a reduction from \textsc{Max-Weight Independent Set} on $kH$-free graphs to the same problem on $H$-free graphs with $n^{O_{H,k}(\log n)}$ overhead. In this setting, it improves the $n^{O_{H,k}(\log^3 n)}$ overhead obtained by specializing the general reduction of Gartland and Lokshtanov [FOCS 2020].

0.16

Integer reachability in VASS with transfers: a refined complexity analysis

cs.FL cs.CC ·2026-10-01 ·Tymoteusz Kucharek, Piotr Hofman
published similarity 0.66
Abstract · Full version of the paper accepted at FSTTCS 2026

Integer reachability is NP-complete for vector addition systems with states (VASS), but becomes PSPACE-complete in the presence of transfer operations. We refine this complexity gap for single-transfer VASS by identifying structural features of transfers responsible for the increase in complexity. Each system induces a transfer graph whose vertices are counters and whose edges represent possible transfers. We classify its vertices as good or bad, according to the branching and cyclic structure of their reachable subgraphs. Let $b$ be the number of bad vertices. We show that every positive instance admits a polynomially verifiable certificate of size $|I|^{O(b+1)}$, where $|I|$ is the input size. Consequently, integer reachability for single-transfer VASS can be decided in nondeterministic time $|I|^{O(b+1)}$; in particular, it belongs to NP for every class with a bounded number of bad counters. Conversely, we show that bad counters provide sufficient structural power to encode space-bounded computation. For every transfer graph with $b$ bad vertices, we construct a single-transfer VASS that encodes the acceptance of a Turing machine using $b^{O(1)}$ tape cells. This yields PSPACE-hardness for every polynomial-time constructible family of transfer graphs containing linearly many bad vertices. Our results isolate the transfer patterns responsible for the complexity of integer reachability.

0.18

Hamilton Cycles in 10-Tough $(2P_2 \cup P_1)$-Free Graphs

cs.DM math.CO ·2026-08-25 ·Qiuyu Chen
theory similarity 0.66
Abstract · 16 pages, no figures

A graph is called 10-tough and $(2P_2 \cup P_1)$-free if every vertex set whose deletion leaves at least two components has cardinality at least ten times the number of those components and if the graph has no induced subgraph consisting of two disjoint edges and an isolated vertex. We prove that every finite simple 10-tough $(2P_2 \cup P_1)$-free graph on at least three vertices is Hamiltonian. The proof splits according to whether some edge has joint neighbourhood of order at most $4n/11$. In the small-neighbourhood case, a matched path-cover is compressed to a prescribed matching. In the large-neighbourhood case, an asymmetric analysis of the two components left by a putative small cut yields the required connectivity bound. A Hamilton cycle through the prescribed edges is then expanded, and a cycle-extension lemma inserts the remaining vertices.

0.09

Discrete Temporal CSPs et al

cs.CC math.LO ·2026-10-15 ·Lukas Pieper
similarity 0.66
Abstract

We revisit the complexity classification of constraint satisfaction problems (CSPs) for first-order reducts of $(\mathbb{Z},<)$, established by Bodirsky, Martin, and Mottet in 2018. Following their approach, we give a self-contained proof of this classification, correcting several errors in the argument. We further show that, with the exception of cases arising from finite-domain CSPs, all tractable cases are solved by a well-known uniform algorithm, eliminating the need for the collection of ad-hoc algorithms used in the original paper. A central component of the proof allows the analysis to be restricted to first-order reducts of $(\mathbb{Z},<)$ that contain the successor relation. We substantially simplify this reduction and generalize the underlying construction. This generalization allows us to apply the same technique to first-order reducts of the triangular lattice graph and of infinite regular trees, yielding a complete complexity classification for these classes of structures, in particular a $\mathsf{P}$ versus $\mathsf{NP}$-complete dichotomy.

0.21