In this talk, we give an example that combinatorial reconfiguration appears in industry, specifically power distribution systems. A power distribution network is designed as supplying electricity via multiple numbers of routes for redundancy. For example, the Japan standard benchmark model of power distribution networks has approximately 10^{58} alternatives for the choice of network configurations. Even the computation of a single optimal network configuration among them is out of reach. Furthermore, even if we may compute a single optimal network configuration, we need to find a switching procedure to reconfigure the current configuration to the optimal one so that any power failure does not occur during the transformation. This is exactly the situation of combinatorial reconfiguration. In this talk, we will explain the situation in power distribution systems, our reconfiguration algorithm, and experimental results. In addition, we will also explain optimization variant of reconfiguration problems, which is a more practical problem setting.

To solve real-world problems, we usually formulate these problems as mathematical models and then develop optimization algorithms for them. In this context, optimization algorithms generally find a single best or nearly best solution. However, these mathematical models may overly simplify or even ignore involved factors emerging in real-world problems, which yields that a solution obtained from the mathematical model may not be a solution for the original real-world problem. One possible approach to this issue is to enumerate multiple solutions. This approach also has a serious drawback in that the solutions enumerated are similar to one another, which may potentially defeat the purpose of finding multiple solutions. To fill the gap between real-world problems and mathematical models, diversity of solutions is a significant factor, which has received considerable attention in many fields. In this talk, I will present recent developments for finding diverse solutions in combinatorial optimization problems.

We study the problem of deciding reconfigurability of target sets of a graph. Given a graph $G$ with vertex thresholds $\tau$, consider a dynamic process in which vertex $v$ becomes activated once at least $\tau(v)$ of its neighbors are activated. A vertex set $S$ is called a "target set" if all vertices of $G$ would be activated when initially activating vertices of $S$. In the Target Set Reconfiguration problem, given two target sets $X$ and $Y$ of the same size, we are required to determine whether $X$ can be transformed into $Y$ by repeatedly swapping one vertex in the current set with another vertex not in the current set preserving every intermediate set as a target set. In this talk, we investigate the complexity of Target Set Reconfiguration in restricted cases. On the hardness side, we prove that Target Set Reconfiguration is PSPACE-complete on bipartite planar graphs of degree 3 or 4 and of threshold 2, bipartite 3-regular graphs of threshold 1 or 2, and split graphs, which is in contrast to the fact that a special case called Vertex Cover Reconfiguration is in P for the last graph class. On the positive side, we present a polynomial-time algorithm for Target Set Reconfiguration on graphs of maximum degree 2 and trees. The latter result can be thought of as a generalization of that for Vertex Cover Reconfiguration. 

Sometimes, Japanese kids use a ladder lottery to have a random assignment. The ladder lottery is very popular for Japanese people and also an interesting object from viewpoints of mathematics and computer science. In this talk, we introduce enumeration and reconfiguration problems of the ladder lotteries. First, we define the ladder lotteries. Then, we explain our algorithm for enumerating all the ladder lotteries. The algorithm enumerates using braid relations of ladder lotteries. Finally, we consider the reconfiguration problem of ladder lotteries. This problem asks, for given two ladder lotteries L1 and L2, whether L1 can be transformed to L2 by repeatedly applying braid relations. In this talk, we introduce some results on the length of the shortest reconfiguration sequence of two ladder lotteries.

 

In research on theoretical computer science, the research on games and puzzles have been playing important roles. Especially, in the research on computational complexity, giving simple and intuitive complete problems for some complexity classes will bring us new viewpoints and deep understanding of the classes since the characterizations by the Turing machine model are not necessarily easy to capture. 

 

From historical point of view, since there have been given tons of complete problems for the class NP, it is clarified that some common properties of puzzles characterize the class NP. Recently, it becomes to be possible to solve a fairly large-scape NP complete problems in a realistic time. The reasons are not only development of computers and algorithms; such understanding also plays a certain role. 

 

On the other hand, there had been a group of puzzles whose complexities  were unsolved in the last 5 decades. In recent years, it has gradually  become clear that such puzzles can be explained in the framework of combinatorial reconfiguration. Especially, it is interesting that representative puzzles are all PSPACE-complete. Elucidating simple PSPACE complete problems in the framework of combinatorial reconfiguration is expected to improve the understanding of the structure of class PSPACE, and in the future, it will be possible to solve some PSPACE complete problems in a realistic time.

 

I would like to share some interesting open problems that are interesting from the viewpoint of combinatorial reconfiguration.
 

Graph orientation is the process of orienting the edges of an undirected graph to obtain a directed graph, and is a topic that has been actively studied in the fields of combinatorial optimization and graph theory. In this talk, we will present our latest results on "reconfiguration of graph orientations", where the directions of some edges are flipped one by one while maintaining a certain connectivity constraint. Our main result is that "for an arbitrary orientation of a 2k-edge-connected undirected graph, we can monotonically increase the edge-connectivity by flipping the directions of some edges one by one, and finally obtain a k-edge-connected orientation." This result strengthens the classical Nash-Williams' theorem, and is useful when discussing the connectivity of the edge-flip graph of k-edge-connected orientations.
This result is based on joint research with some members of this project, and will be presented at SODA2022.

The Token Sliding problem (TS) is one of the most well-studied problems in combinatorial reconfiguration. In this talk, we study a directed variant of the problem: the Directed Token Sliding problem (DTS). In TS, a token can slide along an edge in both directions, while in DTS it must respect the direction of an arc, meaning that the reconfigurability is asymmetric. Since an undirected edge can be simulated by two arcs with opposite directions, DTS is a generalization of TS. In this talk, we show the hardness of DTS when the class of input graphs is limited. We also show that, as our main result, DTS can be solved in polynomial time when the input graph is a directed tree. This is a joint work with members of Groups A01 and C01, and graduate students.