=Paper=
{{Paper
|id=Vol-3193/paper1ASPOCP
|storemode=property
|title=Computing H-Partitions in ASP and Datalog
|pdfUrl=https://ceur-ws.org/Vol-3193/paper1ASPOCP.pdf
|volume=Vol-3193
|authors=ChloΓ© Capon,Nicolas Lecomte,Jef Wijsen
|dblpUrl=https://dblp.org/rec/conf/iclp/CaponLW22
}}
==Computing H-Partitions in ASP and Datalog==
https://ceur-ws.org/Vol-3193/paper1ASPOCP.pdf
Computing H-Partitions in ASP and Datalog
ChloΓ© Capon, Nicolas Lecomte and Jef Wijsen
University of Mons, Mons, Belgium
Abstract
An π»-partition of a finite undirected simple graph πΊ is a labeling of πΊβs vertices such that the constraints
expressed by the model graph π» are satisfied. These constraints concern the adjacency or nonadjacency of
vertices depending on their label. For every model graph π», it can be decided in non-deterministic polynomial
time whether a given input graph πΊ admits an π»-partition. Moreover, it has been shown in [1] 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 π»-partitions can be expressed in Datalog with stratified negation. Moreover, using
the answer set solver Clingo [2, 3], 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.
Keywords
Answer Set Programming, Datalog, logic programming, graph partitioning
1. Introduction
Answer Set Programming (ASP) is a powerful programming paradigm that allows for an easy encoding
of decision problems in NP. If the answer to a problem in NP is βyes,β then, by definition, there is a
βyesβ-certificate of polynomial size that can be checked in polynomial time. In an ASP guess-and-check
program, a programmer first declares the format of such a certificate, and then specifies the constraints
that a well-formatted certificate should obey in order to be a βyesβ-certificate. For example, for the
well-known problem SAT, an ASP-programmer can first declare that certificates take the form of
truth assignments, and then specify that βyesβ-certificates are those certificates that leave no clause
unsatisfied.
While ASP guess-and-check programs are typically oriented towards NP-complete problems, they
can also be used for problems in P. For example, the previously mentioned encoding of SAT also solves
2SAT, which is known to be in P. In general, assume that we have an answer set solver at our disposal,
and that we have written a guess-and-check ASP program for a particular problem that is NP-complete
(for example, SAT). Assume furthermore that we know that under some restrictions, the problem can be
solved in polynomial time (for example, the restriction of SAT to 2SAT). In logic programming, it may
be possible to encode such a polynomial-time solution in a syntactic restriction of ASP, for example, in
Datalog with stratified negation [4], which guarantees the existence of a polynomial-time execution.
From a theoretical standpoint, a program in Datalog is more efficient than a general guess-and-check
ASP program. From a practical standpoint, however, one may wonder whether such a Datalog program
will run faster in our ASP engine, compared to a general guess-and-check ASP program. The latter
question will be addressed in this paper.
ASPOCP 2022: 15th Workshop on Answer Set Programming and Other Computing Paradigms, July 31, 2022, Haifa, Israel
$ jef.wijsen@umons.ac.be (J. Wijsen)
Β http://math.umons.ac.be/staff/Capon.Chloe/ (C. Capon); https://math.umons.ac.be/staff/Lecomte.Nicolas/ (N. Lecomte);
http://informatique.umons.ac.be/staff/Wijsen.Jef/ (J. Wijsen)
0000-0001-8216-273X (J. Wijsen)
Β© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org)
Figure 1: Examples of model graphs (figure copied from [1]).
We will test this scenario on the problem of finding π»-partitions in undirected graphs πΊ [1]. All
undirected graphs in this paper are understood to be finite and simple. Given an undirected graph πΊ,
this problem consists in deciding whether there exists a partition of πΊβs vertices such that this partition
respects some constraints encoded in another graph π» with exactly four vertices, called model graph.
Each class of the partition is labeled by a vertex in π». There are two types of constraints:
β’ if π» contains a full edge between two vertices, π΄ and π΅, then each vertex in the class labeled by
π΄ must be adjacent to each vertex in the class labeled by π΅; and
β’ if π» contains a dotted edge between two vertices, π΄ and π΅, then each vertex in the class labeled
by π΄ must be nonadjacent to each vertex in the class labeled by π΅.
Note that there are no constraints between two vertices in the same class. All possible model graphs,
up to isomorphism, are presented in Figures 1 and 2. The π»-partitioning problem for πΎ2 + π2 , also
known as finding a skew partition, is in polynomial time [5, 6]. The π»-partitioning problem for 2πΎ2
is NP-complete [7]. For each model graph in Figure 2, Dantas et al. [1] provide a polynomial-time
algorithm, of low polynomial degree, for deciding whether an undirected graph admits an π»-partition.
In this paper, we show how these polynomial-time algorithms can be encoded in Datalog with stratified
negation. We then experimentally compare these Datalog programs with a guess-and-check ASP
program. In theory, the computational complexity of Datalog is in P, while guess-and-check ASP
programs can solve NP-complete problems.
This paper is organized as follows. Section 2 formalizes the problem of finding π»-partitions and
paraphrases the polynomial-time method of Dantas et al. [1]. Sections 3 and 4 focus on finding π»-
partitions in logic programming, first in ASP, and then in Datalog with stratified negation. In our
experimental validation of Section 5, we first generate undirected graphs of different sizes on which our
programs can be executed. We distinguish between those input graphs that admit an π»-partition, called
yes-instances, and those that do not, called no-instances. We show different methods for generating
yes-instances and no-instances, for a fixed model graph π», and then compare the running times of our
logic programs in the answer set solver Clingo [2, 3]. Finally, Section 6 concludes the paper. Due to
space limitations, some proofs have been omitted, which can be found in the extended version [8].
2. Preliminaries
In this section, we formally define the problem H-PARTITION and sketch an algorithm borrowed
from [1]. In Section 4, this algorithm will be written in Datalog with stratified negation.
2.1. The Problem H-PARTITION
A model graph π» is an undirected graph with four vertices, called π΄, π΅, πΆ and π· (sometimes written
in lowercase letters). The vertices are called π΄, π΅, πΆ, and π· in anticlockwise order, starting with the
top-left vertex. Every edge is of exactly one of two types: full or dotted. All possible model graphs, up
to isomorphisms, are presented in Figures 1 and 2. We define H-PARTITION as the following decision
problem.
Figure 2: List of model graphs π» (figure copied from [1]).
Problem H-PARTITION
Input: A model graph π»; an undirected graph πΊ.
Question: Is it possible to partition π (πΊ) into four pairwise disjoint, non-empty subsets, ππ΄ , ππ΅ , ππΆ ,
and ππ· such that, for all π, π β {π΄, π΅, πΆ, π·} with π ΜΈ= π:
β’ if (π, π) is a full edge of π», then every vertex in ππ is adjacent to every vertex in ππ ; and
β’ if (π, π) is a dotted edge of π», then every vertex in ππ is nonadjacent to every vertex in ππ .
Such a partition, if it exists, is called a solution or an π»-partition.
We call a pair (π», πΊ) a yes-instance if H-PARTITION returns yes on input π» and πΊ; otherwise (π», πΊ)
is a no-instance. H-PARTITION(π») denotes the H-PARTITION problem for a fixed model graph π».
The partitions ππ΄ , ππ΅ , ππΆ , and ππ· are commonly denoted by π΄, π΅, πΆ, and π·, respectively. One can
view such a partition of π (πΊ) as a labeling of π (πΊ) with the labels π΄, π΅, πΆ, and π·. From here on, we
will often omit curly braces and commas in the denotation of subsets of {π΄, π΅, πΆ, π·}. For example,
π΄π΅π· denotes the set {π΄, π΅, π·}.
Definition 1. This definition is relative to a fixed model graph π». Let πΏ β {π΄, π΅, πΆ, π·}. We define
NF (πΏ) as the set of vertices of π» that are adjacent, through a full edge, to some vertex of πΏ. Similarly,
ND (πΏ) is the set of vertices of π» that are adjacent, through a dotted edge, to some vertex of πΏ. We say
that πΏ is trivial if |πΏ| = 1.
Informally, given a model graph π», each label among π΄, π΅, πΆ, and π· imposes a constraint that can
be read from π». For example, for the model graph π» = (19) given in Figure 2, the label π΄ imposes
βbeing adjacent to πΆ and nonadjacent to π·,β and πΆ imposes βbeing adjacent to π΄ and nonadjacent to π΅.β A
list of two or more labels imposes all the constraints of each label in the list. For example, for π» = (19),
the list π΄πΆ imposes βbeing adjacent to πΆ, nonadjacent to π·, adjacent to π΄, and nonadjacent to π΅.β A list
is called conflicting if it imposes an unsatisfiable constraint. For example, for π» = (20), the list π΄πΆ is
conflicting, because π΄ imposes βbeing nonadjacent to π΅,β while πΆ imposes βbeing adjacent to π΅.β We
will call a list non-maximal 1 if it can be extended into a longer list that imposes the same constraint. For
1
In [1], non-maximal lists are called impossible.
example, for π» = (33), the lists πΆπ· and π΄πΆπ· impose the same constraint, namely βbeing adjacent to
π΅, nonadjacent to πΆ, and nonadjacent to π·,β and therefore πΆπ· is non-maximal.
Definition 2. This definition is relative to a fixed model graph π». Let πΏ β {π΄, π΅, πΆ, π·}. πΏ is
conflicting if NF (πΏ) β© ND (πΏ) ΜΈ= β
. πΏ is non-maximal if there exists πΏβ² β {π΄, π΅, πΆ, π·} such that πΏ β πΏβ²
with NF (πΏ) = NF (πΏβ² ) and ND (πΏ) = ND (πΏβ² ).
For example, let π» be model graph (13) of Figure 2. The list π΄π΅ is non-maximal because for the set
π΄π΅πΆ, we have that NF (π΄π΅) = π΄π΅πΆ = NF (π΄π΅πΆ) and ND (π΄π΅) = π· = ND (π΄π΅πΆ). The list π΄π· is
conflicting because π΅ β ND (π΄π·) β© NF (π΄π·).
2.2. Finding π»-Partitions
Dantas et al. [1] have shown that H-PARTITION(π») is in polynomial time for all model graphs π»
in Figure 2. Our algorithmic approach slightly differs from theirs because, unlike [1], we will not use
non-maximal or conflicting lists. We now describe our approach.
Definition 3. Let π» be a model graph, and πΊ an undirected graph. Let π₯π΄ , π₯π΅ , π₯πΆ , and π₯π· be four
distinct vertices of πΊ. We say that the quadruplet (π₯π΄ , π₯π΅ , π₯πΆ , π₯π· ) is π»-isomorphic if the subgraph
of πΊ induced by these vertices is a yes-instance of H-PARTITION(π») for a labeling where π₯π΄ , π₯π΅ , π₯πΆ ,
and π₯π· are respectively labeled by π΄, π΅, πΆ, and π·.
For instance, in the graph of Figure 3a, the quadruplet (2, 3, 4, 5) is π»-isomorphic to the model
graph (7) of Figure 2.
Our algorithmic approach loops over all π»-isomorphic quadruplets (π₯π΄ , π₯π΅ , π₯πΆ , π₯π· ). Each such
quadruplet yields an initial partial labeling. Given such an initial partial labeling, we test whether it can
be extended into a complete labeling, i.e., into a solution. To this end, we repeatedly pick an unlabeled
vertex, and compute its possible labels. When we say that a label π β {π΄, π΅, πΆ, π·} is possible for a
vertex, we mean that the model graph does not forbid us to label that vertex with π , given the vertices
that have already been labeled. If only one label is possible for an unlabeled vertex, we label that vertex
with that label. If no label is possible for some unlabeled vertex, we conclude that the current labeling
cannot be extended to a complete labeling. If for every unlabeled vertex at least two labels remain
possible, then we conclude that πΊ is a yes-instance for H-PARTITION(π») (except for model graphs
(7), (10) and (11) where some additional tests are needed).
In [1], refined lists are obtained by removing conflicting and non-maximal lists. The description on
[DdFGK05, page 141] might suggest that we must be careful to only consider refined lists. However,
the following lemma implies that conflicting or non-maximal lists will not occur in our algorithmic
approach.
Lemma 1. Let π» be a model graph, and πΊ an undirected graph. Assume that, during the execution of the
previously described algorithm for H-PARTITION(π») with input πΊ, there is a vertex π£ β π (πΊ) whose
set of all possible labels is πΏ with |πΏ| β©Ύ 2. Then, πΏ is neither conflicting nor non-maximal.
In Section 4, we show how to encode our algorithmic approach in Datalog with stratified negation.
However, we will first provide a straightforward guess-and-check program for H-PARTITION.
3. Guess-and-Check Program for H-PARTITION
In all logic programs of this paper, the constants are in lowercase and the variables are in uppercase
to match with Clingo syntax. We use the binary predicate e to store the edges of the input graph πΊ,
while the unary predicate vertex stores vertices. The binary predicates full and dotted encode,
respectively, full and dotted edges of the model graph. The labels are provided to the program as
partition(a), partition(b), partition(c), and partition(d).
The following program follows the generate-and-test (or guess-and-check) methodology that is classical
for problems in NP: generate a candidate solution, and test whether it is a true solution, i.e., whether it
satisfies all constraints. In the following program, the generating part is the rule 1 { placedIn(X,P)
: partition(P) } 1 :- vertex(X)., which places every vertex in exactly one partition. The
testing part imposes that every partition must contain at least one vertex, and that the constraints of
the model graph must be satisfied. Moreover, we suppose that e is symmetric, i.e., e(t,s) is stored
whenever e(s,t) is stored.
% Every vertex goes in exactly one partition.
1 { placedIn(X,P) : partition(P) } 1 :- vertex(X).
% No partition is empty.
filled(P) :- placedIn(X,P).
:- partition(P), not filled(P).
% Constraints of the model graph.
:- placedIn(X,P), placedIn(Y,Q), full(P,Q), not e(X,Y).
:- placedIn(X,P), placedIn(Y,Q), dotted(P,Q), e(X,Y).
4. Datalog Programs for H-PARTITION
In this section, we show how to encode H-PARTITION(π») in Datalog with stratified negation, for
model graphs π» in Figure 2. Section 4.1 encodes the approach of [1] in general. We argue that this
general encoding is correct for every model graph in Figure 2 that is distinct from (7), (10), and (11).
We then show how to adjust the general encoding for these three model graphs. Finally, we show that
for model graphs π» with an isolated vertex, non-recursive Datalog with negation suffices to check the
existence of π»-partitions.
4.1. General Datalog Program
Dantas et al. [1] showed that H-PARTITION(π») can be solved in polynomial time for all model
graphs π» in Figure 2. Following our previously described method, we check whether some initial valid
labeling of four vertices, called a base, can be extended to a complete labeling of all vertices.
Finding a base. The algorithm loops over all quadruplets of distinct vertices and checks whether a
quadruplet is π»-isomorphic. Our Datalog rules are as follows:
base(X,Y,Z,T) :- distinct(X,Y,Z,T), not problematic_base(X,Y,Z,T).
Here, the predicate distinct(X,Y,Z,T) checks whether π, π , π, and π are four distinct vertices
of πΊ, and problematic_base is defined, for each possible edge in the model graph π», with two rules.
For example, if we consider the edge (π, π), the rules are:
problematic_base(X,Y,Z,T) :- dotted(a,b), e(X,Y), vertex(Z), vertex(T).
problematic_base(X,Y,Z,T) :- full(a,b), not e(X,Y), vertex(X), vertex(Y), vertex(Z), vertex(T).
Similar rules are added for edges (π, π), (π, π), (π, π), (π, π), and (π, π).
Extension to a complete labeling. First, for every base (πΌ, π½, πΎ, πΏ) of four vertices, we label πΌ with
π΄, π½ with π΅, πΎ with πΆ, and πΏ with π·.
inPart(I,a,I,J,K,L) :- base(I,J,K,L).
inPart(J,b,I,J,K,L) :- base(I,J,K,L).
inPart(K,c,I,J,K,L) :- base(I,J,K,L).
inPart(L,d,I,J,K,L) :- base(I,J,K,L).
We keep track that a vertex that has been labeled in a base must not be re-labeled later on.
done(I,I,J,K,L) :- base(I,J,K,L).
done(J,I,J,K,L) :- base(I,J,K,L).
done(K,I,J,K,L) :- base(I,J,K,L).
done(L,I,J,K,L) :- base(I,J,K,L).
Next, rather than computing the set of possible labels for a yet unlabeled vertex π, we use the predicate
imp(X,P,I,J,K,L) with the meaning that the vertex π cannot be labeled by π β {π΄, π΅, πΆ, π·},
relative to the fixed base (πΌ, π½, πΎ, πΏ). The Datalog rules are straightforward. The second rule, for
example, expresses that for a full edge (π, π) in the model graph, if a vertex π has been labeled with π,
then a vertex π that is nonadjacent to π cannot be labeled with π . One should read βprobβ as a
shorthand for βproblematic.β
imp(X,P,I,J,K,L) :- vertex(X), full_prob(X,P,I,J,K,L), not done(X,I,J,K,L).
full_prob(X,P,I,J,K,L) :- full(P,Q), inPart(Y,Q,I,J,K,L), not e(X,Y), vertex(X).
imp(X,P,I,J,K,L) :- vertex(X), dot_prob(X,P,I,J,K,L), not done(X,I,J,K,L).
dot_prob(X,P,I,J,K,L) :- dotted(P,Q), inPart(Y,Q,I,J,K,L), e(X,Y).
For every vertex π of πΊ that is not in the fixed base (πΌ, π½, πΎ, πΏ), we now consider two possibilities:
(1) if three labels among π΄, π΅, πΆ, and π· are impossible for π, then π is labeled with the remaining
fourth label; and
(2) if all labels among π΄, π΅, πΆ, and π· are impossible for π, then the base cannot be extended to a
complete labeling.
Finally, if some base never encounters the second case, the answer to H-PARTITION(π») is βyesβ;
otherwise the answer is βnoβ. Note incidentally that in a βyesβ-instance, there may be vertices π that
are not labeled by the first case.
% First case.
inPart(X,a,I,J,K,L) :- imp(X,b,I,J,K,L), imp(X,c,I,J,K,L), imp(X,d,I,J,K,L).
inPart(X,b,I,J,K,L) :- imp(X,a,I,J,K,L), imp(X,c,I,J,K,L), imp(X,d,I,J,K,L).
inPart(X,c,I,J,K,L) :- imp(X,a,I,J,K,L), imp(X,b,I,J,K,L), imp(X,d,I,J,K,L).
inPart(X,d,I,J,K,L) :- imp(X,a,I,J,K,L), imp(X,b,I,J,K,L), imp(X,c,I,J,K,L).
% Second case.
bad_init(I,J,K,L) :- vertex(X), base(I,J,K,L), imp(X,a,I,J,K,L),
imp(X,b,I,J,K,L), imp(X,c,I,J,K,L), imp(X,d,I,J,K,L).
yes_instance() :- base(I,J,K,L), not bad_init(I,J,K,L).
no_instance() :- not yes_instance().
We have the following result.
Theorem 2. If π» is one of the model graphs of Figure 2 such that π» is distinct from model graphs (7),
(10), and (11), then H-PARTITION(π») is expressible in Datalog with stratified negation.
(a) Counterexample for the model graph (7). (b) Counterexample for the model graph (10).
Figure 3: The corner cases of the main approach.
4.2. Adjustment for Model Graph (7)
In [1], the model graph (7) of Figure 2 is reduced to the model graph πΎ2 . This is possible because the
constraints for π΄ and πΆ are identical (i.e., being adjacent to both π΅ and π·), and the constraints for π΅
and π· are identical. Then, every non-base vertex labeled by πΆ can also be labeled by π΄, and every
non-base vertex labeled by π· can also be labeled by π΅. Our previous Datalog program would fail,
however, for the reason that the set of possible labels for a non-base vertex is never a singleton.
For example, consider the graph πΊ in Figure 3a with the base (1, 2, 3, 4). The list of possible labels
for the vertex 5 is π΄πΆ, and the list of possible labels for the vertex 6 is π΅π·. Our previous algorithm
would terminate here and conclude that πΊ is a yes-instance. Note, however, that if vertex 5 is labeled
with π΄ (the case where we label 5 with πΆ is similar), it is impossible to label the vertex 6 with π΅ or π·,
because vertices 5 and 6 are nonadjacent.
We adjust our Datalog program as follows: if the set of possible labels of a vertex π has size 2,
the new program will label π with one of these two possibilities, arbitrarily chosen. The rest of the
program remains unchanged. That is, in the box that immediately precedes Theorem 2, we replace the
four rules for the predicate inPart by the following two rules:
inPart(X,a,I,J,K,L) :- imp(X,b,I,J,K,L), imp(X,d,I,J,K,L).
inPart(X,b,I,J,K,L) :- imp(X,a,I,J,K,L), imp(X,c,I,J,K,L).
4.3. Adjustment for Model Graphs (10) and (11)
As in [1], the model graphs (10) and (11) of Figure 2 need a special treatment. We illustrate the issue
by the model graph (10) and the graph πΊ given in Figure 3b. For the base (1, 2, 3, 4), the list of possible
labels for the vertex 5 is π΅πΆ, and the list of possible labels for the vertex 6 is π΄π·. So our original
algorithm would terminate and wrongly conclude that the base (1, 2, 3, 4) can be extended to a complete
labeling. Nevertheless, we claim that this base cannot be extended to a complete labeling. Indeed, let us
label the vertex 5 by π΅ (the case where we label 5 with πΆ is similar). Since π΅ is adjacent, through full
edges, to both π΄ and π·, and since vertices 5 and 6 are nonadjacent, we cannot label 6 with π΄ or π·. We
note incidentally that the graph πΊ is a yes-instance through other bases, for example, (1, 2, 3, 6).
It can be verified that for the model graph (10), the lists of possible labels are π΄π· and π΅πΆ; for the
model graph (11), the lists of possible labels are π΄πΆ and π΅π·. We have the following result.
Lemma 3. (Cf. [1]) Let π» be one of the model graphs (10) or (11) in Figure 2. If there exists a solution to
H-PARTITION(π») with a base (π, π, π, π), then there is also a solution with the same base such that:
β’ each vertex having π΄ in its list of possible labels is labeled π΄; and
β’ each vertex having π΅ in its list of possible labels is labeled π΅.
We now use Lemma 3 to adjust our previous Datalog program of Section 4.1. First, we copy the
labeled vertices.
label(X,a,I,J,K,L) :- inPart(X,a,I,J,K,L).
label(X,b,I,J,K,L) :- inPart(X,b,I,J,K,L).
label(X,c,I,J,K,L) :- inPart(X,c,I,J,K,L).
label(X,d,I,J,K,L) :- inPart(X,d,I,J,K,L).
Next, if π΅ is an impossible label for a vertex but π΄ is not, the vertex is labeled by π΄. Symmetrically,
if π΄ is an impossible label for a vertex but π΅ is not, the vertex is labeled by π΅.
label(X,a,I,J,K,L) :- not imp(X,a,I,J,K,L), imp(X,b,I,J,K,L).
label(X,b,I,J,K,L) :- imp(X,a,I,J,K,L), not imp(X,b,I,J,K,L).
We now have to check that this labeling is correct according to the model graph. If not, we reject the
initial base.
problem(X,P,I,J,K,L) :- label(X,P,I,J,K,L), full(P,Q), label(Y,Q,I,J,K,L), not e(X,Y).
problem(X,P,I,J,K,L) :- label(X,P,I,J,K,L), dotted(P,Q), label(Y,Q,I,J,K,L), e(X,Y).
bad_base(I,J,K,L) :- problem(X,P,I,J,K,L).
Finally, the definition of yes_instance() is changed as follows:
yes_instance() :- base(I,J,K,L), not bad_base(I,J,K,L), not bad_init(I,J,K,L).
no_instance() :- not yes_instance().
Along the lines of Theorem 2, we obtain the following result.
Theorem 4. If π» is one of the model graphs (10) or (11) in Figure 2, then H-PARTITION(π») is expressible
in Datalog with stratified negation.
4.4. Model Graphs with Isolated Vertices
A vertex in a model graph π» is isolated if it is not adjacent to a full or dotted edge. The model graphs in
Figure 2 with at least one isolated vertex are (1), (2), (3), (4), (22), and (29). It can be easily seen that
for these model graphs, H-PARTITION(π») can be solved in non-recursive Datalog with negation (i.e.,
in predicate logic).
Lemma 5. Let πΊ be an undirected graph. Let π» be a model graph with an isolated vertex. Then the
following are equivalent:
1. πΊ contains an π»-isomorphic quadruplet of distinct vertices; and
2. πΊ is a yes-instance of the problem H-PARTITION(π»).
From Section 4.1, it follows that non-recursive Datalog suffices to test the existence of an π»-isomorphic
quadruplet of distinct vertices. Thus, we obtain the following result.
Theorem 6. If π» is a model graph with an isolated vertex, then H-PARTITION(π») is expressible in
non-recursive Datalog with negation.
5. Experiments
To compare the efficiency of our programs in an existing answer set solver, we need a generator for
yes-instances and no-instances of arbitrary size. The motivation for distinguishing between yes- and
no-instances comes from the asymmetry of NP-problems: on a yes-instance, an algorithm can stop as
soon as the first π»-partition is found; but on no-instances no such early stopping is possible. In this
section, we discuss generators for yes- and no-instances, and then we report on execution times of our
programs on these instances.
5.1. Generating Yes-Instances
Let π, π be two positive integers, and π» a model graph. We want to build a graph πΊ with π vertices and
π edges that is a yes-instance for the problem H-PARTITION(π»). Necessarily, π β©Ύ 4 and π β€ π(πβ1) 2 ,
where the latter is the number of edges in the complete graph with π vertices.
We denote N0 = {1, 2, 3, . . .}. Let π, π, π, π β N0 such that π + π + π + π = π. One can wonder if
there exists a yes-instance with π edges where the numbers of vertices labeled by π΄, π΅, πΆ, and π· are,
respectively, π, π, π, and π.
Definition 4. We define ππ» min (π, π, π, π) as the smallest number π such that some graph πΊ with
|πΈ(πΊ)| = π admits an π»-partition (ππ΄ , ππ΅ , ππΆ , ππ· ) such that |ππ΄ | = π, |ππ΅ | = π, |ππΆ | = π, and
|ππ· | = π. Analogously, we define ππ» max (π, π, π, π) as the largest number π such that some graph πΊ
with |πΈ(πΊ)| = π admits an π»-partition (ππ΄ , ππ΅ , ππΆ , ππ· ) such that |ππ΄ | = π, |ππ΅ | = π, |ππΆ | = π, and
|ππ· | = π.
We write π for a label and also for the number of vertices labeled with this label. If the context is not
clear, we write #π for the number of vertices labeled by π. We have the following result.
Lemma 7. Let π» be a model graph. Let π, π, π, π β N0 such that π + π + π + π = π. Then,
βοΈ
ππ»min (π, π, π, π) = #π Β· #π (1)
(π,π)βFull(π»)
π(π β 1) βοΈ
ππ»
max (π, π, π, π) = β #π Β· #π (2)
2
(π,π)βDotted(π»)
where Full(π») is the set of the full edges of π», and Dotted(π») is the set of the dotted edges of π».
βοΈWe give a proof of (1). We first show that there exists an undirected graph πΊmin with π vertices
Proof.
and (π,π)βFull(π») #π Β· #π edges that has a solution where the numbers of vertices labeled by π΄, π΅, πΆ,
and π· are, respectively, π, π, π, and π. Let πΊmin be an undirected graph whose vertices are
π (πΊmin ) = {π΄1 , π΄2 , . . . , π΄π , π΅1 , . . . , π΅π , πΆ1 , . . . , πΆπ , π·1 , . . . , π·π }
and the edges of πΊmin are defined as follows: for ππ , ππ β π (πΊmin ), (ππ , ππ ) is an edge of πΊmin if and
only if (π, π) is a full edge of π».
Since for each full edge (π, π) in π», each vertex labeled with π is connected to each vertex labeled
with π, there are #π Β· #π such edges. Moreover, there are no other edges than those described here. As
we sum up these values for each full edge (π, π), we obtain the desired number of edges in πΊmin .
We claim that this labeling satisfies all the constraints. The full constraints are satisfied by construction.
The dotted constraints are also satisfied because πΊmin contains only edges connecting two vertices
whose labels are adjacent through a full edge in π».
Figure 4: Model graph (23).
It remains to be shown that there exists no graph with strictly less than (π,π)βFull(π») #π Β· #π edges
βοΈ
that is a yes-instance where the number of vertices labeled by π΄, π΅, πΆ, and π· are, respectively, π, π, π,
and π. Assume for the sake of contradiction that there exists such a graph πΊβ² . We can assume without
loss of generality that πΊβ² and πΊmin have the same set of vertices. Since πΊβ² has strictly less edges than
πΊmin , there is an edge (π’, π£) in πΊmin that is not in πΊβ² . Since πΊβ² is a yes-instance, it has a solution. Let
π be the label of π’ in this solution, and π the label of π£. Since (π’, π£) is an edge of πΊmin , we have that
(π, π) is a full edge of π». So, we have two vertices π’ and π£ that are labeled by π and π respectively, but
there is no edge in πΊβ² between π’ and π£. This is a contradiction with the fact that πΊβ² is a yes-instance.
This concludes the proof of (1).
The proof of (2) is similar because it suffices to consider πΊmax which is obtained from a complete
graph with π edges by removing all the edges between two vertices whose labels are connected by a
dotted edge in π».
For example, let us fix π, π, π, π β N0 with the model graph (23) of Figure 2 and π = π + π + π + π.
According to the Figure 4, we have:
(23)
πmin (π, π, π, π) = ππ + ππ
π(π β 1)
π(23)
max (π, π, π, π) = β ππ β ππ β ππ
2
(23) (23)
Moreover, we claim that, for all π such that πmin (π, π, π, π) β©½ π β©½ πmax (π, π, π, π), there exists a
graph πΊ with π vertices and π edges such that πΊ is a yes-instance for a labeling where the numbers of
vertices labeled by π΄, π΅, πΆ, and π· are, respectively, π, π, π, and π. The idea is that we can extend the
(23)
graph for πmin (π, π, π, π) by adding edges until we reach π edges such that every added edge does not
violate any dotted constraint. We will now formalize this construction.
Definition 5. Let πΊ and πΊβ² be two undirected graphs, We say that πΊ is an extension of πΊβ² , denoted
πΊβ² β πΊ, if π (πΊβ² ) = π (πΊ) and πΈ(πΊβ² ) β πΈ(πΊ). If πΊβ² β πΊ, we also say that πΊβ² is extended by πΊ.
In other words, πΊ is an extension of πΊβ² if it is possible to obtain πΊ from πΊβ² by adding some edges.
One can easily see that πΊmin β πΊmax . Indeed, we take πΊmin and consider the labeling induced by the
construction of πΊmin . We can add all possibles edges that do not violate any dotted constraint. In this
way, we obtain πΊmax by definition.
Theorem 8. Let π» be a model graph. Let π, π, π, π β N0 and π = π + π + π + π. Let πΊmin and πΊmax
be the graphs with π vertices and respectively ππ» π»
min (π, π, π, π) and πmax (π, π, π, π) edges defined in (the
proof of) Lemma 7. Every graph πΊ such that πΊmin β πΊ β πΊmax has a solution (ππ΄ , ππ΅ , ππΆ , ππ· ) where
|ππ΄ | = π, |ππ΅ | = π, |ππΆ | = π, and |ππ· | = π.
πΊ1 πΊ2 πΊ3
Figure 5: For the model graph (6), we have that πΊ1 is a yes-instance, πΊ2 is a no-instance, and πΊ3 is a yes-
instance.
Proof. Let us consider the same labeling of the vertices in πΊ as in πΊmin . So the number of vertices
labeled by π΄, π΅, πΆ, and π· are, respectively, π, π, π, and π. It remains to be shown that this labeling
satisfies all the constraints.
β’ Let (π, π) be a full edge of π». We have to show that all the vertices labeled by π are adjacent to
all vertices labeled by π. This holds true because πΊ is an extension of πΊmin and πΊmin already
satisfies this constraint.
β’ Let (π, π) be a dotted edge of π». We have to show that all the vertices labeled by π are nonadjacent
to all vertices labeled by π. This holds true because πΊmax is an extension of πΊ and πΊmax already
satisfies this constraint.
All the constraints are satisfied and, consequently, πΊ is a yes-instance.
This theorem has a natural corollary.
Corollary 9. Let π» be a model graph, and π, π, π, π β N0 such that π = π + π + π + π. Let π be an
integer such that ππ» π»
min (π, π, π, π) β©½ π β©½ πmax (π, π, π, π). There is an undirected graph πΊ with π vertices
and π edges such that πΊ has a solution where the numbers of vertices labeled by π΄, π΅, πΆ, and π· are,
respectively, π, π, π, and π.
Based on Corollary 9, we introduce the following generator of yes-instances.
Generator for yes-instances
Input: A model graph π»; two positive integers π and π such that π β©Ύ 4.
Output: Yes-instances with π vertices and π edges.
Generator: For every quadruplet (π, π, π, π) of positive integers such that π + π + π + π = π and
ππ» π»
min (π, π, π, π) β©½ π β©½ πmax (π, π, π, π),
build a yes-instance from πΊmin by randomly adding edges that do not violate any
dotted constraint, until the number of edges reaches π;
if no such quadruplet exists, return βthere is no such yes-instance.β
5.2. Generating No-Instances
Given an integer π β©Ύ 4 and a model graph π», we want to build a graph πΊ with π vertices that is
a no-instance for the problem H-PARTITION(π»). The following proposition tells us when this is
possible.
Proposition 10. Let π» be a model graph and π an integer such that π β©Ύ 4. There is an undirected
graph πΊ with π vertices that is a no-instance for H-PARTITION(π») if and only if π» is not the model
graph (1) in Figure 2.
Proof. Assume that π» is the model graph (1). Then, any graph πΊ with π vertices is a yes-instance
because there is no constraint to satisfy, due to the absence of full and dotted edges.
For the opposite direction, assume that π» is not the model graph (1). Then π» contains a dotted edge
or a full edge.
β’ If π» contains at least one full edge, the empty graph with π vertices and no edge is a no-instance
because the full constraint will never be satisfied for any labeling of the vertices.
β’ If π» contains at least one dotted edge, the complete graph with π vertices and π(πβ1) 2 edges is a
no-instance because the dotted constraint will never be satisfied for any labeling of the vertices.
This concludes the proof.
The undirected graphs in the proof of Proposition 10 are of little interest in an experimental validation,
because they do not admit an π»-isomorphic quadruplet of vertices, and therefore the Datalog program
would not even enter its recursive part. Instead, for a model graph π», we would like to generate
no-instances that contain an π»-isomorphic quadruplet. Note here that, by Lemma 5, such no-instances
do not exist if π» has an isolated vertex.
It would be interesting to develop an approach similar to that for yes-instances: start with a small
no-instance and extend it until some desired number of vertices is reached. Nevertheless, this seems a
difficult task, because the addition of edges for new vertices can turn no-instances into yes-instances,
and vice versa. For example, in Figure 5, πΊ1 is extended by πΊ2 , and πΊ2 is extended by πΊ3 . For the
model graph (6), we have that πΊ2 is a no-instance, while πΊ1 and πΊ3 are yes-instances.
In view of the aforementioned difficulties, we have decided to generate no-instances in a randomized
fashion. Given π β©Ύ 4 and model graph π» that is not the model graph (1) of Figure 2, the idea is to
generate random graphs with π vertices until a no-instance for H-PARTITION(π») is found. To see
whether this approach is viable, we have generated random graphs with π = 100 by adding an edge to
a graph with a given probability, its expected density. The expected density is considered as a random
variable whose probability distribution is a Gaussian distribution, π© (0.5, 0.25). This distribution seems
better than a βclassicalβ uniform distribution on the expected density because there are more possible
graphs with a density of 0.5 than 0.01 or 0.99. Table 1 shows, for each model graph in Figure 2, the
number of yes-instances and no-instances over a sample of 1000 generated graphs.
For the model graphs (1), (2), (3), (4), (18), (22), (29) of Figure 2, there are more yes-instances than
no-instances. Except for (18), these model graphs have an isolated vertex and, by Lemma 5, an input
graph is a yes-instance as soon as it contains an π»-isomorphic quadruplet. For the model graph (18),
a graph is easily a yes-instance because it suffices to have an edge (π’, π£) such that π’ is nonadjacent
to at least two other vertices: the vertex π’ will be labeled by πΆ, all vertices adjacent to π’ will have
the label π΄, and all nonadjacent vertices will have label π΅ or π·. For model graphs that are distinct
from the above seven model graphs, there are considerably more no-instances than yes-instances. In
conclusion, our approach should find a no-instance in a few tries, except for the seven models that have
been discussed before, for which we will use the no-instances of the proof of Proposition 10.
5.3. Execution Times
We have used the answer set solver Clingo [2, 3] to compare the execution times of ASP guess-and-check
programs with programs in Datalog with stratified negation. Figure 6 shows execution times on input
graphs of different small sizes that were generated as previously explained. The execution times reported
model graph # yes # no model graph # yes # no
(1) 1000 0 (18) 999 1
(2) 1000 0 (19) 185 815
(3) 1000 0 (20) 15 985
(4) 998 2 (21) 35 965
(5) 15 985 (22) 1000 0
(6) 175 825 (23) 15 985
(7) 13 987 (24) 15 985
(8) 15 985 (25) 14 986
(9) 13 987 (26) 56 944
(10) 9 991 (27) 15 985
(11) 0 1000 (28) 5 995
(12) 0 1000 (29) 1000 0
(13) 0 1000 (30) 0 1000
(14) 2 998 (31) 0 1000
(15) 4 996 (32) 6 994
(16) 4 996 (33) 15 985
(17) 183 817 (34) 12 988
Table 1
Proportion of yes- and no-instances.
Figure 6: Execution time in Clingo (the blue line is hidden behind the yellow line).
in Figure 6 are average execution times over the 34 model graphs of Figure 2. It is immediately clear
from this figure that when executed by Clingo, the guess-and-check program is much more efficient
than our Datalog programs with stratified negation. The difference in efficiency was even more striking
for larger graphs. In fact, on graphs with more than 50 vertices, we encountered memory problems
when executing our Datalog programs in Clingo, which seem to be due to the size of the grounded
program. In search for an explanation, we displayed and investigated the grounded rules in Clingo. The
grounded Datalog programs only contain true atoms, i.e., rules whose body has already been evaluated
as true and therefore left empty. Figure 7 shows that the Datalog programs yield significantly more
grounded rules than the guess-and-check programs. Datalog often yields more than 250 000 true atoms
while guess-and-check never results in more than 5000 ground rules.
Figure 7: Number of true atoms (Datalog) and grounded rules (ASP) in Clingo (the blue line is hidden behind
the yellow line).
6. Conclusion
We presented a logical programming approach to the problem of finding π»-partitions in undirected
graphs. In particular, we showed how the polynomial-time solutions given in [1] can be encoded in
Datalog with stratified negation. In an experimental validation, we found that in the answer set solver
Clingo, these Datalog programs execute much slower than a simple guess-and-check program. We also
studied the problem of generating yes- and no-instances for H-PARTITION with a fixed number of
vertices or edges.
Our experiments indicate that when using an answer set solver, there may be no benefit in writing
programs that are theoretically more efficient than guess-and-check programs. It would be interesting
to investigate execution times of our Datalog programs on a dedicated Datalog engine. It would also be
interesting to find systematic methods for generating no-instances with a fixed number of vertices or
edges.
References
[1] S. Dantas, C. M. H. de Figueiredo, S. Gravier, S. Klein, Finding π»-partitions efficiently, RAIRO Theor.
Informatics Appl. 39 (2005) 133β144. URL: https://doi.org/10.1051/ita:2005008. doi:10.1051/ita:
2005008.
[2] M. Gebser, R. Kaminski, A. KΓΆnig, T. Schaub, Advances in gringo series 3, in: J. P. Delgrande,
W. Faber (Eds.), Logic Programming and Nonmonotonic Reasoning - 11th International Conference,
LPNMR 2011, Vancouver, Canada, May 16-19, 2011. Proceedings, volume 6645 of Lecture Notes in
Computer Science, Springer, 2011, pp. 345β351. URL: https://doi.org/10.1007/978-3-642-20895-9_39.
doi:10.1007/978-3-642-20895-9β_39.
[3] M. Gebser, R. Kaminski, B. Kaufmann, T. Schaub, Clingo = ASP + control: Preliminary report, CoRR
abs/1405.3694 (2014). URL: http://arxiv.org/abs/1405.3694. arXiv:1405.3694.
[4] S. Abiteboul, R. Hull, V. Vianu, Foundations of Databases, Addison-Wesley, 1995. URL: http://
webdam.inria.fr/Alice/.
[5] C. M. H. de Figueiredo, S. Klein, Y. Kohayakawa, B. A. Reed, Finding skew partitions effi-
ciently, J. Algorithms 37 (2000) 505β521. URL: https://doi.org/10.1006/jagm.1999.1122. doi:10.1006/
jagm.1999.1122.
[6] W. S. Kennedy, B. A. Reed, Fast skew partition recognition, in: H. Ito, M. Kano, N. Katoh,
Y. Uno (Eds.), Computational Geometry and Graph Theory - International Conference, KyotoCGGT
2007, Kyoto, Japan, June 11-15, 2007. Revised Selected Papers, volume 4535 of Lecture Notes in
Computer Science, Springer, 2007, pp. 101β107. URL: https://doi.org/10.1007/978-3-540-89550-3_11.
doi:10.1007/978-3-540-89550-3β_11.
[7] C. N. Campos, S. Dantas, L. Faria, S. Gravier, 2K2 -partition problem, Electron. Notes Dis-
cret. Math. 22 (2005) 217β221. URL: https://doi.org/10.1016/j.endm.2005.06.031. doi:10.1016/
j.endm.2005.06.031.
[8] C. Capon, N. Lecomte, J. Wijsen, Computing h-partitions in ASP and datalog, CoRR abs/2202.03730
(2022). URL: https://arxiv.org/abs/2202.03730. arXiv:2202.03730.