FY2022

• There are many real-world problems that can be formulated as combinatorial optimization problems. They tend to be NP-hard and are hard to solve exactly when the instance sizes are large. As a practical way to solve such problems, heuristic algorithms are often used to find good solutions, though not necessarily optimal, in a reasonable amount of time. Standard basic heuristic strategies include greedy methods and local search algorithms. Such basic strategies are often combined to make more sophisticated methods, called metaheuristics, to find better solutions using more computation time. This talk introduces some of our results on efficient heuristic algorithms based on such strategies.

  2023.02.06 Mon. 10:00-12:00

  35th CoRe Seminar
  Speaker :YAGIURA, Mutsunori (Nagoya U., invited talk) Title :Practical algorithms for combinatorial optimization problems Sumarry :
• An amidakuji (i.e., ladder lotteries, or Ghost Legs) consists of n vertical lines (lines for short) and some horizontal bars (bars for short), where lines have their labels, and each bar connects two lines. By regarding each bar as the exchange of the labels of a pair of lines, an amidakuji (i.e., the network of the lines and bars) represents a permutation. Amidakuji's also correspond to sorting networks, in which bars are regarded as comparators. An amidakuji corresponds to a primitive sorting network if every bar connects two consecutive lines. A rhombus tiling is a tiling of rhombuses of unit edge length without gap or overlap. In this talk, we begin with the relation between Amidakujis and rhombus tilings. Then, we move to the enumeration by the reverse search and ZDDs (Zero-Suppressed Binary Decision Diagrams).

  2023.01.16 Mon. 10:00-12:00

  34th CoRe Seminar
  Speaker :HORIYAMA, Takashi (Hokkaido U., invited talk) Title :Enumeration of amidakujis and rhombus tilings 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 :
• I will introduce the theoretical field of distributed computing to you in this talk by explaining recent results on two problems in the field. Specifically, I will talk about
   (i) the leader election problem in the population protocol model, and
   (ii) Byzantine gathering problem by mobile agents.

   

  The population protocol model represents a network consisting of tiny sensors that moves passibly (i.e., they constantly move, but cannot control their own move). This model was proposed by Angluin et al. in 2004 and has been intensively studied since then. In particular, the leader election problem and the majority problem are well studied. In this talk, I will discuss the former, that is, the leader election problem.

   

  Mobile agents are mobile entity that moves autonomously on a computer network. The gathering problem is a well-studied fundamental problem, which requires all agents to gather at a single node. In this talk, we will discuss a variant of this problem, i.e., the gathering problem with the assumption that some agents take arbitrary adversarial actions. 

  2022.12.05 Mon. 10:00-12:00

  33rd CoRe Seminar
  Speaker :SUDO, Yuichi (Hosei U., invited talk) Title :The theoretical field of distributed computing Sumarry :
• I am a researcher in the field of electric power and energy. I am researching mechanisms to maximize the introduction of renewable energy sources on the premise of ensuring safety, stable supply, economic efficiency, and environmental conservation. One of the issues in increasing the introduction of renewable energy sources is the degradation of power quality, which adversely affects social life. In this presentation, the mechanism and countermeasures for power quality degradation caused by renewable energy source will be described, and research to expand the amount of renewable energy sources that can be introduced will be introduced.

  2022.11.28 Mon. 10:00-12:00

  32nd CoRe Seminar
  Speaker :IIOKA, Daisuke (Chubu U., Group B01) Title :Development of electric power system based mainly on renewable energy sources Sumarry :
• Dynamical Systems is a field that studies the collective behavior of objects that update their states according to some rules. Discrete-Time Boolean Finite Dynamical System (DT-BFDS) is a subfield where the systems have some finite number of objects whose states are Boolean values, and the state updates occur in discrete time. In the subfield of DT-BFDS, researchers aim to (i) design models for capturing real-world phenomena and using the models to make predictions and (ii) develop simulation techniques for acquiring insights about the systems' behavior. Useful for both aims is understanding the system dynamics mathematically before executing the systems. Obtaining a mathematical understanding of BFDS is quite challenging, even for simple systems, because the state space of a system grows exponentially in the number of objects. Researchers have used computational complexity to circumvent the challenge. The complexity theoretic research in DT-BFDS has successfully produced complete characterizations for many dynamical problems.

   

  The DT-BFDS studies have mainly dealt with deterministic models, where the update at each time step is deterministic, so the system dynamics are completely determinable from the initial setting. However, natural systems have uncertainty. Models having uncertainty may lead to far-better understandings of nature. Although a few attempts have explored DT-BFDS with uncertainty, including stochastic initialization and tie-breaking, they have scratched only a tiny surface of models with uncertainty. The introduction of uncertainty can be through two schemes. One is the introduction of alternate update functions. The other is the introduction of alternate update schedules. In this talk, I present a set of new DT-BFDS models with uncertainty and present some initial results.
   

  2022.11.14 Mon. 10:00-12:00

  31st CoRe Seminar
  Speaker :OGIHARA, Mitsunori (U. Miami, invited talk) Title :A theory for discrete-time Boolean finite dynamical systems with uncertainty Sumarry :
• In the k-recoloring problem, we are given two (vertex-)colorings of a graph using k colors, and asked to transform one into the other by recoloring only one vertex at a time, while at all times maintaining a proper k-coloring. In this talk, we consider a (directed) recolorability constraint on the k colors, which forbids some pairs of colors to be recolored directly. The recolorability constraint is given in terms of a digraph, whose vertices correspond to the colors and whose arcs represent the pairs of colors that can be recolored directly. We provide algorithms for the problem based on the structure of the digraph, showing that the problem is solvable in linear time when the digraph is a directed cycle or is in a class of multitrees. This talk is based on joint work with Soichiro Fujii, Yuni Iwamasa, and Akira Suzuki.

  2022.10.31 Mon. 10:00-12:00

  30th CoRe Seminar
  Speaker :KIMURA, Kei (Kyushu U., invited talk) Title :Algorithms for coloring reconfiguration under recolorability digraphs Sumarry :
• The online bipartite matching problem is the problem of finding a maximum-size matching when vertices on one side arrive one by one. The problem has practical applications such as online advertisement, ride-sharing, and crowd sourcing. This talk proposes a variant of the problem motivated by such applications, and presents online algorithms with constant competitive ratio. This talk is based on joint work with Hanna Sumita, Shinji Ito, Kei Takemura, Daisuke Hatano, Takuro Fukunaga, Ken-ichi Kawarabayashi.

  2022.10.17 Mon. 10:00-12:00

  29th CoRe Seminar
  Speaker :KAKIMURA, Naonori (Keio U., Group C01) Title :Constrained online bipartite matching 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 :