C01

• 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 :
• In this talk, I consider a matching in a bipartite graph in which each vertex has a preference over the edges incident to it. Especially, I focus on a Pareto stable matching, which is a matching satisfying stability and Pareto efficiency. In talk, I give a survey of a Pareto stable matching including my recent result. I also talk about the relationship between Pareto stable matchings and combinatorial reconfiguration.

  2022.4.25 Mon. 15:00-17:00

  23rd CoRe Seminar
  Speaker :KAMIYAMA, Naoyuki (Kyushu U., Group C01) Title :Pareto stable matchings 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 :
• Topology, one of the speaker's main research interests, is the study of the properties of "shapes" and "spaces." Ideas and methods of solving problems coming from topology are becoming more and more influential to all other branches of mathematics. More recently, the word "topological" has also starting to appear outside the mathematical world. One of the advantages of topological methods is that they provide a tool to turn some geometric data into some algebraic ones such as groups. In this talk, the speaker would like to give the audience some ideas on how one might think as a topologist through concrete examples. The speaker will also mention some related topics motivated by a current project on combinatorial reconfiguration.
   

  2021.07.26 Mon. 10:00-12:00

  14th CoRe Seminar
  Speaker :NOZAKI, Yuta (Hiroshima U., Group C01) Title :From the viewpoint of topology Sumarry :
• The constraint satisfaction problem (CSP) is the problem of determining if there exists an assignment of values to variables so that all given constraints are satisfied. While the CSP is NP-complete in general, a restriction on relations appearing in constraints can ensure the polynomial-time solvability. In 1998, Feder and Vardi conjectured that a problem obtained from such a restriction is either in P or NP-complete, which is called the dichotomy conjecture. This was settled affirmatively by Bulatov and by Zhuk in 2017. In this talk, I will give a brief overview of an algebraic approach to CSPs that plays an important role in the proofs of the dichotomy conjecture.

  2021.06.07 Mon. 10:00-12:00

  11th CoRe Seminar
  Speaker :IWAMASA, Yuni (Kyoto U., Group C01) Title :An algebraic approach to constraint satisfaction problems Sumarry :
• 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.
   

  2021.04.26 Mon. 10:00-12:00

  8th CoRe Seminar
  Speaker :MAEZAWA, Shun-ichi (U. Electro-Communications, Group C01) Title :Subgraphs with certain conditions in edge-colored graphs Sumarry :
• 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.

  2021.02.12 Fri. 15:00-17:00

  6th CoRe Seminar
  Speaker :OZEKI, Kenta (Yokohama National U., Group C01) Title :Reconfiguration problem of 3-edge-colorings in cubic graphs Sumarry :
• 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.

  2020.12.25 Fri. 15:00-17:00

  4th CoRe Seminar
  Speaker :OKAMOTO, Yoshio (U. Electro-Communications, Group C01) Title :Combinatorial reconfiguration and discrete structures Sumarry :