An Introduction to Combinatorial Reconfiguration

Thời gian: 14:30 đến 15:30 Ngày 12/03/2024

Địa điểm: C101, VIASM

Báo cáo viên/ Speaker's name: Hoàng Anh Đức, Đại học Khoa học tự nhiên, Đại học Quốc gia Hà Nội

Abstract:

For the last few decades, "Combinatorial Reconfiguration" has emerged in different areas of computer science. In a reconfiguration variant of a computational problem (e.g.,Satisfiability, Independent Set, Vertex-Coloring, etc.), a transformation rule that describes an adjacency relation between feasible solutions (e.g., satisfying truth assignments, independent sets, proper vertex-colorings, etc.) of the problem is given. Another way of looking at these reconfiguration problems is via the so-called reconfiguration graph (or solution graph)--a graph whose nodes are feasible solutions and two nodes are joined by an edge if one can be obtained from the other by applying the given rule exactly once. A typical example is the well-known classic Rubik's cube puzzle, where each configuration of the cube corresponds to a feasible solution, and two configurations (solutions) are adjacent if one can be obtained from the other by rotating a face of the cube by either 90, 180, or 270 degrees. A classic question is, given two feasible solutions S and T, whether there exists a sequence of adjacent feasible solutions between them. In the corresponding reconfiguration graph, this question is equivalent to deciding whether there is a path between two nodes S and T. In this talk, I will briefly introduce this research area and discuss some reasons why I think reconfiguration problems are important and worth studying.

Hình thức tổ chức/ Seminar format: Trực tiếp/On-site