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


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