CS Paper Radar

It's Hard to PArcK

Kyle Burke, Jeffrey Leman, Craig Tennenhouse

cs.CC cs.DMmath.CO ·submitted 2026-08-29 21:06 UTC · v1

Abstract

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.

Comment
16 pages, 20 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Planar PArcK is PSPACE-complete

cs.CC cs.DMmath.CO ·2026-11-15 ·Craig Tennenhouse, Kanae Yoshiwatari
similarity 0.72
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

Arc Kayles is PSPACE-complete

cs.CC cs.DMmath.CO ·2026-09-20 ·Édouard Bonnet
similarity 0.55
Abstract · 11 pages, 1 figure

We show that Arc Kayles is PSPACE-complete. This solves a question raised by Schaefer in 1976.

0.26

The Complexity of Undirected Partizan Edge Geography

cs.DS math.CO ·2026-09-16 ·Yuto Okada
similarity 0.55
Abstract · 9 pages, 6 figures

Partizan Edge Geography is a two-player game on a graph where each player has their own token on a vertex and moves their token to a neighbor in a turn removing the edge. Two player alternately move their tokens and the first player who cannot move loses the game. Fraenkel and Simonson (TCS, 1993) showed that the winner determination of this game is PSPACE-complete on directed graphs, given a graph and token positions. This paper resolves its complexity on undirected graphs by showing the PSPACE-completeness on bipartite undirected graphs of maximum degree 3. The same reduction also works for a variant where two tokens cannot be placed on the same vertex.

0.53

Building Navigable Graphs Without Search in Three Composable Stages

cs.DB cs.IR ·2026-10-06 ·Édgar Chávez
code/datahot direction similarity 0.54
Abstract · 26 pages. Code: github.com/zevahcle/graft-ann (branch fgraft); experiments, logs and patches: github.com/zevahcle/fgraft-experiments

Navigable graphs can be built without searching for neighbors: partition the data, evaluate every pair inside each part, and select each point's edges from the candidates. We give such a construction in three separable stages and show that the middle one decides the quality. The pool is any partition with a few memberships per point. The ending turns a point's candidates into out-edges; ours keeps a bounded heap, prunes by occlusion with a per-corpus slack, and appends reverse edges, re-pruning only where a list overflows. The spine is any edge set, exempt from the prune, that keeps the graph reachable from its entry; ours, half-space-proximal edges over a random sample, routes monotonically to every sampled point and replaces a spanning tree at 1/10 to 1/500 of its cost. The ending composes with any partitioner: on PiPNN's own candidate pool it beats PiPNN's ending on each of six corpora from $10^6$ to $10^8$ points, by 3 to 14% in distance evaluations at equal recall, and with 60 to 120 memberships per point the composed build matches or beats a full dense construction at k=10 and k=100 on all six, in 0.5 to 0.9 of its build time, deterministically. The analysis explains why. Once a pool is localised its quality is set by the data: every pool built on GIST lands within 4% of the exact-kNN ceiling, and the pairs a block cover misses are predicted, point by point, by the local clustering of the kNN graph, whose zero-clustering tail sets the memberships a corpus needs and grows with n. All code, patches and logs are public.

0.49

Decomposing Directed Graphs into Partial Orders is Hard

cs.CC ·2026-10-27 ·Grzegorz Gutowski, Dominik Jilg, Antonio Lauerbach, Mikołaj Rams
theory similarity 0.51
Abstract

Comparability graphs represent partial orders and provide natural building blocks for representing a graph as a union of simpler graphs. The analogous task in the directed setting is to represent a digraph as a union of partial orders. Aboulker et al. [arXiv, 2026] recently introduced the partial order decomposition number as a useful structural parameter in their study of tournaments. Formally, a partial order decomposition of a digraph $D$ is a cover of its arc set by transitive acyclic subdigraphs, each representing a strict partial order on the vertex set of $D$. The partial order decomposition number is the minimum number of such subdigraphs needed. We also consider the partitioning variant, in which every arc belongs to exactly one of the partial orders in the decomposition. We prove that, for every fixed $k\geq 2$, deciding whether a digraph admits a decomposition into at most $k$ partial orders is NP-complete, even for directed acyclic graphs (DAGs). For $k=2$, we reduce from NAE-3-SAT. For $k\geq 3$, we reduce from $k$-Coloring, and the reduction yields DAGs with triangle-free underlying graphs. Both reductions establish hardness for both variants. We further show that the minimum cover size and the minimum partition size can differ even on DAGs.

0.25

Smallest Cubic Non-1-Planar Graphs

cs.CG math.COcs.DM ·2026-09-23 ·Sergey Pupyrev
similarity 0.51
Abstract

A graph is 1-planar if it has a drawing in which every edge is crossed at most once. We show that the smallest cubic non-1-planar graphs have $30$ vertices. Two such graphs are the Tutte-Coxeter graph of girth eight and a graph of girth seven that we call the Byte graph. Every subcubic graph with fewer than $30$ vertices is 1-planar. Our proof is computer-assisted, but directly testing all relevant graphs is impractical. To establish non-1-planarity of the two graphs, we extend a SAT-based solver with a custom clause propagator based on separating cycles and a case split based on graph automorphisms, allowing independent cases to be solved in parallel. To show that all smaller subcubic graphs are 1-planar, we introduce the concept of $k$-flexibility: every set of at most $k$ prescribed edges can remain uncrossed in some 1-planar drawing. We use this property to reconstruct 1-planar drawings of larger graphs from drawings of smaller $k$-flexible graphs. This replaces exhaustive testing of more than forty billion cubic graphs with computations on far fewer graphs of smaller order.

0.28

Kempe Reachability with $k\geq 3$ Colors Is $\mathsf{PSPACE}$-Complete on Claw-Free Graphs

cs.DS cs.DM ·2026-10-22 ·Duc A. Hoang
similarity 0.51
Abstract

A \emph{proper vertex coloring} assigns colors to vertices so that adjacent vertices have distinct colors. A \emph{Kempe change} in a proper vertex coloring exchanges two colors on one component of the subgraph induced by the vertices of those colors. For a fixed palette of $k$ colors, \textsc{Kempe Reachability} asks whether two given proper vertex colorings of the same graph are connected by a sequence of Kempe changes. This problem is known to be $\mathsf{PSPACE}$-complete for every fixed $k\geq 3$. A graph is \emph{claw-free} if no vertex has three pairwise nonadjacent neighbors. The \emph{line graph} of a graph has one vertex for each edge, with two vertices adjacent exactly when the corresponding edges share an end. Line graphs are claw-free, and their Kempe changes correspond to \emph{edge-Kempe changes} in the original graph, which exchange two colors on one component of the subgraph formed by the edges of those colors. A claw-free graph with a proper $k$-coloring has maximum degree at most $2k-2$, whereas for $k\geq 4$ all proper $k$-colorings of a graph of maximum degree at most $k$ are connected by Kempe changes. We show that, for every fixed $k\geq 3$, \textsc{Kempe Reachability} with $k$ colors is $\mathsf{PSPACE}$-complete even on line graphs of connected simple $k$-regular graphs, and hence even on connected $(2k-2)$-regular claw-free graphs. Equivalently, deciding whether two proper $k$-edge-colorings are connected by edge-Kempe changes is $\mathsf{PSPACE}$-complete even on connected simple $k$-regular graphs. ChatGPT 6 Pro and Claude Fable 5.1 were used to assist with developing and reviewing mathematical arguments and drafting and revising the paper. The author takes full responsibility for the correctness and content of the paper.

0.26

A Polynomial Kernel for Planar Directed Feedback Vertex Set

cs.DS ·2026-09-20 ·Zimo Sheng, Mingyu Xiao
similarity 0.51
Abstract

The Directed Feedback Vertex Set problem (DFVS) asks whether a digraph can be made acyclic by deleting at most $k$ vertices. Whether DFVS admits a polynomial kernel parameterized by $k$ is a major open problem in kernelization, even for planar digraphs. We resolve the planar case by giving a deterministic kernel with $O(k^{66}\log^2 k)$ vertices and arcs. Our algorithm proceeds in three stages. First, we apply structural reduction rules to the input digraph, bounding the number of directed faces and some special vertices. Second, we pass to the planar dual, where vertex deletion corresponds to adding groups of reverse arcs to make each weakly connected component strongly connected. The structural bounds in the first stage yield a small retained vertex set in the dual. We then compress the dual instance by identifying vertices with the same distance records from this retained vertex set. The main technical contribution is a directed-cut argument showing that this identification preserves feasibility. Finally, we transform the polynomial-size dual instance back into an instance of Planar Directed Feedback Vertex Set via a $3$-CNF encoding and a planar graph construction.

0.39