Dr. techn. Ing. Jan Legerský

Dr. techn. Ing. Jan Legerský

Mgr. Michal Opler, Ph.D.

Department of Theoretical Computer Science

One of the questions in Rigidity Theory is whether a realization of the vertices of a graph in the plane is flexible, namely, if it allows a continuous deformation preserving the edge lengths. A flexible realization of a connected graph in the plane exists if and only if the graph has a NAC-coloring, which is surjective edge coloring by two colors such that for each cycle either all the edges have the same color or there are at least two edges of each color. While it is known that it is NP-complete to decide if a graph has a NAC-coloring, we show that the problem is also NP-complete for graphs with maximum degree five. We present a significantly faster algorithm with an implementation for NAC-coloring search, and we discuss related heuristics. The performance is compared with previous algorithms and among the heuristics. We also present fixed-parameter tractable (FPT) algorithm for NAC-coloring counting parametrized by treewidth. We discuss relation to stable cuts and an algorithm for finding a stable cut is implemented as part of the thesis.

Dr. techn. Ing. Jan Legerský

Dr. Rodrigo Augusto da Silva Alves

Department of Applied Mathematics

This thesis focuses on the application of reinforcement learning to rigidity theory. The goal of this thesis is to reimplement an evolutionary deep reinforcement learning algorithm, the deep cross-entropy method, and apply it to rigidity theory. In 2021 Adam Zsolt Wagner applied this algorithm to disprove some open conjectures by constructing counterexamples. This algorithm maximizes some evaluation function and the ultimate goal of this thesis is to find a minimally rigid graph with a high number of realizations in the plane. Rigidity theory is a branch of mathematics that studies graphs and their property of being rigid. A realization of a graph is a map of vertices to the plane. A realization with a graph is considered rigid if it can not be continuously deformed without changing the lengths of the edges. Rigidity is a property of the graph when using a generic realization. There exists an implementation that computes the number of realizations for a given minimally rigid graph which is utilized in this work. The numbers of realizations have been previously computed by other researchers for all minimally rigid graphs with up to 14 vertices. For bigger graphs, only lower bounds on the maximum number exist. All the best known graphs with up to 15 vertices were found in this thesis and in significantly less time. The outcomes of this thesis are multiple efficient reimplementations of the deep cross-entropy method in the form of Python scripts. Two reimplementations were created for reproducing Wagner's results and are generic so that they can be used for other tasks. It is shown that they are approximately 50 times faster than the original one created by Wagner. Other two implementations are specialized for constructing minimally rigid graphs with a high number of realizations. All implementations are parallelized and easily deployed on a server with a high number of CPU cores leveraging all available computational resources.