An arborescence, which is a directed analogue of a spanning tree in an undirected graph, is one of the most fundamental combinatorial objects in a digraph. In this paper, we study arborescences in digraphs from the viewpoint of combinatorial reconfiguration, which is the field where we study reachability between two configurations of some combinatorial objects via some specified operations. Especially, we consider reconfiguration problems for time-respecting arborescences, which were introduced by Kempe, Kleinberg, and Kumar. We first prove that if the roots of the initial and target time-respecting arborescences are the same, then the target arborescence is always reachable from the initial one and we can find a shortest reconfiguration sequence in polynomial time. Furthermore, we show if the roots are not the same, then the target arborescence may not be reachable from the initial one. On the other hand, we show that we can determine whether the target arborescence is reachable from the initial one in polynomial time. Finally, we prove that it is NP-hard to find a shortest reconfiguration sequence in the case where the roots are not the same. Our results show an interesting contrast to the previous results for (ordinary) arborescences reconfiguration problems. © The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2025.

Directed Token Sliding asks, given a directed graph and two sets of pairwise nonadjacent vertices, whether one can reach from one set to the other by repeatedly applying a local operation that exchanges a vertex in the current set with one of its out-neighbors, while keeping the nonadjacency. It can be seen as a reconfiguration process where a token is placed on each vertex in the current set, and the local operation slides a token along an arc respecting its direction. Previously, such a problem was extensively studied on undirected graphs, where the edges have no directions and thus the local operation is symmetric. Directed Token Sliding is a generalization of its undirected variant since an undirected edge can be simulated by two arcs of opposite directions. In this paper, we initiate the algorithmic study of Directed Token Sliding. We first observe that the problem is PSPACE-complete even if we forbid parallel arcs in opposite directions and that the problem on directed acyclic graphs is NP-complete and W[1]-hard parameterized by the size of the sets in consideration. We then show our main result: a linear-time algorithm for the problem on directed graphs whose underlying undirected graphs are trees, which are called polytrees. Such a result is also known for the undirected variant of the problem on trees [Demaine et al., Theoret. Comput. Sci., 600 (2015), pp. 132--142], but the techniques used here are quite different because of the asymmetric nature of the directed problem. We present a characterization of yes-instances based on the existence of a certain set of directed paths, and then derive simple equivalent conditions from it by some observations, which yield an efficient algorithm. For the polytree case, we also present a quadratic-time algorithm that outputs, if the input is a yes-instance, one of the shortest reconfiguration sequences. © 2026, Society for Industrial and Applied Mathematics Publications. All rights reserved.

Nozaki et al. gave a homotopy classification of the knotted defects of ordered media in three-dimensional space by considering continuous maps from complements of spatial graphs to the order parameter space modulo a certain equivalence relation. We extend their result by giving a classification scheme for ordered media in handlebodies, where defects are allowed to reach the boundary. Through monodromies around meridional loops, global defects are described in terms of planar diagrams whose edges are colored by elements of the fundamental group of the order parameter space. We exhibit examples of this classification in octahedral frame fields and biaxial nematic liquid crystals.

In this article, we consider a transformation of k disjoint paths in a graph. For a graph and a pair of k disjoint paths P and Q connecting the same set of terminal pairs, we aim to determine whether P can be transformed to Q by repeatedly replacing one path with another path so that the intermediates are also k disjoint paths. The problem is called DISJOINT PATHS RECONFIGURATION. We first show that DISJOINT PATHS RECONFIGURATION is PSPACE-complete even when k = 2. On the other hand, we prove that, when the graph is embedded on a plane and all paths in P and Q connect the boundaries of two faces, DISJOINT PATHS RECONFIGURATION can be solved in polynomial time. The algorithm is based on a topological characterization for rerouting curves on a plane using the algebraic intersection number. We also consider a transformation of disjoint s-t paths as a variant. We show that the disjoint s-t paths reconfiguration problem in planar graphs can be determined in polynomial time, while the problem is PSPACE-complete in general.

The problem of packing as many subgraphs isomorphic to some H∈H as possible into a graph, where H is a collection of graphs, has been well studied in the literature. Both vertex-disjoint and edge-disjoint versions are known to be NP-complete for H that contains at least three vertices and at least three edges, respectively. In this paper, we consider "list variants" of these problems: Given a graph G, an integer k, and a collection LH of subgraphs of G isomorphic to some H∈H, the goal is to compute k subgraphs in LH that are pairwise vertex- or edge-disjoint. We show several positive and negative results, focusing on classes of sparse graphs, such as bounded-degree graphs, planar graphs, and bounded-treewidth graphs. © 2025 The Author(s)

The qubit routing problem, also known as the swap minimization problem, is a (classical) combinatorial optimization problem that arises in the design of compilers of quantum programs. We study the qubit routing problem from the viewpoint of theoretical computer science, while most of the existing studies investigated the practical aspects. We concentrate on the linear nearest neighbor (LNN) architectures of quantum computers, in which the graph topology is a path. Our results are three-fold. (1) We prove that the qubit routing problem is NP-hard. (2) We show that the qubit routing problem on a path can be solved in a fixed-parameter time where the number of two-qubit gates is a parameter. (3) We show that the qubit routing problem on a path can be solved in polynomial time if each qubit is involved in at most one two-qubit gate. © 2025 Copyright held by the owner/author(s).

A ladder lottery, known as "Amidakuji" in Japan, is a common way to decide an assignment at random. In this paper, we investigate reconfiguration and enumeration problems of cyclic ladder lotteries. First, when a permutation π and an optimal displacement vector x are given, we investigate the reconfiguration and enumeration problems of the "optimal" cyclic ladder lotteries of π and x. Next, for a given permutation π we consider reconfiguration and enumeration problems of the optimal displacement vectors of π. © 2025 The Author(s)

The dominating set reconfiguration problem is defined as determining, for a given dominating set problem and two among its feasible solutions, whether one is reachable from the other via a sequence of feasible solutions subject to a certain adjacency relation. This problem is PSPACE-complete in general. The concept of the dominating set is known to be quite useful for analyzing wireless networks, social networks, and sensor networks. We develop an approach to solve the dominating set reconfiguration problem based on answer set programming (ASP). Our declarative approach relies on a high-level ASP encoding, and both the grounding and solving tasks are delegated to an ASP-based combinatorial reconfiguration solver. To evaluate the effectiveness of our approach, we conduct experiments on a newly created benchmark set.

We introduce and study reconfiguration problems for (internally) vertex-disjoint shortest paths: Given two tuples of internally vertex-disjoint shortest paths for fixed terminal pairs in an unweighted graph, we are asked to determine whether one tuple can be transformed into the other by exchanging a single vertex of one shortest path in the tuple at a time, so that all intermediate results remain tuples of internally vertex-disjoint shortest paths. We also study the shortest variant of the problem, that is, we wish to minimize the number of vertex-exchange steps required for such a transformation, if exists. These problems generalize the well-studied Shortest Path Reconfiguration problem. In this paper, we analyze the complexity of these problems from the viewpoint of graph classes, and give some interesting contrast. © 2024, Brown University. All rights reserved.

We give a homotopy classification of the global defects in ordered media and explain it via the example of biaxial nematic liquid crystals, that is, systems where the order parameter space is the quotient of the three-sphere S 3 by the quaternion group Q. As our mathematical model, we consider continuous maps from complements of spatial graphs to the space S 3 / Q modulo a certain equivalence relation and find that the equivalence classes are enumerated by the six subgroups of Q. Through monodromy around meridional loops, the edges of our spatial graphs are marked by conjugacy classes of Q; once we pass to planar diagrams, these labels can be refined to elements of Q associated with each arc. The same classification scheme applies not only in the case of Q but also to arbitrary groups. © 2024 The Authors.