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 independent set reconfiguration problem (ISReconf) is the problem of determining, for two given independent sets of a graph, whether one can be transformed into the other by repeatedly applying a prescribed reconfiguration rule. There are two well-studied reconfiguration rules, called the Token Sliding (TS) rule and the Token Jumping (TJ) rule, and it is known that the complexity status of ISReconf differs between the TS and TJ rules for some graph classes. In this paper, we analyze how changes in reconfiguration rules affect the computational complexity of ISReconf. To this end, we generalize the TS and TJ rules to a unified reconfiguration rule, called the k-Jump rule, which removes one vertex from a current independent set and adds a vertex within distance k from the removed vertex to obtain another independent set having the same cardinality. We give the following three results: First, we show that the computational complexity of ISReconf under the k-Jump rule for general connected graphs is identical for all k≥3. Second, we present a polynomial-time algorithm to solve ISReconf under the 2-Jump rule for split graphs. Third, we consider the shortest variant of ISReconf, which determines whether there is a transformation of at most ℓ steps, for a given integer ℓ≥0. We prove that this shortest variant under the k-Jump rule is NP-complete for chordal graphs of diameter at most 2k+1, for any k≥3. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.

We develop a new characterization of potential maximal cliques of a triconnected planar graph and, using this characterization, give a polynomial delay algorithm generating all potential maximal cliques of a given triconnected planar graph. Combined with the dynamic programming algorithm due to Bouchitté and Todinca, this algorithm leads to a treewidth algorithm for general planar graphs that runs in time linear in the number of potential maximal cliques and polynomial in the number of vertices. © Alexander Grigoriev, Yasuaki Kobayashi, Hisao Tamaki, and Tom C. van der Zanden.

The concept of k-planarity is extensively studied in the context of Beyond Planarity. A graph is k-planar if it admits a drawing in the plane in which each edge is crossed at most k times. The local crossing number of a graph is the minimum integer k such that it is k-planar. The problem of determining whether an input graph is 1-planar is known to be NP-complete even for near-planar graphs [Cabello and Mohar, SIAM J. Comput. 2013], that is, the graphs obtained from planar graphs by adding a single edge. Moreover, the local crossing number is hard to approximate within a factor 2 − Ε for any Ε > 0 [Urschel and Wellens, IPL 2021]. To address this computational intractability, Bannister, Cabello, and Eppstein [JGAA 2018] investigated the parameterized complexity of the case of k = 1, particularly focusing on structural parameterizations on input graphs, such as treedepth, vertex cover number, and feedback edge number. In this paper, we extend their approach by considering the general case k ≥ 1 and give (tight) parameterized upper and lower bound results. In particular, we strengthen the aforementioned lower bound results to subclasses of constant-treewidth graphs: we show that testing 1-planarity is NP-complete even for near-planar graphs with feedback vertex set number at most 3 and pathwidth at most 4, and the local crossing number is hard to approximate within any constant factor for graphs with feedback vertex set number at most 2. © Tatsuya Gima, Yasuaki Kobayashi, and Yuto Okada; licensed under Creative Commons License CC-BY 4.0.

The minimum sum coloring problem with bundles was introduced by Darbouy and Friggstad (SWAT 2024) as a common generalization of the minimum coloring problem and the minimum sum coloring problem. During their presentation, the following open problem was raised: whether the minimum sum coloring problem with bundles could be solved in polynomial time for trees. We answer their question in the negative by proving that the minimum sum coloring problem with bundles is NP-hard even for paths. We complement this hardness by providing algorithms of the following types. First, we provide a fixed-parameter algorithm for trees when the number of bundles is a parameter; this can be extended to graphs of bounded treewidth. Second, we provide a polynomial-time algorithm for trees when bundles form a partition of the vertex set and the difference between the number of vertices and the number of bundles is constant. Third, we provide a polynomial-time algorithm for trees when bundles form a partition of the vertex set and each bundle induces a connected subgraph. We further show that for bipartite graphs, the problem with weights is NP-hard even when the number of bundles is at least three, but is polynomial-time solvable when the number of bundles is at most two. The threshold shifts to three versus four for the problem without weights. © 2025 Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto.

The crossing number of a graph is the least number of crossings over all drawings of the graph in the plane. Computing the crossing number of a given graph is NP-hard, but fixed-parameter tractable (FPT) with respect to the natural parameter. Two well-known variants of the problem are 2-layer crossing minimization and circular crossing minimization, where every vertex must lie on one of two layers, namely two parallel lines, or a circle, respectively. In both cases, edges are drawn as straight-line segments. Both variants are NP-hard, but admit FPT-algorithms with respect to the natural parameter. In recent years, in the context of beyond-planar graphs, a local version of the crossing number has also received considerable attention. A graph is k-planar if it admits a drawing with at most k crossings per edge. In contrast to the crossing number, recognizing k-planar graphs is NP-hard even if k = 1 and hence not likely to be FPT with respect to the natural parameter k. In this paper, we consider the two above variants in the local setting. The k-planar graphs that admit a straight-line drawing with vertices on two layers or on a circle are called 2-layer k-planar and outer k-planar graphs, respectively. We study the parameterized complexity of the two recognition problems with respect to the natural parameter k. For k = 0, the two classes of graphs are exactly the caterpillars and outerplanar graphs, respectively, which can be recognized in linear time. Two groups of researchers independently showed that outer 1-planar graphs can also be recognized in linear time [Hong et al., Algorithmica 2015; Auer et al., Algorithmica 2016]. One group asked explicitly whether outer 2-planar graphs can be recognized in polynomial time. Our main contribution consists of XP-algorithms for recognizing 2-layer k-planar graphs and outer k-planar graphs, which implies that both recognition problems can be solved in polynomial time for every fixed k. We complement these results by showing that recognizing 2-layer k-planar graphs is XNLP-complete and that recognizing outer k-planar graphs is XNLP-hard. This implies that both problems are W[t]-hard for every t and that it is unlikely that they admit FPT-algorithms. On the other hand, we present an FPT-algorithm for recognizing 2-layer k-planar graphs where the order of the vertices on one layer is specified. © Yasuaki Kobayashi, Yuto Okada, and Alexander Wolff.

We introduce the Multi-Objective Combinatorial Reconfiguration Optimization Problem (MO-CROP), and propose an Answer Set Programming (ASP) based approach for its solution. MO-CROP involves finding the Pareto-optimal sequences (or Pareto front) of adjacent feasible solutions between two given feasible solutions of a combinatorial problem, considering both cost and length. Our algorithm is compactly implemented through multi-shot ASP solving, and its implementing solver optirecon provides an effective tool for solving MO-CROP. As a concrete example of MO-CROP, we present an ASP encoding for solving the multi-objective independent set reconfiguration optimization problem. Experimental results on the benchmark set from the recent CoRe Challenge demonstrate our approach's ability to capture diverse optimal sequences that reveal trade-offs between cost and length, a capability often lacking in traditional combinatorial reconfiguration methods. © 2025 The Authors.