Computing H-Partitions in ASP and Datalog
share
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.
READ FULL TEXT