Computing H-Partitions in ASP and Datalog
This work addresses graph partitioning for computational logic researchers, but it is incremental as it focuses on implementation comparisons rather than new algorithms.
The paper tackles the problem of computing H-partitions in graphs by expressing existing polynomial-time algorithms in Datalog with stratified negation, and it finds through experiments that guess-and-check programs run faster than Datalog equivalents in the Clingo solver.
A $H$-partition of a finite undirected simple graph $G$ is a labeling of $G$'s vertices such that the constraints expressed by the model graph $H$ are satisfied. For every model graph $H$, it can be decided in non-deterministic polynomial time whether a given input graph $G$ admits a $H$-partition. Moreover, it has been shown by Dantas et al. that for most model graphs, this decision problem is in deterministic polynomial time. In this paper, we show that these polynomial-time algorithms for finding $H$-partitions can be expressed in Datalog with stratified negation. Moreover, using the answer set solver Clingo, we have conducted experiments to compare straightforward guess-and-check programs with Datalog programs. Our experiments indicate that in Clingo, guess-and-check programs run faster than their equivalent Datalog programs.