# Computing H-Partitions in ASP and Datalog

arXiv: https://arxiv.org/abs/2202.03730 · HTML: https://mlsanity.com/paper/2202.03730/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 14 references that are in the map.
- First posted on arXiv 8 Feb 2022.

## Builds on (most cited first, 1 of 1)

- [Clingo = ASP + Control: Preliminary Report](https://mlsanity.com/paper/1405.3694/) (2014)

## Abstract (arXiv)

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.