One of the adjacent fields of combinatorial reconfiguration is enumeration problems. An enumeration problem is a problem of outputting all solutions satisfying given constraints without duplication and is a fundamental field in theoretical computer science. Several frameworks have been proposed for constructing algorithms for solving enumeration problems. One of them is called the supergraph technique. The supergraph technique enumerates solutions by traversing on a solution graph whose vertices are solutions. In this talk, I will introduce an overview of how to construct enumeration algorithms based on the supergraph technique.

An edge-colored graph is a graph where each edge is assigned a color.In this talk, we introduce some studies on subgraphs with certain conditions in edge-colored graphs, for example, properly colored Hamilton cycles and properly colored spanning trees, and speaker's results. In addition, we discuss a relationship to a maroid. For example, we study a relationship between Rota's colorful conjecture and a decomposition of edge-colored graphs.
 

Invited Talk:

UNO Hiroyuki (Osaka Prefecture U.)

Gourds: a sliding-block puzzle with turning (ISAAC2020 Best Paper Award）

Zero-suppressed binary decision diagram (ZDD) is a compressed data structure for representing a family set. Algorithms that enumerate subgraphs such as paths and spanning trees of a given graph and construct ZDDs representing them are known. Moreover, algorithms that construct ZDDs for chordal subgraphs, interval subgraphs, planar subgraphs, and so on, have been proposed. We can apply constructed ZDDs to various applications including hotspot detection, electral districting and pencil puzzle solvers. In this talk, features of ZDDs and recent research on enumeration of subgraphs using ZDDs are introduced.

An edge-coloring of a graph is an assignment of colors on edges so that no two adjacent edges have the same color. In particular, it is a 3-edge-coloring if it uses at most three colors. In a 3-edge-coloring, if we choose a bicolored cycle and swap the colors on the cycle, we obtain another 3-edge-coloring. This operation is introduced by Kempe for the attempt to solve 4 Color Problem, and is still useful method for several related problems. In this talk, we discuss the reconfiguration problem of 3-edge-colorings in cubic graphs under the operation.

We exlain the three research topics: bounded model checking, SAT planning, and network update. Although computational problems considered in these topics (and also applications) are different, they are, in essence, required to compute some form of the reachability of states, and hence have a close relation with the emerging discipline of combinatorial reconfiguration. This talk aims to provide basic knowledge of these topics to make it possible to discuss how they are related to the combinatorial reconfiguration.

Combinatorial reconfiguration problems that have been traditionally discussed in discrete mathematics will be presented with an emphasis on the speaker's work and open problems, as well as computational aspects that have recently been introduced. Key concepts include the Hasse diagrams of partially ordered sets, the 1-skeleta of convex polytopes, and the Cayley graphs of finite groups. Those concepts will be introduced with an example of sorting, a fundamental problem in computer science. Then, connections of Catalan structures, linear programming and permutation groups with with combinatorial reconfiguration will be discussed.

This talk reviews known results on the independent set reconfiguration problem mainly from the viewpoints of graph classes and width parameters.