CS Paper Radar

Closest papers

Nearest neighbours by meaning across the whole index.

It's Hard to PArcK

cs.CC cs.DMmath.CO ·2026-08-29 ·Kyle Burke, Jeffrey Leman, Craig Tennenhouse
similarity 0.55
Abstract · 16 pages, 20 figures

We show that Partizan Arc Kayles (PArcK), a generalization of Domineering to graphs, is PSPACE-complete via a reduction from Positive CNF and with recently-discovered techniques for creating PArcK positions with high temperature. The reduction uses only red and blue edges.

0.29

Planar PArcK is PSPACE-complete

cs.CC cs.DMmath.CO ·2026-11-15 ·Craig Tennenhouse, Kanae Yoshiwatari
similarity 0.45
Abstract · 9 pages

Partizan Arc Kayles, or PArcK, is a partizan combinatorial game on edge colored graphs, and is a generalization of the game Domineering. Previously, PArcK was shown to be PSPACE-complete on bipartite graphs. In this paper we show that PArcK is PSPACE-complete even when restricted to planar graphs of degree at most three by a reduction from Generalized Hex.

0.24

On U_c-admitting spaces and U_c-completions of T_0 spaces

cs.LO math.GN ·2026-10-22 ·Kangming Lu, Qingguo Li, Shengwen Wang, Rongqi Xiao
theory similarity 0.42
Abstract

In this paper, we introduce a new class of spaces, termed U_c-admitting spaces, and investigate their relationships with U_s-admitting spaces and well-filtered spaces. Adopting the perspective of H-sobriety, we show that every U_c-admitting space is H-sober, so that U_c-admitting spaces arise as a special case of H-sober spaces. Consequently, the category U_c-Sob of U_c-admitting spaces and continuous maps is complete and forms a reflective subcategory of Top_0. In addition, we prove that a T_0 space X is U_c-admitting if and only if its Smyth power space is U_c-admitting. Finally, we present the standard U_c-completion of an arbitrary T_0 space.

0.25

PSPACE-Completeness of Multi-Agent Path Finding for Large Agents

cs.CC ·2026-08-13 ·Maichi Zhang, Naoyuki Kamiyama, Kanae Yoshiwatari
similarity 0.40
Abstract

Multi-Agent Path Finding for Large Agents (LA-MAPF) is a geometric variant of MAPF in which agents are modeled as disks and conflicts are determined by physical overlap in the underlying Euclidean workspace. The goal of LA-MAPF is to decide whether there exists a sequence of conflict-free transitions from a start configuration to a goal configuration. Agafonov and Yakovlev proved that LA-MAPF is NP-hard. In this paper, we strengthen their result by proving that LA-MAPF is PSPACE-complete via a polynomial-time reduction from Restricted Sliding Tokens.

0.04

PSPACE-Completeness of the Reachability Relation of Robust Dynamical Systems

cs.CC ·2026-10-19 ·Manon Blanc
theory similarity 0.39
Abstract

Dynamical systems are a widely used model of computation and an intuitive representation of many natural phenomena in many applied fields. The last decades have seen an impressive use of computers in studying and analysing them, with several visible theoretical breakthroughs. The question of reachability for dynamical systems is central: given two points, is there a trajectory between them in the dynamical system? Reachability, in particular over the reals, is undecidable in the general case: it is only computably enumerable, even under reasonable hypotheses, e.g. for a computable dynamics in general. But it is known to become decidable, and even lies in PSPACE, under suitably quantified robustness assumptions. In this paper, we focus on PSPACE-completeness results over the reals, in the sense of computable analysis, regarding discrete-time and continuous-time robust dynamical systems. We prove that, under some additional and rather reasonable hypotheses, the reachability relation becomes even PSPACE-complete for both classical and second-order complexity second-order complexity, for an adapted notion of reduction. As a side-effect, we also prove an improvement of an algebraic Ordinary Differential Equations-based characterisation of PSPACE, removing one of the base functions of the algebra. By doing so, we link results from dynamical systems and complexity over the reals, including the models of computable analysis and second-order complexity.

0.29

Compressed Subsequence Checking is PSPACE-complete

cs.FL ·2026-09-13 ·Markus Lohrey
theory similarity 0.37
Abstract

It is shown that the (scattered) subsequence problem for two words represented by straight-line programs is $\mathsf{PSPACE}$-complete, even over a binary alphabet. The lower bound is obtained by a polynomial-time reduction from quantified subset sum. If the two words are given explicitly, i.e., uncompressed, then the subsequence problem is hard for uniform $\mathsf{NC}^1$ and in deterministic logspace.

0.24

Space Complexity of Reachability in Simple Path Graphs

cs.CC ·2026-10-20 ·Krishnamoorthy Dinesh, Chandana Sasidharan
published similarity 0.36
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

Reachability in Five-Dimensional Vector Addition Systems Is PSPACE-Complete

cs.FL cs.CC ·2026-10-29 ·Weijun Chen, Bo Fu, Yuxi Fu
theory similarity 0.36
Abstract · 69 pages,1 figure

Vector addition systems (VAS) are a fundamental model of concurrent computation in which transitions update nonnegative integer counters by adding integer vectors, provided all counters remain nonnegative. Closely related to Petri nets, VAS are the single-state counterpart of vector addition systems with states (VASS), which use finitely many states to restrict the available transitions. A classical simulation of $d$-VASS by $(d+3)$-VAS connects their reachability problems, but the complexity-theoretic picture of fixed-dimensional VAS remains largely unclear. While reachability in $2$-VASS is PSPACE-complete under binary encoding, the best known upper bound for $5$-VAS was only elementary. We prove that every reachable $5$-VAS instance has a reachability witness of length polynomial in its unary size. Consequently, $5$-VAS reachability is NL-complete under unary encoding and PSPACE-complete under binary encoding. We also establish a polynomial factorization of the reachability relation of every $d$-VAS with $d \ge 3$. For $5$-VAS, this strengthens Hopcroft and Pansiot's effective semilinearity of reachability sets to the full reachability relation. For every fixed $d\ge3$, it also yields an $\mathsf F_d$ upper bound for reachability in $(d+3)$-VAS.

0.16