FY2021

• 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.

  2022.01.20 Thu. 10:00-12:00

  21st CoRe Seminar
  Speaker :KOBAYASHI, Yasuaki (Kyoto U., Group A01) Title :Finding diverse solutions in combinatorial optimization problems Sumarry :
• 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. 

  2022.01.06 Thu. 10:00-12:00

  20th CoRe Seminar
  Speaker :OHSAKA, Naoto (CyberAgent, Inc., invited talk) Title :On reconfigurability of target sets Sumarry :
• 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.

  2021.12.16 Thu. 10:00-12:00

  19th CoRe Seminar
  Speaker :YAMANAKA, Katsuhisa (Iwate U., invited talk) Title :Enumeration and reconfiguration of ladder lotteries Sumarry :
• As a part of the research project "Fusion of Computer Science, Engineering and Mathematics Approaches for Expanding Combinatorial Reconfiguration" (head investigator: Takehiro Ito), we are going to organize Workshop "Graph Theory for Combinatorial Reconfiguration" via Zoom on November 29 (based on European Timezone). 

   

  A basic idea is to share fundamental concepts in graph theory that can be potentially applied for combinatorial reconfiguration problems and identify future research directions. In graph theory, combinatorial reconfiguration has been widely used; Reduction of graphs such as deletion and contraction of edges in graph minors; Kempe chains in graph coloring, which give important insights to a proof of the Four Color Theorem; and Diagonal flips of triangulations. This workshop aims at the broad audience of discrete mathematics and theoretical computer science, who wish to learn and work on this active research area. 

   

  The program will be exclusively composed of invited talks. Each talk is planned to span one hour, including discussion.

   

  List of Confirmed Invited Speakers

  • Maria Chudnovsky (Princeton University, USA) 
  • Zdeněk Dvořák (Charles University, Czech Republic) 
  • Tomáš Kaiser (University of West Bohemia, Czech Republic) 
  • Atsuhiro Nakamoto (Yokohama National University, Japan) 
  • Jakub Przybyło (AGH University of Science and Technology, Poland)
  • Zi-Xia Song (University of Central Florida, USA) 

   

  Program, Talk Abstracts, and Registration

  • Program
  • Talk abstracts
  • Registration is free of charge, but please make your registration in advance. 

   

  Organizers

  • Shun-ichi Maezawa (The University of Electro-Communications, Japan) 
  • Kenta Ozeki (Yokohama National University, Japan) 

   

  2021.11.29 Mon.

  Workshop "Graph Theory for Combinatorial Reconfiguration"
  Speaker : Title : Sumarry :
• 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.
   

  2021.11.25 Thu. 10:00-12:00

  18th CoRe Seminar
  Speaker :UEHARA, Ryuhei (JAIST, invited talk) Title :History of puzzles from the viewpoint of combinatorial reconfiguration Sumarry :
• 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.

  2021.11.11 Thu. 10:00-12:00

  17th CoRe Seminar
  Speaker :KOBAYASHI, Yusuke (Kyoto U., Group C01) Title :Reconfiguration of graph orientations with connectivity constraints Sumarry :
• 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.

  2021.10.21 Thu. 10:00-12:00

  16th CoRe Seminar
  Speaker :NAKAHATA, Yu (NAIST) Title :Token sliding on directed graphs Sumarry :
• The Maximum Induced Subgraph problem with Property P is one of graph optimization problems. In the problem, we find a maximum cardinality induced subgraph satisfying some property P. By setting the property P appropriately, we can formulate many graph optimization problems as the Maximum Induced Subgraph problem. For example, if the property is "induced subgraph is an independent set," the problem is equivalent to the Maximum Independent Set problem. A property P of graph G is said to be hereditary whenever a graph G satisfies the property P and any induced subgraph of G also satisfies the same property P. It is known that the Maximum Induced Subgraph problem with hereditary property is extremely hard to approximate. In this talk, I will talk about the Maximum Induced Subgraph problem with non-hereditary property, in particular, "induced subgraph is regular." 

  2021.10.07 Thu. 10:00-12:00

  15th CoRe Seminar
  Speaker :ETO, Hiroshi (Tohoku U., Group A01) Title :The complexity of maximum induced subgraph problem with some properties Sumarry :
• 2021.09.01 Wed. 14:00-16:30

  3rd CoRe Project Meeting
  Speaker : Title : Sumarry :
• Invited Talk:
  IKEGAMI, Atsuko (Seikei U.)
  Diversity and similarity of solutions in nurse scheduling

  2021.09.01 Wed. 14:00-16:30

  3rd CoRe Project Symposium
  Speaker : Title : Sumarry :