Twin-Width SAT-Solver for PACE’23
שירז שי וינון חורב
:שמות הסטודנטים המציגים
ד"ר כהן שראל
שיתופי פעולה במחקר
In this project, we have embarked on an international collaboration to investigate the NP-hard problem of twin-width graph invariant, a concept introduced by Bonnet, Kim, Thomasse ́, and Watrigan. Comprising of an international research team, including Dr. Lior Kama and Dr. Sarel Cohen from The Academic College of Tel Aviv-Yaffo, along with Dr. Davis Issac, Dr. Kirill Simonov, and Katerina Niklanovits from Potsdam University, Germany, we have leveraged a practical approach to address this challenging NP-hard problem. The project focuses on creating a preprocessing algorithm for efficient generation of prime-module decompositions of graphs, thereby reducing the problem size by calculating the twin-width only for each prime factor. Further, we converted the NP-hard problem into a SAT formula, and utilized cutting-edge SAT solvers to efficiently derive solutions for the twin-width problem. Throughout the project, we maintained consistent collaboration through weekly meetings, developed algorithms to tackle problems specific to this issue, and finally submitted our software solution to the PACE 2023 challenge. This effort signifies our contribution to resolving this complex problem, offering solutions to this computational challenge. We concluded our research by writing a paper containing our innovative algorithm and benchmarking results to a top-tier A* conference (AAAI).