Accepted paper at IJCAI 2019

The work proposes the use of declarative solvers for enumerating potential maximal cliques in the context of exact algorithms for computing notions of width that characterize tractable fragments in a variety of NP-hard problem settings.

The paper Enumerating Potential Maximal Cliques via SAT and ASP by Tuukka Korhonen, Jeremias Berg, and Matti Järvisalo of the  has been accepted for publication in the proceedings of the (IJCAI 2019). 

The Bouchitté-Todinca algorithm (BT), operating dynamic programming over the so-called potential maximal cliques (PMCs), yields a practically efficient approach to treewidth and generalized hypertreewidth. The enumeration of PMCs is a scalability bottleneck for BT in practice. The paper proposes the use of declarative solvers for PMC enumeration as a substitute for the specialized PMC enumeration algorithms employed in current BT implementations. The presented Boolean satisfiability (SAT) and answer set programming (ASP) based PMC enumeration approaches open up new possibilities for improving the efficiency of BT in practice.

IJCAI is a top conference world-wide in the general field of artificial intelligence research.