Symposium

• Jun KAWAHARA (Kyoto U., Group B01) will give a talk in the organized session "Autonomous decision making under complex conditions or situations" of the 4th Asia Pacific Conference of the Prognostics and Health Management Society (PHMAP 2023). 

   

  2023.09.13 Wed. 14:00-14:20

  Jun Kawahara, Chuta Yamaoka, Takehiro Ito, Akira Suzuki, Daisuke Iioka, Shuhei Sugimura, Seiya Goto,  and Takayuki Tanabe

  "Algorithmic Study for Power Restoration in Electrical Distribution Networks"

   

  This talk will be based on the joint press release of our research project. The organized session will be held from 13:20 to 16:00, and 7 talks are scheduled. (PHMAP 2023 will be held on September 11-14.)

  2023.09.13 Wed. 13:20-16:00

  Talk in International conference "PHM Asia Pacific 2023"
  Speaker : Title : 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 a minisymposium on Combinatorial Reconfiguration in the 10th International Congress on Industrial and Applied Mathematics (ICIAM 2023). This minisymposium aims at communicating recent research trends on combinatorial reconfiguration and discussing possible future directions.

   

  Program and Registration

  • Program
  • Please make your registration for ICIAM 2023.  

   

  List of Speakers

  • Colin Defant (Massachusetts Institute of Technology, USA) * invited speaker
  • Irene Parada (Universitat Politècnica de Catalunya, Spain) * invited speaker
  • Nicholas Williams (Lancaster University, UK) * invited speaker
  • Takehiro Ito (Tohoku University, Japan)

   

  Talk Titles and Abstracts

  • [17:40-18:05]  Takehiro Ito (Tohoku University, Japan)

  Title: Invitation to Combinatorial Reconfiguration

  Abstract: Combinatorial Reconfiguration studies reachability and related questions over combinatorial structures. A typical example asks if the solution space of a Boolean formula is connected with respect to the Boolean cube topology, formed by flipping one bit at the time. Reconfiguration problems have motivation from a variety of fields such as puzzles, statistical physics and industry, and have been studied intensively in this decade from the algorithmic viewpoints. In this talk, we will give a broad introduction of combinatorial reconfiguration, and show some recent progress on the topic.

   

  • [18:05-18:30]  Irene Parada (Universitat Politècnica de Catalunya, Spain) * invited speaker

  Title: Geometric Algorithms for Modular Robotics

  Abstract: Modular self-reconfigurable robots consist of individual units that can move and connect to one another to form a larger, more complex shape. A central problem that arises is how to efficiently reconfigure these robots from one shape to another while maintaining connectivity.

  We will explore the computational complexity of the reconfiguration problem for the most fundamental lattice-based models of modular robots. Specifically, we will examine how the reconfiguration problem differs depending on the lattice and movement capabilities of the units. We will discuss efficient algorithms for universal reconfiguration in some models, while in others the problem is PSPACE-complete, which means that it is computationally intractable. For those cases, we identify simple conditions that allow for efficient reconfiguration.

  Overall, this talk will provide insights into the challenges of reconfiguring modular robots and demonstrate how geometric and graph algorithms can help us tackle this problem.

   

  • [18:30-18:55]  Colin Defant (Massachusetts Institute of Technology, USA) * invited speaker

  Title: Toric Promotion and Permutoric Promotion

  Abstract: We introduce toric promotion as a cyclic variant of Schutzenberger's famous promotion operator. Toric promotion acts on the labelings of a graph G; it is defined as the composition of certain toggle operators, listed in a natural cyclic order. We will show that the orbit structure of toric promotion is surprisingly nice when G is a forest. We then consider more general permutoric promotion operators, which are defined as compositions of the same toggle operators, but in permuted orders. When G is a path graph, we provide a complete description of the orbit structures of all permutoric promotion operators, showing that they satisfy the cyclic sieving phenomenon. Our proof is surprisingly involved and relies on the analysis of gliding globs, sliding stones, and colliding coins. The work on permutoric promotion is joint with Rachana Madhukara and Hugh Thomas.

   

  • [18:55-19:20]  Nicholas Williams (Lancaster University, UK) * invited speaker

  Title: Triangulations of Cyclic Polytopes Through the Lens of Reconfiguration

  Abstract: We discuss the reconfiguration problem given by taking the set of triangulations of a cyclic polytope as the state space, with the reconfiguration moves given by bistellar flips (the higher-dimensional analogue of flipping a diagonal within a quadrilateral). The state space is connected, and we will outline how this is proven using a certain partial order on the states called the higher Stasheff-Tamari order. We will further consider as many different other aspects of the reconfiguration as time permits, including the significance of triangulations of higher-dimensional cyclic polytopes for reconfigurations of lower-dimensional cyclic polytopes, efficient combinatorial descriptions of triangulations of cyclic polytopes, and the diameter of the state space.

   

  Organizers

  • Takehiro Ito (Tohoku University, Japan)
  • Yusuke Kobayashi (Kyoto University, Japan)
  • Yoshio Okamoto (The University of Electro-Communications, Japan)

   

  2023.08.22 Tue. 17:40-19:20

  Minisymposium on Combinatorial Reconfiguration in ICIAM 2023
  Speaker : Title : Sumarry :
• We will organize the 3rd workshop on Combinatorial Reconfiguration, affiliated with the 50th International Colloquium on Automata, Languages, and Programming (ICALP2023).

   

  • Program and Registration

  Program

  This workshop will be held as a pure face-to-face event. To attend our workshop, please make a registration for ICALP workshops. 

   

  • Aim and Scope

  Combinatorial Reconfiguration studies reachability and related questions over combinatorial structures. These types of questions arise in many areas of mathematics, computer science, and related fields. A typical example asks if the solution space of a Boolean formula is connected with respect to the Boolean cube topology, formed by flipping one bit at the time. Another example of a well-studied application is sampling from a very large configuration space by simulating a Markov chain involving local reconfigurations. Although there is now a wealth of publications on many aspects of Combinatorial Reconfiguration, including a general framework, many questions remain open. The study of Combinatorial Reconfiguration brings together problems and techniques from a variety of fields in mathematics and computer science, such as combinatorial game theory, graph and hypergraph theory, enumeration, probability theory, random sampling via Markov Chain Monte Carlo methods, bioinformatics, complexity theory, discrete geometry, statistical physics, and many others.

   

  With the success of the workshops affiliated with ICALP 2021 and ICALP 2022, this workshop aims at strengthening relations among researchers in various fields of theoretical computer science and mathematics, and broadening interest in Combinatorial Reconfiguration to a wider audience. Two invited talks by leading experts are planned as a way to build bridges to closely-related fields. We also plan to report the results of the 2nd Combinatorial Reconfiguration Challenge (CoRe Challenge 2023) during the workshop.
  https://core-challenge.github.io/2023/

  
  The workshop is planned to be held in person in Paderborn.

   

  The workshop is held in cooperation with JSPS KAKENHI project "Fusion of Computer Science, Engineering and Mathematics Approaches for Expanding Combinatorial Reconfiguration."
  https://core.dais.is.tohoku.ac.jp/en/

   

  • Invited Speakers

  - Marthe Bonamy (Université de Bordeaux, France)
  - Jun Kawahara (Kyoto University, Japan)

   

  • Call for Contributed Talks and Submission Guideline

  Authors are invited to submit original work that is related to any aspect or application of Combinatorial Reconfiguration. Any work already or not yet published is welcome. Presentations of ongoing work and open problems, as well as challenges, are encouraged. Short survey talks are also welcome.
  
  The submission must be formatted in one page that contains the title of the work, the list of all authors, an email address of the corresponding author, and a brief summary of the presentation. The manuscript must be prepared with the following template as a PDF file.
  http://www.dais.is.tohoku.ac.jp/core2023template.zip
  
  Even though there will be no strict formal refereeing process, some contributions might not be accepted at the discretion of the Program Committee. A collection of one-page abstracts will be distributed to the workshop participants only. Submission should be done via EasyChair.
  https://easychair.org/conferences/?conf=core2023

   

  • Important Dates

  - Submission deadline: April 22, 23:59 AoE (extended to) May 7, 23:59 AoE
  - Notification: May 8 (extended to) May 12

  (- Early registration deadline for ICALP 2023: May 15, 23:59 CET)
  - Camera-ready version due: June 19, 23:59 AoE
  - Date of workshop: July 10, 2023

   

  • Program Committee

  - Nicolas Bousquet, CNRS, Université Lyon 1, France
  - Takehiro Ito, Tohoku University, Japan (Chair)
  - Naomi Nishimura, University of Waterloo, Canada
  - Yoshio Okamoto, The University of Electro-Communications, Japan
  - Akira Suzuki, Tohoku University, Japan

   

  • Organizing Committee

  - Takehiro Ito, Tohoku University, Japan (Chair)
  - Yoshio Okamoto, The University of Electro-Communications, Japan
  - Akira Suzuki, Tohoku University, Japan

   

  2023.07.10 Mon.

  3rd Workshop on Combinatorial Reconfiguration, affiliated with ICALP 2023
  Speaker : Title : 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 "Combinatorial Reconfiguration and Fixed-Parameter Tractability" via Zoom on December 12, 2022 (based on European Timezone).

  
  The objective is to learn recent developments of fixed-parameter (in)tractability and their relations with combinatorial reconfiguration. In her influential survey paper "Introduction to Combinatorial Reconfiguration" (Algorithms 2018), Naomi Nishimura dedicated one section to applications of the parameterized complexity methodology to problems on combinatorial reconfiguration. Indeed, several papers have been presented along this line of research. Furthermore, the research activity on fixed-parameter (in)tractability has been quite active, and there are a lot of recently introduced methods that are waiting for being applied to combinatorial reconfiguration. In this workshop, we will learn recent research trends of fixed-parameter tractability and combinatorial reconfiguration, and will discuss a new connection between these two fields of theoretical computer science.

   

  This workshop aims at the broad audience of discrete mathematics and theoretical computer science, who wish to learn and work on these active research areas.

   

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

   

  List of Confirmed Invited Speakers

  • Hans L. Bodlaender (Utrecht University, the Netherlands)
  • Bart M. P. Jansen (Eindhoven University of Technology, the Netherlands)
  • Eun Jung Kim (Paris-Dauphine University, France)
  • Moritz Mühlenthaler (Université Grenoble Alpes, France)
  • Saket Saurabh (The Institute of Mathematical Sciences, India)
     

  Registration

  Registration is free of charge, but please make your registration in advance. 

   

  Program

  2022.12.12 Mon.  CET (JST)

  08:55-09:00 (16:55-17:00)	Welcome address
  09:00-10:00 (17:00-18:00)	Eun Jung Kim (Paris-Dauphine University, France) Twin-Width and Its Implications
  10:15-11:15 (18:15-19:15)	Moritz Mühlenthaler (Université Grenoble Alpes, France) Constraint Satisfaction Reconfiguration
  11:15-13:00 (19:15-21:00)	Lunch/Dinner Break
  13:00-14:00 (21:00-22:00)	Saket Saurabh (The Institute of Mathematical Sciences, India) FPT Approximation Schemes for the Maximum Coverage and MAX-SAT Problem
  14:15-15:15 (22:15-23:15)	Bart M. P. Jansen (Eindhoven University of Technology, the Netherlands) Search Space Reduction Beyond Kernelization
  15:30-16:30 (23:30-24:30)	Hans L. Bodlaender (Utrecht University, the Netherlands) Parameterized Complexity of Reconfiguration of Small Independent Sets and Dominating Sets

   

  Talk Titles and Abstracts

  • 09:00-10:00 (17:00-18:00)

  Eun Jung Kim (Paris-Dauphine University, France)

  Title: Twin-Width and Its Implications

  Abstract: First Order Logic (FO logic) expresses many classic computational problems such as k-Independent Set problem with variables and logical connectives. First Order model checking is known to be fixed-parameter tractable on important classes such as nowhere dense classes, bounded rank-width graphs, unit interval graphs as well as strict hereditary classes of permutations. A notion called twin-width, introduced by Bonnet, Kim, Thomassé, Watrigant (FOCS 2020), elegantly captures vast swathes of such classes, and provides a new perspective to explain why so many computational problems are fixed-parameter tractable on graph classes seemlying so different. We will briefly sketch the new notion, and its rapidly developing impact in theoretical computer science with an emphasis on algorithm designs.

   

  • 10:15-11:15 (18:15-19:15)

  Moritz Mühlenthaler (Université Grenoble Alpes, France)

  Title: Constraint Satisfaction Reconfiguration

  Abstract: The constraint satisfaction problem (CSP) asks for an assignment of values to variables such that given constraints are satisfied. Special cases of the CSP are for example graph coloring and Boolean satisfiability. We consider the following reconfiguration variant of the CSP: given two feasible solutions of a CSP instance, can we transform one solution into the other by changing the value of a single variable at a time, such that in each step the constraints are satisfied? We give an overview of what is known about the complexity of this question and highlight the techniques behind recent algorithmic results.

   

  • 13:00-14:00 (21:00-22:00)

  Saket Saurabh (The Institute of Mathematical Sciences, India)

  Title: FPT Approximation Schemes for the Maximum Coverage and MAX-SAT Problem

  Abstract: Vertex Cover is a classical NP-hard problem. Partial Vertex Cover is a variant of the Vertex Cover problem where the goal is to maximize the number of edges covered, given a fixed number of vertices that can be used. Partial Vertex Cover is a W[1]-hard problem. There are FPT approximation schemes for Partial Vertex Cover parameterized by the solution size, i.e.,  there are $(1-\epsilon)$-factor approximation algorithms running in time $f(k,\epsilon) n^{O(1)}$ for all $0<\epsilon<1$. In this talk, we consider the Partial Vertex Cover problem and SAT problems in hypergraphs where there is no bound on the size of the hyperedges. We design an FPT approximation scheme for these problems on hypergraphs that satisfies the Kij-free property, i.e., no $i$ vertices are contained in $j$ common hyperedges. 

   

  • 14:15-15:15 (22:15-23:15)

  Bart M. P. Jansen (Eindhoven University of Technology, the Netherlands)

  Title: Search Space Reduction Beyond Kernelization

  Abstract: The framework of kernelization gives a mathematical model for the rigorous analysis of preprocessing, aimed at showing that any instance with parameter k can efficiently be reduced to an equivalent one whose size depends only on k. Kernelization serves as a useful tool to obtain FPT algorithms, since any brute-force algorithm solves the reduced instance in time depending only on k. However, from the definition of kernelization it is not clear why kernelization would lead to significant speed-ups when the reduced instance is not solved by brute force, but by a fixed-parameter tractable algorithm whose running time is governed by the value of the parameter. To speed up such algorithms, it is the parameter controlling the size of the search space which should decrease, rather than the encoding size of the input. The discrepancy between reducing the instance size versus decreasing the search space is the focus of this talk. The quest for preprocessing algorithms that reduce the search space leads to a new type of algorithmic and graph-theoretical questions. The talk gives an introduction to this budding line of inquiry by presenting examples from recent work on the search for essential vertices and antler structures in graphs.
  Based on joint work with Benjamin M. Bumpus, Huib Donkers, and Jari J.H. de Kroon.

   

  • 15:30-16:30 (23:30-24:30)

  Hans L. Bodlaender (Utrecht University, the Netherlands)

  Title: Parameterized Complexity of Reconfiguration of Small Independent Sets and Dominating Sets

  Abstract: In this talk, we look at the complexity of reconfiguring independent or dominating sets, where we assume that the size of the sets is a small parameter k, under different rules of moving the "tokens". It appears that the parameterized complexity depends on the assumption of how the number of moves that can be made is specified, but less on the type of moves.
  Some related literature is also reviewed.

   

  Organizers

  • Takehiro Ito (Tohoku University, Japan)
  • Yoshio Okamoto (The University of Electro-Communications, Japan)
  • Yota Otachi (Nagoya University, Japan)

   

  2022.12.12 Mon.

  Workshop "Combinatorial Reconfiguration and Fixed-Parameter Tractability"
  Speaker : Title : Sumarry :
• 2022.09.02 Fri.

  Workshop "Polytope Diameter and Related Topics"
  Speaker : Title : Sumarry :
• We will organize a mini-symposium on combinatorial reconfiguration in Japanese Conference on Combinatorics and its Applications 2022 (JCCA-2022).

   

  10:50--11:20
  Hiroshi Eto (Tohoku U.), Takehiro Ito (Tohoku U.), Yasuaki Kobayashi (Hokkaido U.), Shun-ichi Maezawa (Tokyo U. Science), Yota Otachi (Nagoya U.), and Kunihiro Wasa (Hosei U.)
  "Induced Matching Reconfiguration on Trees"
   
  11:20--11:50
  Tatsuya Gima (Nagoya U.), Takehiro Ito (Tohoku U.), Yasuaki Kobayashi (Hokkaido U.), and Yota Otachi (Nagoya U.)
  "Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited"
   
  14:00--14:30
  Kento Nakada (Okayama U.)
  "Combinatorial game theory ---Extension from Nim and Sato's game to INSET game---"
   
  14:30--15:00
  Takehiro Ito (Tohoku U.), Jun Kawahara (Kyoto U.), Shin-ichi Minato (Kyoto U.), Yota Otachi (Nagoya U.), Toshiki Saitoh (Kyushu Institute of Technology), Akira Suzuki (Tohoku U.), Ryuhei Uehara (JAIST), Takeaki Uno (NII), Katsuhisa Yamanaka (Iwate U.), and Ryo Yoshinaka (Tohoku U.)
  "Computational Complexity of Ball/Water Sort Puzzles"

   

  2022.08.17 Wed. 10:50-15:00

  JCCA-2022 Mini-Symposium
  Speaker : Title : Sumarry :
• We will organize the 2nd workshop on Combinatorial Reconfiguration, affiliated with the 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022).

   

  • Program and Registration

  Program

  Registration for Zoom

  If you will attend our workshop virtually, you don't need to make an ICALP registration for our workshop: our workshop is free of charge for virtual participants.

  For on-site participants, it is not obligatory to register for the Zoom meeting. Nevertheless, we kindly recommend you to register. The collection of abstracts is planned to be shared through the Zoom meeting, and the compilation of the list of participants will be easier for the organizers if you register.

   

  • Aim and Scope

  Combinatorial Reconfiguration studies reachability and related questions over combinatorial structures. These types of questions arise in many areas of mathematics, computer science, and related fields. A typical example asks if the solution space of a Boolean formula is connected with respect to the Boolean cube topology, formed by flipping one bit at a time. Another example of a well-studied application is sampling from a very large configuration space by simulating a Markov chain involving local reconfigurations. Although there is now a wealth of publications on many aspects of Combinatorial Reconfiguration, including a general framework, many questions remain open. The study of Combinatorial Reconfiguration brings together problems and techniques from a variety of fields in mathematics and computer science, such as combinatorial game theory, graph and hypergraph theory, enumeration, probability theory, random sampling via Markov Chain Monte Carlo methods, bioinformatics, complexity theory, discrete geometry, statistical physics, and many others.

  
  With the success of the 1st workshop affiliated with ICALP 2021, this workshop aims at strengthening relations among researchers in various fields of theoretical computer science and mathematics, and broadening interest in Combinatorial Reconfiguration to a wider audience. Two invited talks by leading experts are planned as a way to build bridges to closely-related fields. We also plan to have the award ceremony for the 1st Combinatorial Reconfiguration Challenge (CoRe Challenge 2022) during the workshop. 
  https://core-challenge.github.io/2022/

  
  The workshop is planned to be held in person in Paris, but participants have the option to join online. However, because of the future uncertainty, we may opt for a fully online workshop, even if ICALP itself is held in person.

  
  The workshop is held in cooperation with JSPS KAKENHI project "Fusion of Computer Science, Engineering and Mathematics Approaches for Expanding Combinatorial Reconfiguration."
  https://core.dais.is.tohoku.ac.jp/en/

   

  • Invited Speakers

  - Catherine Greenhill (UNSW Sydney, Australia)
  - Amer E. Mouawad (American University of Beirut, Lebanon)

   

  • Call for Contributed Talks and Submission Guideline

  Authors are invited to submit original work that is related to any aspect or application of Combinatorial Reconfiguration. Any work already or not yet published is welcome. Presentations of ongoing work and open problems, as well as challenges, are encouraged. Short survey talks are also welcome.

  
  The submission must be formatted in one page that contains the title of the work, the list of all authors, an email address of the corresponding author, and a brief summary of the presentation. The manuscript must be prepared with the following template as a PDF file.
  http://www.dais.is.tohoku.ac.jp/core2022template.zip

  
  There will be no formal refereeing process. A collection of one-page abstracts will be distributed to the workshop participants only. Submission should be done via EasyChair.

  https://easychair.org/conferences/?conf=core2022

   

  • Important Dates

  - Submission deadline: May 11, 23:59 AoE
  - Notification: May 25
  - Camera-ready version due: June 13, 23:59 AoE
  - Date of workshop: July 4, 2022

   

  • Program Committee

  - Nicolas Bousquet, CNRS, Universite Lyon 1, France
  - Takehiro Ito, Tohoku University, Japan (Chair)
  - Jun Kawahara, Kyoto University, Japan
  - Naomi Nishimura, University of Waterloo, Canada
  - Yoshio Okamoto, The University of Electro-Communications, Japan
  - Akira Suzuki, Tohoku University, Japan

   

  • Organizing Committee

  - Takehiro Ito, Tohoku University, Japan (Chair)
  - Jun Kawahara, Kyoto University, Japan
  - Clément Legrand-Duchesne, Université de Bordeaux, France
  - Yoshio Okamoto, The University of Electro-Communications, Japan
  - Akira Suzuki, Tohoku University, Japan

  2022.07.04 Mon.

  2nd Workshop on Combinatorial Reconfiguration, affiliated with ICALP 2022
  Speaker : Title : 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 :
• 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 :
• 2021.08.30 Mon.

  Workshop "Combinatorial Reconfiguration in Discrete and Computational Geometry"
  Speaker : Title : Sumarry :