arXiv CSopen access

How Hard is it to Decide if a Fact is Relevant to a Query?

How Hard is it to Decide if a Fact is Relevant to a Query?

arXiv:2604.22422v1 [cs.DB] 24 Apr 2026

Meghyn Bienvenu , Diego Figueira , Pierre Lafourcade Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400, Talence, France {meghyn.bienvenu, diego.figueira, pierre.lafourcade}@u-bordeaux.fr

Abstract We consider the following fundamental problem: given a database D, Boolean conjunctive query (CQ) q, and fact f ∈ D, decide whether f is relevant to q w.r.t. D, i.e., does f belong to a minimal subset S ⊆ D such that S |= q. Despite being of central importance to query answer explanation, the combined complexity of deciding query relevance has not been studied in detail, leaving open what makes this problem hard, and which restrictions can yield lower complexity. Relevance has already been shown to be harder than query evaluation: namely, Σp2 -complete for CQs, even over a binary signature. We further observe that NP-hardness applies already to (acyclic) chain CQs. Our work identifies self-joins (multiple atoms with the same relation) as the culprit. Indeed, we prove that if we forbid or bound the occurrence of self-joins, then relevance has the same complexity as query evaluation, namely, NP (without structural restrictions) and LogCFL (for bounded hypertreewidth classes). In the ontology setting, we establish an analogous result for ontology-mediated queries consisting of a CQ and DL-LiteR ontology, namely that relevance is no harder than query answering provided that we bound the interaction width (which generalizes both self-join width and a recently introduced ‘interaction-free’ condition). Our results thus pinpoint what makes relevance harder than query evaluation and identify natural classes of queries which admit efficient relevance computation.

 This pdf contains internal links: clicking on a notion leads to its definition. This is the long version of the KR’26 paper (Bienvenu, Figueira, and Lafourcade 2026).

1

Introduction

There has been considerable interest in both the database and knowledge representation communities on devising methods for explaining why a given query answer holds, resulting in a diversity of approaches. In the database area, proposals include qualitative notions based upon causality (Meliou et al. 2010) and provenance (Green and Tannen 2017), as well as quantitative notions of explanation based upon (causal or Shapley-value-based) responsibility measures, which involve assigning scores to facts based upon their contribution to making the query hold (Livshits et al. 2021; Bienvenu, Figueira, and Lafourcade 2024b; Bienvenu, Figueira, and Lafourcade 2025a). In the setting of ontologymediated query answering (OMQA) (Poggi et al. 2008;

Bienvenu and Ortiz 2015; Xiao et al. 2018), where query answers are computed by reasoning over the information contained in the data and the ontology, there have also been a diversity of explanation notions advanced in the literature. Some of these rely upon proofs which show step-by-step how a query answer is obtained (Borgida, Calvanese, and Rodriguez-Muro 2008; Alrabbaa et al. 2022), others compute minimal subsets of facts that make the query hold (Bienvenu, Bourgaux, and Goasdoué 2019; Ceylan et al. 2019; Ceylan et al. 2020; Ceylan et al. 2025), while some recent work has begun to explore quantitative responsibility measures (Bienvenu, Figueira, and Lafourcade 2024a; Bienvenu, Figueira, and Lafourcade 2025c). In the present paper, our focus will be on explanations given as minimal supports (a.k.a. causes, MinEXes), i.e. subset-minimal sets of facts that suffice to obtain the query answer. More precisely, we shall be interested in the fundamental problem of query relevance, which is to decide whether a given fact from the dataset is relevant to the query, in the sense that it belongs to at least one minimal support. Indeed, identifying the relevant facts can be considered a central task in query answer explanation, which is useful both for summarizing the minimal supports and for aiding users in debugging unexpected query results. Relevance is also closely related to recently explored Shapley-based responsibility measures. Indeed, for classes of monotone queries such as conjunctive queries (with or without an ontology), a fact will be assigned a positive score iff it is relevant (cf. discussions in (Bienvenu, Figueira, and Lafourcade 2025a)). Finally, it is worth noting that notions of relevance have also been considered for other kinds of explanations, including abductive explanations (Eiter and Gottlob 1995) justifications for ontology axiom entailment (Peñaloza and Sertkaya 2017; Chen et al. 2022), explanations for query non-answers (Calvanese et al. 2013), and explanations for query (non)answers under various inconsistency-tolerant semantics (Bienvenu, Bourgaux, and Goasdoué 2019). We briefly summarize here what is known about the complexity of the query relevance task, which has been explored for ontology-mediated queries (OMQs) formulated in description logic and existential rule ontology languages (Ceylan et al. 2019; Ceylan et al. 2020; Ceylan et al. 2025). For data complexity, in which the size of the query and ontology are treated as fixed, the task is known to be tractable

Query evaluation hw<∞ hw ∞

LogCFL-c NP-c

Relevance sjw<∞ sjw ∞ LogCFL-c NP-c† NP-c Σp2 -c‡

Table 1: Complexity results for classes of conjunctive queries with (un)bounded hypertree width (hw) and self-join width (sjw). Shaded cells indicate new results. † NP-hardness applies to chain CQs over a single binary relation. ‡ General Σp2 -hardness is known, we show it holds even for CQs with a single binary relation.

for (unions) of conjunctive queries (CQs), as well as for ontology-mediated queries that can be rewritten as UCQs (i.e. for so-called FO-rewritable ontology languages). Indeed, this is an easy consequence of the fact that the size of minimal supports is bounded by a constant, making it possible to solve the relevance problem by reduction to first-order query evaluation. By contrast, for (ontologymediated) query languages for which the size of minimal supports is unbounded, the relevance problem becomes NPhard in data complexity. For combined complexity, the relevance task has been proven Σp2 -complete for conjunctive queries, even in the absence of an ontology and with only binary relations (Vaicenavičius 2020). Additional combined complexity results have been established for various kinds of OMQs, with complexities ranging from Σp2 to 2EXPTIME, depending on the expressivity of the ontology language. While the preceding results show that relevance is generally harder than query evaluation, to the best of our knowledge, there has not been any exploration of what precisely makes relevance harder than query evaluation, nor the related question of which restrictions can lower the complexity. The purpose of our paper will thus be to pinpoint the sources of difficulty and identify classes of queries for which relevance is no harder than query evaluation, in particular, leading to the identification of tractable classes. Contributions Our first contribution is to show that for conjunctive queries (without an ontology), it is the presence of self-joins (i.e. multiple query atoms using the same relation) that make relevance harder than query evaluation. We start by observing that for ‘well-behaved’ classes of conjunctive queries, like acyclic CQs and CQs of bounded hypertreewidth, for which query evaluation is tractable, the relevance problem is NP-complete. In fact, relevance is NPhard even for acyclic chain CQs of the form R(x1 , x2 ) ∧ R(x2 , x3 ) ∧ · · · ∧ R(xn−1 , xn ) on a single relation (Theorem 4.2), which demonstrates that tractability cannot be regained by simplifying the query structure. However, if we restrict to CQs with ‘few’ self-joins (via a notion of self-join width, recently introduced by Bienvenu, Figueira, and Lafourcade (2025a)), then the complexity of relevance matches that of query evaluation, namely NP for general CQs or LogCFL if queries have bounded hypertree width (Theorem 4.5). These results are summarized in Table 1. We then move to considering the relevance problem for OMQs consisting of a CQ and a description logic (DL) ontology. After observing that both conjunction (⊓) and quali-

OMQ evaluation Relevance iw<∞ iw ∞ iw<∞ iw ∞ tw=1, ℓ<∞ NL-c LogCFL-c NL-c NP-c tw <∞ LogCFL-c NP-c LogCFL-c NP-h tw ∞ NP-c NP-c Σp2 -c Table 2: Complexity results for classes of ontology-mediated queries in (DL-LiteR , CQ), with (un)bounded treewidth (tw), interaction width (iw), or number of (ℓ) in acyclic CQs (iw= 1). Shaded cells indicate new results.

fied existential restrictions (∃R.C) can make relevance hard even for atomic queries, we focus on ontologies formulated in DL-LiteR , a prominent lightweight DL often used for OMQA (Calvanese et al. 2007). We introduce a novel notion of interaction width, which can be seen as generalizing both self-join width and a recently introduced ‘interaction-free’ property (Bienvenu, Figueira, and Lafourcade 2025c). Our second main contribution is to show that for OMQs consisting of a CQ and DL-LiteR ontology, bounding the interaction width makes relevance no harder than query evaluation. The obtained results, summarized in Table 2, show that simultaneously bounding the interaction width and treewidth enables efficient (LogCFL) relevance computation, and for acyclic bounded-leaf CQs, relevance drops to NL. Finally, as a third and last contribution, we investigate a more abstract notion of relevance based on graph homomorphisms, which underlies the CQ relevance problem. Concretely, we study the question of, given two graphs G and G′ , whether a given edge belongs to a minimal homomorphic image of G in G′ . We consider both directed and undirected variants of this problem, finding that they are both Σp2 -complete, thereby providing natural and simple Σp2 complete problems of independent interest. As a corollary, we obtain that Σp2 -hardness of CQ relevance already holds over signatures consisting of a single binary relation. Organization After preliminaries in Section 2, we introduce the relevance problem for CQs and OMQs in Section 3 together with some basic observations and reductions. We study the relevance problem for classes of CQs in Section 4 and the relevance problem for OMQs in Section 5. In Section 6, we introduce and study the Minimal Homomorphism Problem for graphs. We conclude in Section 7 with a discussion of future work.

2

Preliminaries

We introduce the key notions, terminology, and notation that will be used in this paper. For detailed introductions to databases and description logics, we refer readers to (Abiteboul, Hull, and Vianu 1995; Baader et al. 2017). Complexity We shall refer by L and NL the complexity classes of deterministic and nondeterministic logarithmic space, respectively. NP is the class of decision problems solvable by a nondeterministic polynomial-time Turing machine, and Σp2 the class of decision problems solvable by a nondeterministic polynomial-time Turing machine with ac-

cess to an NP oracle. The class LogCFL consists of all decision problems reducible to a context-free language, considered highly parallelizable, where L ⊆ NL ⊆ LogCFL ⊆ AC1 ⊆ NC2 ⊆ P ⊆ NP ⊆ Σp2 . Databases A (relational) database D is a finite set of relational facts R(a), where R is a relation name of arity k ≥ 1 and a is a k-ary vector of constants. The signature of D is the set of relation names that occur in the facts of D together with their arity, and we speak of a binary signature if only unary and binary predicates are used. Conjunctive Queries Conjunctive queries (CQ) are firstorder formulas of the form q(x) = ∃y α1 ∧ · · · ∧ αn where the αi are relational atoms that can contain constants and/or variables, where x is the vector of free variables of the formula. By atoms(q) we denote {αi }i . We shall only be interested in Boolean CQs, that is, CQs with no free variables, and we will henceforth assume that all CQs are Boolean. For any syntactic object O (e.g., database, query), we will use vars(O) and const(O) to denote the sets of variables and constants contained in O, and let terms(O) := vars(O) ∪ const(O) denote its set of terms. hom A homomorphism q −−→ D from a CQ q to a database D is a function h : terms(q) → const(D) such that h(c) = c for every c ∈ const(q) and R(h(t1 ), . . . , h(tn )) ∈ D for hom every atom R(t1 , . . . , tn ) in q. A homomorphism h : q −−→ q ′ between CQs is defined similarly. A CQ is a core if all the hom homomorphisms h : q −−→ q are injective. It is known that for any (Boolean) CQ q, D |= q iff there is a homomorphism hom h : q −−→ D, and that a CQ q entails another CQ q ′ iff hom q ′ −−→ q. We use h(q) for the result of replacing each x ∈ vars(q) with h(x) and call h(q) a homomorphic image of q. Inequalities A CQ q with inequalities, or CQ̸= , is a CQ extended with inequality atoms of the form t ̸= t′ where t, t′ are terms (i.e., variables or constants). For any database hom or CQ X, the notion of homomorphism h : q −−→ X is restricted in the expected way, by further requiring that h(t) ̸= h(t′ ) whenever q contains the inequality atom t ̸= t′ .

Evaluation For a class C of CQs (or of CQ̸= s), the query evaluation problem for C is the problem of, given a database D and a CQ q ∈ C, deciding whether D |= q. The problem is well known to be NP-complete for the class of all CQs (Chandra and Merlin 1977), but it becomes tractable under structural restrictions. Except when explicitly stated otherwise, we always mean combined complexity, where both the query and database are part of the input (as compared to data complexity, where only D is considered as input). Tree-like Queries An acyclic CQ is one in which there are no cycles in its underlying (hyper)graph. In the case of binary signatures this means that the underlying undirected graph, containing the edge {t, t′ } for each query atom R(t, t′ ), has no cycles. For signatures of bounded arity, the acyclicity is generalized to a measure of tree-likeness via the notion of treewidth. We refer the reader to (Gottlob et al. 2016, §3.1) for a definition. For unbounded signatures, several generalizations have been proposed, one of the most prominent being hypertree width; in particular, acyclic CQs

are precisely the queries of hypertree width 1. We refer readers to (Gottlob et al. 2016, Definition 3.1 & following paragraph) for a definition. The hypertree width of a CQ̸= is defined to be that of the CQ obtained by considering ̸= as any ordinary binary relation. Theorem 2.1 ((Gottlob, Leone, and Scarcello 2002)). For every fixed k > 0, the query evaluation problem for CQ̸= s of hypertree width at most k is LogCFL-complete under logspace reductions. The result holds also for self-join free CQs. Further, checking if a CQ̸= has hypertree width at most k is in LogCFL.1 Description Logics A description logic (DL) knowledge base (KB) K = (A, T ) consists of an ABox A and a TBox T , constructed from mutually disjoint sets NC of concept names (unary relation names), NR of role names (binary relation names), and NI of individual names (here called constants). An inverse role has the form R− , with R ∈ NR , and − we use N± R = NR ∪ {R | R ∈ NR } for the set of roles. The ABox is a finite set of facts (i.e., a database) over the binary signature given by NC and NR . The TBox (ontology) is a finite set of axioms. Its form depends on the DL in question. Our results primarily concern lightweight DLs of the DLLite family (Calvanese et al. 2007). We shall in particular consider the DL-LiteR dialect, whose TBox axioms take the form of concept inclusions B ⊑ C and role inclusions P ⊑ S, built according to the following grammar B := A | ∃P

C := B | ¬B

S := P | ¬P

where A ∈ NC and P ∈ N± R . The logic DL-Litecore is obtained from DL-LiteR by disallowing role inclusions. Another prominent lightweight DL that we shall briefly mention is EL, where the TBox consists of general concept inclusions (GCIs) D1 ⊑ D2 between concepts of the form: D := ⊤ | A | D ⊓ D | ∃R.D

A ∈ NC , R ∈ NR

The semantics of DL KBs is defined using interpretations I = (∆I , ·I ), where the domain ∆I is a non-empty set and .I maps each a ∈ NI to aI ∈ ∆I , each A ∈ NC to AI ⊆ ∆I , and each R ∈ NR to RI ⊆ ∆I × ∆I . The function ·I is extended to complex concepts and roles: ⊤I = ∆I , (∃P )I = {d | ∃e ∈ ∆I , (d, e) ∈ P I }, (R− )I = {(e, d) | (d, e) ∈ RI }, (C ⊓ D)I = C I ∩ DI . An interpretation I satisfies a fact A(a) (resp. P (b, c)) if bI ∈ AI (resp. (bI , cI ) ∈ P I ). I satisfies a (concept or role) inclusion G ⊑ H if GI ⊆ H I . We call I a model of a KB K, denoted I |= K, if I satisfies all axioms in T and all facts in A. A KB K is consistent if it has a model. A KB K entails an inclusion or fact γ, written K |= γ, if every model I of K satisfies γ. Likewise, we write K |= ∃P (a) to mean aI ∈ (∃P )I in every model I of K. Ontology-Mediated Queries We say that a (Boolean) CQ q is entailed from a KB K = (A, T ), written K |= q, if I |= q for every model I of K. We may alternatively group T and q 1

While the literature does not cover the class of CQ̸= strictly speaking, it can easily be seen that ̸=-atoms can be handled in LogCFL for the query evaluation problem.

f3 q:

D:

f1

f2

f4

Figure 1: An example query and database to illustrate the notion of relevance. Arrows represent R atoms/facts.

together as a ontology-mediated query (OMQ) Q = (T , q), in which case we may write A |= Q to mean (A, T ) |= q. The notation (L, Q) is used for the class of all OMQs (T , q) consisting of a TBox formulated in the DL L and a query q ∈ Q. Aside from conjunctive queries (CQ), we also consider classes of OMQs whose component CQs are atomic queries (AQ), i.e. CQs with a single atom. The query evaluation problem for a class of OMQs is defined analogously as before: given an ABox A and an OMQ Q from the considered class, decide whether A |= Q. The following theorem recalls some complexity results for query evaluation in subclasses of (DL-LiteR , CQ) (see (Artale et al. 2009; Bienvenu et al. 2018) and references therein). Theorem 2.2. Query evaluation for (DL-LiteR , CQ) is NPcomplete. For fixed m ≥ 1, ℓ > 1, the problem is LogCFLcomplete for the classes obtained by restricting to (T , q) s.t. • q is acyclic and has at most ℓ leaves, or • T is a DL-Litecore TBox and q has treewidth at most m

Query evaluation is NL-complete for (DL-LiteR , AQ).

Canonical Model Every consistent DL-LiteR KB K = (A, T ) admits a so-called canonical model IA,T , which maps homomorphically into every model of K. As we shall use IA,T in some of our results, we recall here its definition. For the domain ∆IA,T of IA,T , we use the set of all words aP1 . . . Pn (n ≥ 0) such that a ∈ const(A), Pi ∈ N± R , and: • if n ≥ 1, then (A, T ) |= ∃P1 (a)

• for 1 ≤ i < n, T |= ∃Pi− ⊑ ∃Pi+1 and Pi− ̸= Pi+1 .

Elements in ∆IA,T \const(A) will be called anonymous elements. The interpretation function maps each a ∈ const(A) to itself and interprets concept and role names as follows: AIT ,A = {a ∈ const(A) | (A, T ) |= A(a)}∪

{aP1 . . . Pn | n ≥ 1 and T |= ∃Pn− ⊑ A})

this question in terms of Boolean queries, asking why the Boolean query q(a) obtained by instantiating the free variables of the query with the answer tuple holds. Therefore, in what follows, we will focus w.l.o.g. on Boolean queries. For queries that are monotone (i.e., such that adding facts can never change the result from true to false), such as CQs, a simple and natural way to explain why a query q holds is to exhibit minimal subset(s) of the data that make q true. Definition 3.1. A support of a CQ q in a database D is any subset S ⊆ D such that S |= q. It is a minimal support if further it does not strictly contain another support. However, when a query has many minimal supports, it may be more useful to first present users with the set of facts that occur in at least one support. This is especially the case if a query (answer) unexpectedly holds, in which case one will need to determine which facts are at fault. Definition 3.2. For a CQ q, database D and fact f ∈ D, we say that f is relevant to q in D if it belongs to some minimal support of q in D. Example 3.3. Consider the CQ q and database D depicted in Figure 1. There are two minimal supports for q in D, which are {f1 , f2 } and {f3 }. This shows that f1 , f2 , and f3 are all relevant. However, f4 is not relevant despite appearing in a homomorphic image of q in D, because the only support containing f4 is {f3 , f4 }, which is not minimal. △ To define analogous notions for ontology-mediated queries, one must decide how to treat the case where the knowledge base is inconsistent. Namely, do we want to consider minimal inconsistent subsets as supports for an OMQ? We believe it is more natural to separate debugging of inconsistencies from explaining query results, and so we shall require in our definitions that the KB is consistent (we shall discuss the case of inconsistent KBs in Section 7). Definition 3.4. Consider an ontology-mediated query Q = (T , q) with T a DL TBox and q a CQ q, and an ABox A such that (A, T ) is consistent. A minimal support for Q in A is an inclusion-minimal subset S ⊆ A such that S |= Q, and a fact f ∈ A is relevant to Q in A if f belongs to some minimal support of Q in A. Our focus will be on analyzing the complexity of deciding relevance for different classes of (ontology-mediated) CQs. The decision problems are formally defined as follows.

RIT ,A = {(a, b) | R(a, b) ∈ A} ∪ {(w1 , w2 ) | w2 = w1 P and T |= P ⊑ R} ∪

Relevance problem for a class Q ⊆ CQ Input: Query q ∈ Q, database D, and fact f ∈ D Question: Is f relevant for q in D?

Our results exploit the following well-known property:

Relevance problem for OMQ class (L, Q) (Q ⊆ CQ) Input: OMQ (T , q) ∈ (L, Q), ABox A such that (A, T ) is consistent, and fact f ∈ A Question: Is f relevant for (T , q) in A?

{(w2 , w1 ) | w2 = w1 P and T |= P ⊑ R− })

Theorem 2.3. For every DL-LiteR KB (A, T ), (A, T ) |= q hom iff IA,T |= q iff there is a homomorphism q −−→ IA,T .

3

Query Relevance Problem

To improve the usability of information systems, it is important to be able to explain to users why a given answer a was obtained for the query q. Equivalently, we can rephrase

Remark 3.5. We treat these as standard decision problems in the complexity-theoretic sense, rather than ‘promise problems’. That is, an algorithm for Q must first verify that the input string is a valid encoding of a query from Q. △

We conclude this section by stating some easy upper and lower bounds. First, we can observe that the relevance problem can be decided using a straightforward guess-and-check procedure: guess a subset S ⊆ D that contains the given fact f , and verify that S is a minimal support. The latter can be checked by making repeated calls to a query evaluation oracle: we first check that the query holds in S, then check that the query no longer holds if any fact in S is removed. We thus obtain the following generic upper bounds: Proposition 3.6. For any class Q of (ontology-mediated) CQs, the relevance problem for Q is in NPC , where C is the complexity class of the query evaluation problem for Q. Regarding lower bounds, we cannot reasonably hope to achieve better complexity than for query evaluation. Indeed, a query q holds in a database D just in the case that some fact in D is relevant for q, which allows us to relate the complexities of the two problems as follows: Proposition 3.7. For any class Q of (ontology-mediated) CQs, the query evaluation problem for Q is in LC , where C is the complexity class of the relevance problem for Q. While the preceding result can be used to show that the relevance problem is intractable whenever query evaluation is, its formulation in terms of oracle calls is not the most convenient for establishing precise lower bounds. The following result provides a more direct (many-one) reduction: Proposition 3.8. Let Q be any class of CQs such that q ∈ Q implies that there exists q ∧ ∃x.A(x) ∈ Q, for some relation A that does not occur in q. Then there is a many-one logspace reduction from the query evaluation problem for Q to the relevance problem for Q. An analogous statement holds for OMQ classes, except that we must further require that the relation A does not occur in the TBox. Proof. Given q ∈ Q and a database D, let A be any unary relation not appearing in q. Clearly, q ′ = q ∧ ∃x.A(x) and D′ = D ∪ {A(c)} can be constructed from q, D using a logspace transducer. It then suffices to observe that D |= q iff A(c) is relevant to q ′ in D. The preceding proposition applies in particular to the whole class CQ, classes of CQs having hypertree width < m (for any m > 0), and classes of acyclic CQs with at most ℓ leaves. It does not however cover classes of CQs with a fixed finite signature, nor the class of connected CQs.

4

Relevance for Conjunctive Queries

The relevance problem for unrestricted CQs is known to be harder than the evaluation problem, in fact one step higher in the polynomial hierarchy. Theorem 4.1. (Vaicenavičius 2020, Thm. 4.30)2 The relevance problem for CQs is Σp2 -complete, and Σp2 -hardness holds already for constant-free CQs over a binary signature. We will see in the next subsections how two quantitative structural notions of queries affect this problem: the hypertree width and the amount of variables from different atoms that can be homomorphically merged into one fact. 2 While the theorem statement in the dissertation is on unions of CQs, the proof makes use only of CQs over a binary signature.

4.1

CQs with Bounded Treewidth

While query evaluation of CQs is NP-hard, structural restrictions have been identified that make query evaluation tractable. This is in particular the case for any class of CQs with bounded hypertree width (Theorem 2.1). By Proposition 3.6, this lowers the complexity of relevance to NP. Interestingly, the NP lower bound applies even to (acyclic) chain CQs of the form R(x1 , x2 ) ∧ R(x2 , x3 ) ∧ · · · ∧ R(xn−1 , xn ) on a single binary relation R. Theorem 4.2. For any fixed k ≥ 1, the relevance problem for the class of all CQs of hypertree width at most k is NPcomplete. Hardness holds even for the class of chain CQs.

Proof sketch. The minimal supports for the n-atom chain CQ qn are either simple cycles or simple paths of length n: indeed, any set strictly containing a cycle cannot be a minimal support since the cycle satisfies qn . We can then reduce from the existence of a Hamiltonian path on directed graphs. Given a directed graph G with n vertices we can produce a graph G′ by adding two new vertices u, v and the edges (u, v) and (v, v ′ ) for every v ′ ∈ V (G). Since (u, v) is in no cycle, checking whether (u, v) is relevant for qn+1 in G′ is then equivalent to testing whether G contains a simple path of length n − 1 (i.e., a Hamiltonian path).

4.2

CQs with Bounded Self-Join Width

Observe that the chain CQs of Theorem 4.2 need unboundedly many atoms on the same relation name, or ‘self-joins’. A self-join is a pair of atoms on the same relation name, and a self-join free CQ is a CQ with no self-joins. We show that if the number of self-join atoms in CQs is bounded, then the complexity of the relevance problem matches that of query evaluation, namely NP or even LogCFL if queries have bounded hypertree width (such as chain CQs). Instead of counting the number of self-joins, we use a more fine-grained notion of ‘self-join width’, which will allow showing tractability for broad classes of CQs. For a tuple t or atom α = R(t) we write t[i] and α[i] to denote the i-th element of the t-tuple. Two atoms α, β of a CQ q are mergeable if there are two homomorphisms hom hom hα : α −−→ D, hβ : β −−→ D to an arbitrary database D such that hα (α) = hβ (β) (in particular they must have the same relation name). An atom α is (individually) mergeable if it is mergeable with some other atom in q. Definition 4.3 (Self-join width). The self-join width of a CQ q is the cardinality of the following set of variables Mq := {α[i] : α, α′ are mergeable atoms of q

with α[i] ̸= α′ [i] and α[i] ∈ vars(q)}.

This definition can be viewed as a generalization and improvement of a prior notion of self-join width introduced in (Bienvenu, Figueira, and Lafourcade 2025a), see Remark B.1 for more details. Note that any self-join free query has self-join width 0, but the converse does not hold for CQs with constants. Example 4.4. The CQ q := ∃xy.R(c, x) ∧ R(c′ , y), where c, c′ are distinct constants, has self-join width 0 since it has

no two mergeable atoms. The CQ q ′ := ∃xyz R(x, y) ∧ R(x, c) ∧ S(y, z) has self-join width 1 as Mq′ = {y}. △

For classes of bounded self-join width CQs, the complexity of relevance matches that of query evaluation:

Proof. The existence of Eeq essentially follows from the developments in (Bienvenu, Figueira, and Lafourcade 2025a, proof of Theorem 6.6), but here we need to adapt definitions to have a better space complexity. Concretely, we define Eeq := {E ∈ E q : qE is a core, and for all E ′ ∈ E q ,

Theorem 4.5. For any fixed k ≥ 0, ℓ > 0:

• The relevance problem for CQs of self-join width at most k is NP-complete. • The relevance problem for CQs of self-join width at most k and hypertree width at most ℓ is LogCFL-complete.

The rest of this section is devoted to proving this result. Let us fix the class SJ k of CQs of self-join width at most k.

Lemma 4.6. (a) Detecting if two given atoms are mergeable and more generally testing whether a CQ q is in SJ k belongs to NL. (b) Computing Mq from a CQ q ∈ SJ k is in L.

We shall need to consider all the different possible ways of ‘merging’ two mergeable atoms by means of making some variables of Mq equal among them or among the constants contained in the query. For this, consider the set E q of all equivalence relations over Mq ∪ const(q) such that no two distinct constants are in the same equivalence class. Remark 4.7. There is only a polynomial number of such equivalence relations E ∈ E q and further the cardinality |E| of each equivalence relation is of constant size ≤ k, under the suitable encoding where singleton classes are implicit, and hence E can be stored in logarithmic space. △

For any equivalence relation E ∈ E q let qE be the result of collapsing all the terms in the same equivalence class in ̸= as q and removing repeated atoms. Let us further define qE the result of adding a inequality atom t ̸= t′ to qE for each ̸= pair (t, t′ ) ∈ (Mq × (Mq ∪ const(q))) \ E. Intuitively, qE is the query stating that variables of Mq shall be collapsed3 exactly according to E. Lemma 4.8. The problems of testing, given q ∈ SJ k and hom two equivalence relations E, E ′ from E q , whether qE −−→ ̸= hom ̸= qE ′ holds, whether qE −−→ qE ′ holds, and whether qE is a core, are all in L. ̸= The interest of the qE queries stems from the fact that, for a well-chosen subset of E q , they completely characterize the minimal supports of q, as the next lemma shows.

Lemma 4.9. For every q ∈ SJ k there exists a set Eeq ⊆ E q of equivalence relations, such that the following statements are equivalent for every database D: 1. S ⊆ D is a minimal support for q, 2. S = h(qE ) for some E ∈ Eeq and homomorphism h : ̸= qE −−→ D. hom

Further, given an equivalence class E ∈ E q , one can test in L whether E ∈ Eeq (under the encoding of Remark 4.7). 3

If the equivalence class X contains a constant c, then all variables of X are replaced by c; otherwise, we choose a representative variable x ∈ X and replace all variables of X by x.

̸= ̸= ̸= ̸= if qE −→ qE then qE −−→ qE ′ − ′ }. hom

hom

Claim 4.10. Eeq satisfies the 1 ⇔ 2 equivalence. Since the cardinalities of the equivalence classes in E q and Eeq are bounded by a constant (cf. Remark 4.7), they can be stored and manipulated using only logarithmic space. The complexity statement then follows from Lemma 4.8. With the previous lemma in place, Theorem 4.5 follows: Proof sketch of Theorem 4.5. We are given a fact f = R(c), database D and a CQ q. We first need to test if q meets the hypothesis. We test q ∈ SJ k in NL due to Lemma 4.6(a), and for the second statement we test hypertree width in LogCFL due to Theorem 2.1. We now compute the set Mq in L via Lemma 4.6-(b), and we then iterate in logspace over all E ∈ E q checking if there is one such E meeting the following criteria. We first check that E ∈ Eeq in L by Lemma 4.9. We next check that there is some R-atom R(t) in qE ‘consistent’ with our hom input fact R(c), that is, so that R(t) −−→ R(c). Consider ̸= now the result q̂ of replacing in qE every t[i] which is a variable with the constant c[i]. Observe that, due to Lemma 4.9, any homomorphic image of q̂ is a minimal support of q containing f , and further if there exists a minimal support of q containing f , there must be some E ∈ Eeq and atom consistent with f as described before. All these operations can be performed in logarithmic space since there are logspace ̸= ̸= transductions from q to qE , and from qE to q̂, which can be composed.Note that the hypertree width of q̂ is at most that of q plus k. We finally check D |= q̂ by a call to the query evaluation problem. This is in NP in general (Chandra and Merlin 1977, Theorem 7), or in LogCFL if we started with a class of bounded hypertree width by Theorem 2.1. The lower bounds hold by Proposition 3.8 due to equivalent bounds for query evaluation of self-join free CQs.

5

Relevance for Ontology-Mediated Queries

Now that we have a clear picture of the combined complexity of relevance for different classes of CQs, we shall push further and consider ontology-mediated queries (T , q) where T is a description logic ontology and q is a CQ. We will again be interested in understanding how the complexity of the relevance task compares to that of query evaluation.

5.1

New Sources of Hardness

The addition of an ontology introduces new sources of hardness for the relevance problem, which make the problem difficult even when restricted to atomic queries. Indeed, a first

source of hardness stems from the ability to capture reachability in the data, which in DLs can be done using qualified existential restrictions, present in EL and its extensions. This makes relevance intractable even in data complexity: Proposition 5.1 ((Ceylan et al. 2020)). Relevance for (L, AQ) is NP-hard in data complexity (hence also in combined complexity) for any DL L that can express ∃R.A ⊑ A. Proof. Any directed graph G can be represented as an ABox AG which contains R(v1 , v2 ) for each directed edge (v1 , v2 ). Then, to decide whether an edge (v1 , v2 ) in G lies on a simple path from s to t (an NP-hard problem, cf. (Khalil and Kimelfeld 2023, Lemma 5.3)), it suffices to check whether R(v1 , v2 ) is relevant for the OMQ ({∃R.A ⊑ A}, A(s)) w.r.t. the ABox AG ∪ {A(t)}. Observe that the preceding result precludes the possibility of obtaining tractability for classes of OMQs defined by bounding any combination of width notions or any other parameters that assign a finite value to each OMQ. In fact, EL contains a further source of hardness: concept conjunction. Indeed, if the ontology language can express propositional definite Horn clauses, then deciding relevance is hard (in combined complexity) even for atomic queries: Proposition 5.2. Relevance for the OMQ class (L, AQ) is NP-hard for any DL L with concept conjunction and GCIs. Proof. Vm We reduce from SAT. Consider a CNF formula ϕ := j=1 cj with variables in V := {v1 . . . vn }. We build the AQ q := A(d), the ABox A := {X(d), Pi (d), Ni (d) | 1 ≤ i ≤ n}, and the TBox T := Tt ∪ Tp ∪ Tn ∪ Tc with: Tt : {Pi ⊓ Ni ⊑ A | i ∈ [n]} dm Tc : {X ⊓ j=1 Cj ⊑ A}

Tp : {Pi ⊑ Cj | vi ∈ cj } Tn : {Ni ⊑ Cj | v i ∈ cj }

It can be verified that the fact X(d) is relevant to (T , q) w.r.t. A iff ϕ is satisfiable. This implies that if the DL allows for concept conjunction, then we cannot hope to identify tractable classes of OMQs by bounding parameters which are dominated by the query size, since NP-hardness holds already for atomic queries. In view of these results, the only DLs for which we can hope to obtain tractability results by imposing conditions on the query are logics that contain neither conjunction nor admit qualified existential restrictions on the left-hand-side of axioms. This naturally leads us to explore core fragments of the DL-Lite family, which verify these requirements.

5.2

General Results for DL-Lite

We shall henceforth focus on OMQs (T , q) whose TBox T is formulated in DL-LiteR . We consider DL-LiteR since it is a well-known core dialect (notably underlying the OWL 2 QL profile) for which the combined complexity of OMQ evaluation has been well explored (Bienvenu et al. 2018). First, we determine the combined complexity of testing relevance for arbitrary OMQs in (DL-LiteR , CQ), obtaining the same complexity as for CQs in databases:

Proposition 5.3. The relevance (DL-LiteR , CQ) is Σp2 -complete.

problem

for

Proof. The lower bound directly follows from Theorem 4.1, as the hardness proof only uses binary relations. The upper bound follows from Proposition 3.6 and NP membership for query evaluation in (DL-LiteR , CQ), see Theorem 2.2. Next, we pinpoint the complexity of well-behaved OMQ classes whose evaluation problem has been previously shown to be tractable (specifically, LogCFL-complete): Proposition 5.4. The relevance problem is NP-complete for the following classes of OMQs: • class of OMQs (T , q) ∈ (DL-LiteR , CQ) such that q is acyclic and has at most ℓ leaves (for any fixed ℓ > 1) • class of OMQs (T , q) ∈ (DL-Litecore , CQ) such that q has treewidth at most m (for any fixed m ≥ 1) Proof. The NP lower bounds follows from Theorem 4.2. For the upper bounds, we combine Proposition 3.6 with existing LogCFL results for OMQ answering in the considered classes, recalled in Theorem 2.2. The preceding results show that, just as in the plain database setting, the worst-case complexity of relevance is one level higher than query evaluation. Inspired by the positive impact of restricting self-joins, we shall next explore how an analogous notion can be employed to obtain lower complexities for deciding relevance of OMQs.

5.3

Bounded Interaction Width OMQs

The most obvious way of translating the notion of self-joinfree queries to the OMQA setting would be to consider OMQs (T , q) where q is a self-join-free CQ. However, the resulting notion does not have the desired properties due to interactions between atoms that arise from the ontology: Proposition 5.5. The hardness of Proposition 5.3 holds with the restriction that the component CQs are self-join free. Proof. We reduce from the relevance problem of CQs with relations of arity 2. Let q be such a query, and D a database on the same signature, which we can see as an ABox since it does not have any fact of arity > 2. We remove all selfjoins in q by replacing each instance of a relation R with a fresh Ri , along with the axiom Ri ⊑ R that makes Ri a particular instance of a R. Since D does not contain any of those Ri , the resulting OMQ will behave exactly as q on D and its subsets, hence the equivalence between the two when it comes to the relevance problem. This lead Bienvenu, Figueira, and Lafourcade (2025c) to define a notion of interaction-free OMQ, whose purpose is to ensure that an ABox fact can only be used to satisfy a single atom of the query (in a single way). We recall below the definition of interaction-free OMQs4 . 4 We reformulated slightly the original definition to suit our purposes, but it yields the same notion of interaction-free OMQ.

f2 R

q: x

R α

A y

R β

z

A:

R

A R′ c f1

d fA 3

Figure 2: Interacting atoms where T := {R′ ⊑ R, R′ ⊑ R− }.

Definition 5.6 (Interacting query atoms). Given an OMQ Q = (T , q) ∈ (DL-LiteR , CQ), we say that distinct atoms α, β of q interact if there exists a fact f such that ({f }, T ) |= α and ({f }, T ) |= β (with α and β treated as Boolean CQs). An atom α interacts with itself if there exist a fact f , homohom hom morphisms h1 : α −−→ I{f },T and h2 : α −−→ I{f },T , and variable x ∈ vars(α) such that h1 (x) ∈ const(f ) and h2 (x) ̸= h1 (x). We denote by int-atoms(Q) the set of atoms in Q that (self-)interact. Definition 5.7 (Interaction-free OMQ). An OMQ Q ∈ (DL-LiteR , CQ) is interaction-free if int-atoms(Q) = ∅. Example 5.8. Consider the KB (A, T ) and CQ q depicted in Figure 2. α interacts with β via f1 , but both also interact with themselves by the two distinct homomorphisms that R map to (c, d) in either direction, since I{f1 },T ⊇ c ← → d. This is especially important because, out of (x, y) 7→ (c, d) and (x, y) 7→ (d, c), only the latter witnesses the relevance of f1 : the former can only be extended with z 7→ d, whose image strictly contains the minimal support {f2 , f3 }. △ We propose to generalize interaction-free OMQs by introducing the notion of interaction width: Definition 5.9 (Interaction width). The interaction width of an OMQ Q ∈ (DL-LiteR , CQ) is |int-atoms(Q)|. Observe that, as expected, interaction-free OMQs have interaction width zero. It is also worth noting that, differently from self-join width, we count the number of atoms in int-atoms(Q), not the number of variables in such atoms (but this difference is insignificant on binary signatures). Example 5.10. The OMQ Q from Figure 2 has interaction width 2, since int-atoms(Q) = {α, β}. The OMQ Q′n = Vn (Tn , qn ) where qn := i=1 Ri (xi−1 , xi ) and T := {Ri ⊑ hom R} has interaction width n since α −−→ I{R(c,d)} for every atom α of q, hence int-atoms(Q′n ) = atoms(Q′n ). △ The remainder of the section will be dedicated to establishing the following theorem, which shows that by bounding the interaction width, we can obtain the same complexity for query relevance as for query evaluation. Theorem 5.11. The relevance problem is in NP for every subclass of (DL-LiteR , CQ) having bounded interaction width. LogCFL (resp. NL) membership holds if we further require component CQs have bounded treewidth (resp. the component CQs are acyclic with bounded number of leaves). In what follows, we suppose that we have an input OMQ Q = (T , q) of interaction width k and an ABox A. We shall call a fact f ∈ A potentially relevant to atom α in (T , q) if ({f }, T ) |= α. The next lemma distinguishes two kinds of potentially relevant facts:

Lemma 5.12. If a fact f ∈ A is relevant to Q = (T , q) w.r.t. A, then f is potentially relevant to either (i) a single atom in atoms(q)\int-atoms(Q) (and no other atom), or (ii) one or more atoms in int-atoms(Q). We start by testing whether the given fact f ∈ A is potentially relevant to some atom of q, and return no if not. This can be done in NL by guessing a query atom and performing atomic query evaluation. We may thus focus on testing relevance for potentially relevant facts of types (i) or (ii). Consider first the case where f is potentially relevant to a single atom αf ∈ atoms(q) \ int-atoms(T , q). Then there hom exists h : αf −−→ I{f },T , and moreover, every such homomorphism agrees on which variables are sent to which ABox constants (and which are mapped to the anonymous part). Define q-αf as the CQ obtained from q by removing αf and replacing variable x by h(x) if x occurs both in αf and another atom of q. The following lemma provides a direct reduction of relevance to query evaluation: Lemma 5.13. Let f ∈ A be potentially relevant to αf ∈ atoms(q) \ int-atoms(T , q). Then f is relevant to (T , q) w.r.t. A iff (A, T ) |= q-αf . It remains to consider the more challenging case, where f is potentially relevant to some atom(s) in int-atoms(Q). The basic idea will be to iterate over subsets S ⊆ A of at most k facts which contain f and make true the subquery given by int-atoms(Q) and can be extended to build a minimal support for q. The following lemma makes precise which properties of S to check in order to conclude that f is relevant. It refers to the set shared-vars(T , q) of variables that occur both in int-atoms(Q) and in atoms(q) \ int-atoms(T , q).

Lemma 5.14. Let f ∈ A be potentially relevant to at least one atom in int-atoms(T , q). Then f is relevant to (T , q) w.r.t. A iff there exists a subset S ⊆ A with f ∈ S and hom |S| ≤ k and hS : int-atoms(Q) −−→ IS,T such that:

1. if x ∈ shared-vars(T , q), then hS (x) ∈ const(A) 2. (A, T ) |= qhS where qhS is obtained by removing all atoms in int-atoms(T , q) and replacing x ∈ shared-vars(T , q) by hS (x) hom 3. there is no S ′ ⊊ S and hS ′ : int-atoms(Q) −−→ IS ′ ,T such that hS ′ (x) = hS (x) for every x ∈ shared-vars(T , q). This suggests the following procedure for deciding relevance of facts of type (ii): iterate (in logspace) over all candidate sets S and homomorphisms hS and check whether the required conditions hold. We terminate either when some S has been shown to satisfy the conditions (outputting ‘relevant’) or when there are no more candidates to test (‘not relevant’). Note that the second condition requires a query evaluation check, the cost of which will depend on the form of the query qhS . For the third condition, we must perform a second (logspace) exploration of possible S ′ ⊊ S and hS ′ . If we consider CQs of bounded interaction width, without further structural restrictions, we can obtain an optimal NP upper bound by implementing the sketched procedure using a non-deterministic polytime Turing machine (using a nondeterministic guess to verify (A, T ) |= qhS in condition 2).

For the LogCFL and NL results, we further need to establish the complexity of query evaluation for structurally restricted classes of OMQs of bounded interaction width: Theorem 5.15. Query evaluation is in LogCFL for the class of OMQs (T , q) ∈ (DL-LiteR , CQ) with interaction width at most k and treewidth at most m (for any fixed k ≥ 0, m ≥ 1). It is in NL if we further restrict to (T , q) such that q is acyclic and has at most ℓ leaves (for fixed ℓ ≥ 2). Proof sketch. Assuming w.l.o.g. that q is connected, we sephom arately test for the existence of a homomorphism h : q −−→ IA,T that fully maps q into the anonymous part, or one which sends at least one variable to an ABox constant. In the former case, we argue that |q| ≤ k, so we can guess and check a (compact representation of a) potential homomorphism in NL. For the second kind of homomorphism, we show that all variables are mapped either to an ABox constant or to an anonymous element aP1 . . . Pn with n ≤ k, enabling the reuse of techniques developed for boundeddepth ontologies (Bienvenu et al. 2018). Although Theorem 5.15 cannot be used directly to evaluate qhS (as the instantiation of shared variables can make an acyclic query become cyclic, or increase the treewidth), it is possible to simulate constants using fresh unary predicates, thereby retaining q’s good structural properties and obtaining the desired LogCFL (resp. NL) upper bounds. It is worth observing that for interaction-free OMQs,we can only have type (i) potentially relevant facts. Thus, we can decide relevance using AQ checks (to establish potential relevance), followed by evaluating the OMQ (T , q-αf ). This makes relevance for this class of OMQs easily implementable on top of any OMQA system.

6

Minimal Homomorphisms on Graphs

Theorem 4.1 shows that the relevance problem for CQs is a step higher in the polynomial hierarchy than the corresponding query evaluation problem, and that the Σp2 -hardness already holds for binary signatures. We will now study the problem for simplest kind of databases or queries: graphs, either directed or undirected, which we call digraphs and graphs, respectively. We show that the problem remains Σp2 complete even on this simple setting, which can be seen as a result of independent interest. For digraphs G, G′ , a G-homomorphic image on G′ is any subgraph Ĝ′ of G′ such that V (Ĝ′ ) = Im(h) and E(Ĝ′ ) = {(h(v), h(v ′ )) : (v, v ′ ) ∈ E(G)} for some hom h : G −−→ G′ . We shall sometimes write h(G) to denote Ĝ′ . The definition for graphs is analogous. Such Ghomomorphic image is said to be minimal if it does not strictly contain any other G-homomorphic image. We can now define the Minimal Homomorphism Problem in its directed (MinHomd ) and undirected (MinHomu ) versions.

MinHomu (resp. MinHomd ) problem Input: A pair G, G′ of graphs (resp. digraphs), and an edge e ∈ E(G′ ). Question: Is e in some minimal G-homomorphic image on G′ ? The problem MinHomd is the natural equivalent to the relevance problem on a single binary relation: Lemma 6.1. There are logspace many-one reductions between MinHomd and the relevance problem for the class of constant-free CQs over a single binary relation. As we show, it remains Σp2 -complete. Theorem 6.2. MinHomd is Σp2 -complete. Proof sketch. The upper bound is straightforward. For the lower bound, we reduce from the relevance problem over binary relations R1 , . . . , Rn , known to be Σp2 -hard (Theorem 4.1). Given an input D, q, f of the relevance problem we consider digraphs Gq , GD and an edge ef ∈ E(GD ) so that this is a positive instance of MinHomd iff D, q, f is positive for relevance. The idea is simply to replace each atom or fact Ri (a, b) with a long directed path from a to b containing a short directed cycle of a prime length pi in the middle, where p1 < · · · < pn are the first n prime numbers (which can be computed in polynomial time due to (Rosser 1939, Thm. 2)).5 The long paths are of length pn to ensure that the only ‘short’ cycles of length ≤ pn are the ones of these gadgets. In this way, we can build both Gq from q and GD from D. Since prime pi -cycles can only be homomorphically mapped to pi -cycles, and the long paths prevent hom creating any other short cycle, a homomorphism q −−→ D hom can be equivalently seen as a homomorphism Gq −−→ GD from prime cycles to prime cycles. By taking any edge ef of the cycle contained in the replacement of fact f in GD , we have that ef belongs to a minimal Gq -homomorphic image on GD iff f is relevant for q in D. As a corollary, we have that the relevance problem is already hard for CQs using a single binary relation. Corollary 6.3 (of Theorem 6.2 and Lemma 6.1). The relevance problem for CQs is Σp2 -complete even on signatures having a single binary relation. Theorem 6.4. MinHomu is Σp2 -complete. Proof sketch. The lower bound is more involved than for MinHomd since for undirected graphs we no longer have that prime p-cycles can only be homomorphically mapped to p-cycles (in fact they can map to any smaller odd cycle). We can however reduce from MinHomd by making use of graphtheoretic techniques known as ‘replacement methods’. 5 The i-th prime number pi can be computed in polynomial time since it is bounded by O(i log(i)) (cf. (Rosser 1939, Thm. 2)) and testing primality is trivially in polynomial time since i is smaller than the number of binary relations, and hence than the input size.

7

Conclusion and Discussion

The main takeaway from our study is that the difficulty of the relevance problem for (DL-LiteR -mediated) CQs hinges fundamentally on the number of atoms (or of variables from different atoms) that may interact with a fact in the following sense: if we restrict the number of self-join variables or interacting atoms, then the complexity of relevance is essentially as good or bad as that of query evaluation. These insights allowed us to identify natural classes of queries for which relevance can be efficiently decided, and we expect that they will also prove useful when designing practical algorithms for the relevance problem. Complexity Dichotomies & Parameterized Complexity It is a natural question whether bounding the self-join width or interaction width is a necessary condition for obtaining tractability or lower complexity. More precisely, one might try to prove a dichotomy result along the following lines: “For every recursively enumerable class C of conjunctive queries, if C has bounded self-join width and bounded (hyper)treewidth, then relevance is in polynomial time, and otherwise it is NP-hard”. Unfortunately, it is not at all clear that such a dichotomy holds, as there is currently no such dichtomy known for the combined complexity of CQ evaluation, and existing research provides strong evidence against its existence (Grohe 2007). By contrast, an FPT / W[1]-hard dichotomy has been proven for the parameterized evaluation of CQs, using the treewidth (modulo cores) as the parameter (Grohe 2007). Hence, a promising direction is to investigate the parameterized complexity of the relevance problem. Other Ontology Languages We conjecture that the notion of interaction width we introduced for DL-LiteR can be fruitfully applied also to linear existential rules, as they similarly enjoy the singleton support property (i.e. only one fact is needed to satisfy a query atom). For ontology languages which admit conjunction, and hence do not enjoy the singleton support property (since multiple facts may needed to infer a query atom), such as DL-LiteHorn , new restrictions will be needed to define well-behaved OMQ classes admitting tractable relevance computation. Indeed, as noted in Section 5.1, the NP-hardness of relevance for atomic queries precludes any positive results for classes of DL-LiteHorn OMQs obtained via bounding parameters dominated by the query size. For non-first-order-rewritable DLs like EL, Proposition 5.1 effectively rules out any tractability results in combined complexity, but it may still be worthwhile to develop pragmatic algorithms for deciding relevance in such logics. Relevance w.r.t. Inconsistent KBs When studying relevance of OMQs, we focused on consistent knowledge bases. Since explaining the inconsistency of a given KB can be seen as explaining the Boolean query ‘is the KB consistent?’, we could naturally consider the relevance problem for inconsistency. We should be able to transfer upper bounds from the query setting, but not necessarily lower bounds, as such ‘inconsistency queries’ may be restricted in ways that lower the complexity. Indeed, in DL-LiteR , relevance of inconsistency is easily shown to be in NL as minimal inconsistent subsets are of size at most 2. Alternatively, one may study

the relevance problem for explanations of query answers under inconsistency-tolerant semantics. Interestingly, existing proposals of explanations for repair-based semantics (Bienvenu, Bourgaux, and Goasdoué 2019) are defined via minimal supports, so we expect that our results will prove useful. Interaction Width Beyond Relevance We expect that our new notion of interaction width may prove useful for identifying tractable OMQ classes for other explanation-related tasks. In particular, it was recently shown that the class of interaction-free OMQs admits efficient counting of minimal supports (Bienvenu, Figueira, and Lafourcade 2025c), and we are cautiously optimistic that this positive result can be extended classes of OMQs in DL-LiteR with bounded interaction width (in line with an analogous result shown in the database setting for classes of CQs with bounded selfjoin width (Bienvenu, Figueira, and Lafourcade 2025a)). As detailed in the cited works, counting minimal supports has applications in query answer explanation as the number of minimal supports can be used to assign numeric scores to facts based upon their contribution to making the query hold.

Acknowledgements This work has been partially supported by ANR grants INTENDED (ANR-19-CHIA-0014) and EXPAND (ANR-25CE23-1215).

References Abiteboul, S.; Hull, R.; and Vianu, V. 1995. Foundations of databases, volume 8. Addison-Wesley Reading. Alrabbaa, C.; Borgwardt, S.; Koopmann, P.; and Kovtunova, A. 2022. Explaining ontology-mediated query answers using proofs over universal models. In Proceedings of the International Joint Conference on Rules and Reasoning (RuleML+RR), 167–182. Artale, A.; Calvanese, D.; Kontchakov, R.; and Zakharyaschev, M. 2009. The DL-Lite family and relations. Journal of Artificial Intelligence Research (JAIR) 36:1–69. Baader, F.; Horrocks, I.; Lutz, C.; and Sattler, U. 2017. An Introduction to Description Logic. Cambridge University Press. Bienvenu, M., and Ortiz, M. 2015. Ontology-mediated query answering with data-tractable description logics. In Tutorial Lectures of the Reasoning Web (RW) Summer School, volume 9203 of Lecture Notes in Computer Science. 218–307. Bienvenu, M.; Kikot, S.; Kontchakov, R.; Podolskii, V. V.; and Zakharyaschev, M. 2018. Ontology-mediated queries: Combined complexity and succinctness of rewritings via circuit complexity. Journal of the ACM 65(5):28:1–28:51. Bienvenu, M.; Bourgaux, C.; and Goasdoué, F. 2019. Computing and explaining query answers over inconsistent DLLite knowledge bases. Journal of Artificial Intelligence Research (JAIR) 64:563–644. Bienvenu, M.; Figueira, D.; and Lafourcade, P. 2024a. Shapley value computation in ontology-mediated query answering. In Principles of Knowledge Representation and Reasoning (KR).

Bienvenu, M.; Figueira, D.; and Lafourcade, P. 2024b. When is Shapley value computation a matter of counting? Proceedings of the ACM on Management of Data (PACMMOD) 2(2:PODS):1–24. Bienvenu, M.; Figueira, D.; and Lafourcade, P. 2025a. Shapley revisited: Tractable responsibility measures for query answers. Proceedings of the ACM on Management of Data (PACMMOD) 3(2:PODS):1–26. Bienvenu, M.; Figueira, D.; and Lafourcade, P. 2025b. Shapley revisited: Tractable responsibility measures for query answers. CoRR abs/2503.22358v3. Extended version of (Bienvenu, Figueira, and Lafourcade 2025a). Bienvenu, M.; Figueira, D.; and Lafourcade, P. 2025c. Tractable responsibility measures for ontology-mediated query answering. In Principles of Knowledge Representation and Reasoning (KR). Bienvenu, M.; Figueira, D.; and Lafourcade, P. 2026. How hard is it to decide if a fact is relevant to a query? In Principles of Knowledge Representation and Reasoning (KR). Borgida, A.; Calvanese, D.; and Rodriguez-Muro, M. 2008. Explanation in the DL-Lite family of description logics. In Proceedings of the International Conference: On the Move to Meaningful Internet Systems (OTM), 1440–1457. Calvanese, D.; De Giacomo, G.; Lembo, D.; Lenzerini, M.; and Rosati, R. 2007. Tractable reasoning and efficient query answering in description logics: The DL-Lite family. Journal of Automated Reasoning (JAR). Calvanese, D.; Ortiz, M.; Simkus, M.; and Stefanoni, G. 2013. Reasoning about explanations for negative query answers in DL-Lite. Journal of Artificial Intelligence Research (JAIR) 48:635–669. Ceylan, İ. İ.; Lukasiewicz, T.; Malizia, E.; and Vaicenavicius, A. 2019. Explanations for query answers under existential rules. In International Joint Conference on Artificial Intelligence (IJCAI), 1639–1646. Ceylan, İ. İ.; Lukasiewicz, T.; Malizia, E.; and Vaicenavicius, A. 2020. Explanations for ontology-mediated query answering in description logics. In Proceedings of the European Conference on Artificial Intelligence (ECAI), 672–679. Ceylan, İ. İ.; Lukasiewicz, T.; Malizia, E.; and Vaicenavicius, A. 2025. Explanations for query answers under existential rules. Artif. Intell. 341:104294. Chandra, A. K., and Merlin, P. M. 1977. Optimal implementation of conjunctive queries in relational data bases. In Symposium on Theory of Computing (STOC), 77–90. ACM Press. Chen, J.; Ma, Y.; Peñaloza, R.; and Yang, H. 2022. Union and intersection of all justifications. In International Conference on Semantic Web (ESWC), volume 13261 of Lecture Notes in Computer Science, 56–73. Springer. Eiter, T., and Gottlob, G. 1995. The complexity of logicbased abduction. Journal of the ACM 42(1):3–42. Gottlob, G.; Greco, G.; Leone, N.; and Scarcello, F. 2016. Hypertree decompositions: Questions and answers. In ACM Symposium on Principles of Database Systems (PODS), 57– 74. ACM Press.

Gottlob, G.; Leone, N.; and Scarcello, F. 2002. Hypertree decompositions and tractable queries. Journal of Computer and System Sciences (JCSS) 64(3):579–627. Green, T. J., and Tannen, V. 2017. The semiring framework for database provenance. In ACM Symposium on Principles of Database Systems (PODS), 93–99. ACM Press. Grohe, M. 2007. The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM 54(1):1:1–1:24. Hell, P., and Nešetřil, J. 2004. Graphs and homomorphisms, volume 28 of Oxford lecture series in mathematics and its applications. Oxford University Press. Khalil, M., and Kimelfeld, B. 2023. The complexity of the Shapley value for regular path queries. In International Conference on Database Theory (ICDT), 11:1–11:19. Livshits, E.; Bertossi, L.; Kimelfeld, B.; and Sebag, M. 2021. The Shapley value of tuples in query answering. Logical Methods in Computer Science (LMCS) Volume 17, Issue 3:6942. Meliou, A.; Gatterbauer, W.; Moore, K. F.; and Suciu, D. 2010. The complexity of causality and responsibility for query answers and non-answers. Proc. VLDB Endow. 4(1):34–45. Peñaloza, R., and Sertkaya, B. 2017. Understanding the complexity of axiom pinpointing in lightweight description logics. Artif. Intell. 250:80–104. Poggi, A.; Lembo, D.; Calvanese, D.; De Giacomo, G.; Lenzerini, M.; and Rosati, R. 2008. Linking data to ontologies. In Journal on Data Semantics X, 133–173. Rosser, B. 1939. The n-th prime is greater than n log(n). Proceedings of the London Mathematical Society 2(1):21– 44. Vaicenavičius, A. 2020. Explanations for ontologymediated query answers. Ph.D. Dissertation, University of Oxford, UK. Xiao, G.; Calvanese, D.; Kontchakov, R.; Lembo, D.; Poggi, A.; Rosati, R.; and Zakharyaschev, M. 2018. Ontologybased data access: A survey. In International Joint Conference on Artificial Intelligence (IJCAI), 5511–5519.

class C = {qn : n > 0} of Boolean CQs

G e

s

...

t

Figure 3: Database DG for Theorem 4.2. Arrows represent r facts.

A

Appendix to Section 3 “Query Relevance Problem”

Proposition 3.7. For any class Q of (ontology-mediated) CQs, the query evaluation problem for Q is in LC , where C is the complexity class of the relevance problem for Q. Proof. It suffices to iterate, in logspace, over all facts in the database and test whether the considered fact is relevant. Query evaluation succeeds iff some fact is found to be relevant.

B

Appendix to Section 4 “Relevance for Conjunctive Queries”

Theorem 4.2. For any fixed k ≥ 1, the relevance problem for the class of all CQs of hypertree width at most k is NPcomplete. Hardness holds even for the class of chain CQs. Proof. The fact that the problem is in NP is a direct consequence of Proposition 3.6, since the evaluation of CQs with bounded hypertree width is polynomial, see Theorem 2.1. Moving on to the NP-hardness, we reduce from the HamPs,t problem of deciding, given a directed graph G = (V, E) and distinguished vertices s, t ∈ E, if there exists a hamiltonian path from s to t, that is a path s → · · · → t that visits each vertex exactly once.Consider an input instance G, s, t, and denote by n := |V | the number of vertices in G. We build the database DG := {R(s′ , s), R(t, t′ )} ∪ {R(u, v) | (u, v) ∈ E}, where s′ , t′ are fresh constants, as depicted in Figure 3, and the query qG := rn+1 (x, y). Denote by e := R(s′ , s) the first extra edge. If there exists a hamiltonian path from s to t, it forms a simple path P in DG of the form rn−1 (s, t). P ̸|= q because it is short of two edges, however P ∪ {e, R(t, t′ )} is a minimal support for qG , witnessing that e is relevant. If there exists no hamiltonian path from s to t, any homomorphic image of qG that contains e will necessarily contain repeated vertices, hence a cycle. Now a minimal support for qG cannot strictly contain a cycle because any cycle satisfies q alone. The fact e is therefore irrelevant. Remark B.1 (On a prior definition of self-join width). A prior notion of self-join width for a CQ q was introduced and studied in (Bienvenu, Figueira, and Lafourcade 2025a), which is defined as the size of Mold q := {t ∈ terms(α) : α is a mergeable atom of q}.

Observe how our current definition of self-join width is more general, in the sense that Mq ⊆ Mold q . For example, the

qn := ∃xx′ y1 . . . yn Rn (x, y1 , . . . , yn ) ∧

Rn (x′ , y1 , . . . , yn ) ∧ S(x, x′ )

has unbounded self-join width with the definition above of (Bienvenu, Figueira, and Lafourcade 2025a) since Mold qn = ′ {x, x , y1 , . . . , yn }. However, it has self-join width 2 with our definition, since Mqn = {x, x′ }. In this way, the alternative definition we propose yields larger classes of bounded self-join width and thus larger islands of tractability. △ Theorem 4.5. For any fixed k ≥ 0, ℓ > 0: • The relevance problem for CQs of self-join width at most k is NP-complete. • The relevance problem for CQs of self-join width at most k and hypertree width at most ℓ is LogCFL-complete. Proof. We are given a fact f = R(c), database D and a CQ q. We first need to test if q ∈ SJ k , which can be done in NL due to Lemma 4.6-(a). For the second statement, we have to further check that q is of hypertree width at most ℓ. This can be done in LogCFL due to Theorem 2.1. If q does not meet the self-join width hypothesis (and the hypertree width hypothesis for the second statement), we reject the input (cf. Remark 3.5). Otherwise, we compute the set Mq in L via Lemma 4.6(b), and we then iterate, using logarithmic space, over all the possible E ∈ E q (of logarithmic size by Remark 4.7) checking if there is one such E meeting the criteria we describe next. We first check that E ∈ Eeq in L by Lemma 4.9. We next check that there is some R-atom R(t) in qE consistent with our input fact R(c), that is, such that • t[i] = c[i] if t[i] is a constant, • if t[i] = t[j] then c[i] = c[j]. If there is more than one such consistent atom, then we iterate, using logarithmic space, over all of them testing if there is one meeting the properties that follow next. ̸= Consider now the result q̂ of replacing in qE every t[i] which is a variable with the constant c[i]. We then have that any homomorphic image of q̂ is a minimal support of q containing f .Indeed, if S is a homomorphic image of q̂, there hom is a homomorphism h : q̂ −−→ S such that h(q̂) = S. Extending h to the variables of qE in the expected way (i.e., by mapping t[i] to c[i] for every variable t[i]) then yields ̸= hom a homomorphism h′ such that h′ : qE −−→ S and further ′ h (qE ) = S. Then, by Lemma 4.9 (2 ⇒ 1), S is a minimal support of q. Further, if there exists a minimal support of q containing f , there must be some E ∈ Eeq and atom consistent with f as described before. All these operations can be performed in logarithmic ̸= space since there are logspace transductions from q to qE , ̸= and from qE to q̂, which can be composed. Observe that the hypertree width of q̂ is at most that of q plus k: collapsing variables does not increase the width and each added inequality atom x ̸= y may induce adding x, y to some bags which increase the width by at most 1.

We finally check D |= q̂ by a call to the query evaluation problem. This is in NP in general (Chandra and Merlin 1977, Theorem 7), or in LogCFL if we started with a class of bounded hypertree width by Theorem 2.1. The NP-hardness result follows via Proposition 3.8 from the fact that query evaluation is already NP-hard for self-join free CQs. The LogCFL-hardness result follows via Proposition 3.8 from the fact that query evaluation is LogCFL-hard for self-join free acyclic CQs (i.e., of hypertree width 1) by Theorem 2.1. Lemma 4.6. (a) Detecting if two given atoms are mergeable and more generally testing whether a CQ q is in SJ k belongs to NL. (b) Computing Mq from a CQ q ∈ SJ k is in L. Proof. (a) Observe that testing whether two atoms R(t1 , . . . , tn ) and R′ (t′1 , . . . , t′m ) are mergeable is equivalent to testing that (i) R = R′ , (ii) n = m, and (iii) the graph G = (V, E) has no two distinct constants in the same connected component, where V = {t1 , . . . , tn , t′1 , . . . , t′m } and E = {{ti , t′i } : i ∈ [n]}. For testing (the negation of) (iii) one can non-deterministically guess a path between two distinct constants, and use the fact that NL is closed under complement by the Immerman-Szelepcsényi Theorem. For testing whether q ∈ SJ k we compute Mq as follows. We initialize a set A = ∅. Then, we iterate over every pair of atoms α, α′ in q, and if they are mergeable (which can be tested in NL), we iterate over all indices i of the arity of α and add α[i] to the set A if α[i] is a variable such that α[i] ̸= α′ [i]. (b) Note that the proof of NL from the previous point (a) for testing whether two atoms are mergeable becomes L if we further assume that q ∈ SJ k , since the lengths of paths in the graph is bounded by a constant (namely, k). Hence, the procedure to compute Mq of the previous paragraph becomes L. Lemma 4.8. The problems of testing, given q ∈ SJ k and hom two equivalence relations E, E ′ from E q , whether qE −−→ ̸= hom ̸= qE ′ holds, whether qE −−→ qE ′ holds, and whether qE is a core, are all in L. hom

Proof. If such qE −−→ qE ′ exists, then it must be identitary on all variables outside Mq . There are constantly many remaining variables, and we can then go through all possible O(|vars(qE ′ ) ∪ const(qE ′ )|k ) mappings for these in logarithmic space and checking whether some of these mappings yields a homomorphism. The same argument applies ̸= hom ̸= for checking qE −−→ qE ′ by restricting the verification to mappings which are injective on Mq . Finally, note that qE is not a core if, and only if, there is hom hom E ′ ∈ E q such that qE −−→ qE ′ , qE ′ −−→ qE , and qE ′ has fewer atoms than qE . Using only logarithmic space, we can go one by one all E ′ ∈ E q checking if there is one verifying these three conditions, in particular by using the algorithm hom for −−→ testing described above. Claim 4.10. Eeq satisfies the 1 ⇔ 2 equivalence.

̸= qE ′

/ hom g

̸= qE ′

h(qE ) = S

α

(atom injective)

h(α)

g(qE ′ )

hom h

h(g(qE ′ ))

Figure 4: Visual support for proof of Lemma 4.9.

Proof. 1 ⇒ 2 If S ⊆ D is a minimal support for q, let hom h : q −−→ D be a homomorphism realizing it, i.e., such that h(q) = S. Consider the equivalence relation E ∈ E q induced by h (i.e., where (t, t′ ) ∈ E iff h(t) = h(t′ ) for ̸= hom all t, t′ ∈ Mq ∪ const(q)). Hence, ĥ : qE −−→ S via the ̸= relativization ĥ of h onto the variables of qE . Observe that ̸= hom ĥ : qE −−→ S atom injective, in the sense that the size of S equals the number of atoms of qE (cf. Claim B.2). We need to show that E ∈ Eeq . If qE is not a core, then it is easy to see that S cannot be a minimal support; let us hence assume that qE is a core. By contradiction, suppose that ̸= hom ̸= ̸= hom ̸= ′ g : qE −→ qE but qE ̸ −→ qE − ′ − ′ for some E ∈ E q . This means that g(qE ′ ) does not contain all atoms of qE : let α be one of these missing atoms. See Figure 4 for an illustration. Note that h(α) ∈ S cannot be in h(g(qE ′ )) since h atom injective; hence h(g(qE ′ )) ⊊ S contradicting the fact that S is a minimal support of q. 2 ⇒ 1 By means of contradiction, suppose S is the h̸= hom image for h : qE −−→ D (i.e., h(qE ) = S) where E ∈ Eeq , hom but S is not minimal since there is some g : q −−→ S ′ with S ′ ⊊ S. Let E ′ ∈ E q be the equivalence relation induced hom ̸= by g, so that f (qE ′ ) = S ′ for some f : qE −→ D – ′ − as before, note that f atom injective: |atoms(qE ′ )| = |S ′ | (cf. Claim B.2). Since f (qE ′ ) ⊆ h(qE ), it follows that ̸= ̸= hom −→ qE (cf. Claim B.3), and hence that, since E ∈ Eeq , qE ′ − ̸= hom ̸= we must also have qE −−→ qE By composing the ho′. hom ̸= ̸= hom ̸= −→ S ′ we obmomorphisms qE −−→ qE ′ and f : qE ′ − ′ tain that |S | is the number of atoms of qE (by Claim B.2). But this is in contradiction with what we have already established, namely, that the number of atoms of qE is |S| via the atom injective homomorphism h, and that |S| ̸= |S ′ | since S ′ ⊊ S. Claim B.2 (taken from (Bienvenu, Figueira, and Lafourcade ̸= hom 2025b, Claim 50)). If a homomorphism h : qE −−→ D is so that h(qE ) = S, then |S| is the number of atoms of qE Proof. The proof can be found in the cited paper.

♢

Claim B.3 (taken from (Bienvenu, Figueira, and Lafourcade 2025b, Claim 54)). If for E, E ′ ∈ E q there are homomor̸= hom ̸= hom phisms h : qE −−→ D and h′ : qE −→ D with h′ (qE ′ ) ⊊ ′ − ̸= hom ̸= h(qE ), then there is a homomorphism qE −→ qE . ′ − Proof. The proof can be found in the cited paper.

♢

C

Appendix to Section 5 “Relevance for Ontology-Mediated Queries”

Lemma 5.12. If a fact f ∈ A is relevant to Q = (T , q) w.r.t. A, then f is potentially relevant to either (i) a single atom in atoms(q)\int-atoms(Q) (and no other atom), or (ii) one or more atoms in int-atoms(Q). Proof. Suppose that f ∈ A is relevant to Q = (T , q) w.r.t. A. This means that there is a minimal support S ⊆ A for (T , q) that contains f . There is thus a homomorphism hom h : q −−→ IS,T , but minimality implies that q does not embed homomorphically into IS\{f },T . Due to the canonical model definition, there must thus exist some atom αf ∈ q hom such that αf −−→ I{f },T , i.e. f is potentially relevant to αf . First suppose that αf ∈ atoms(q) \ int-atoms(Q). Then by definition, there cannot exist another atom βf such that hom βf −−→ I{f },T , so αf is the unique atom for which f is potentially relevant. Otherwise, αf ∈ int-atoms(Q), hence f is potentially relevant for at least one atom in int-atoms(Q), as in condition (ii). Lemma 5.13. Let f ∈ A be potentially relevant to αf ∈ atoms(q) \ int-atoms(T , q). Then f is relevant to (T , q) w.r.t. A iff (A, T ) |= q-αf . Proof. First suppose that f is relevant to (T , q) w.r.t. A, and let S be a minimal support for (T , q) in A that contains f . hom It follows that there is a homomorphism h : q −−→ IS,T . Moreover, since f is potentially relevant to αf ∈ atoms(q) \ int-atoms(T , q), there is a witnessing homomorphism h′ : hom αf −−→ I{f },T . Since αf ∈ atoms(q) \ int-atoms(T , q), we know that if x ∈ vars(αf ) and h′ (x) ∈ const(A), then hom h′ (x) = h(x). It follows that h also witnesses that q-αf −−→ IS,T , which yields (S, T ) |= q-αf , hence (A, T ) |= q-αf . For the other direction, suppose that (A, T ) |= q-αf , and let S be a minimal support for (T , q-αf ) in A. We claim that S ∪ {f } is a minimal support for (T , q) in A:

• We first show that S ∪ {f } is a support for (T , q) in A. Indeed, we know that there is a homomorphism h : hom hom q-αf −−→ IS,T and a second homomorphism h′ : αf −−→ I{f },T witnessing that f is potentially relevant for αf . Now let h′′ be defined by setting h′′ (x) = h(x) if x ∈ vars(q-αf ) and h′′ (x) = h′ (x) if x ∈ vars(αf ) (note that h′′ is well defined as vars(q-αf ) ∩ vars(αf ) = ∅). Then by appealing to the canonical model construction, we can hom see that h′′ defines a homomorphism q −−→ IS∪{f },T . It follows that (S, T ) |= q, i.e. S is a support for (T , q). • Now we establish minimality. Let us suppose for a contradiction that S ∪ {f } is not a minimal support, and let S ′ ⊊ S ∪ {f } be a stricter smaller support. If hom f ̸∈ S ′ , then q −−→ IS,T . By appealing to the canonical model construction, there must exist f ′ ∈ S such hom that αf −−→ I{f ′ },T , which contradicts our assumption that αf ̸∈ int-atoms(T , q). Thus, it must be the case that hom S ′ ⊊ S and q −−→ IS ′ ∪{f },T . However, since S is a minimal support for (T , q-αf ), either f is being used to satisfy another atom than αf , or there is a homomorphism

hom

witnessing q −−→ IS ′ ∪{f },T that sends x ∈ vars(αf ) to a constant different from h′ (x). Both options are disallowed since αf ̸∈ int-atoms(T , q), yielding the desired contradiction. hom

Lemma C.1. Let x ∈ shared-vars(T , q) and h : q −−→ IA,T . Then h(x) ∈ const(A). Proof. Assume for a contradiction that h(x) is an anonymous constant. By construction of the canonical model in DL-LiteR , any anonymous element w = aP1 . . . Pn of IA,T can be generated by a fact fw ∈ A (i.e., w ∈ I{fw },T ) and this fw will also generate all intermediate aP1 . . . Pk with 1 ≤ k < n as well as all facts of IA,T over these elements. In particular, if we take α ∈ int-atoms(Q) and β ∈ atoms(q) \ int-atoms(T , q) that contain x (as per the definition of shared-vars(T , q)), and denote by w the anonymous constant of h({α, β}) that is the furthest into the anonymous region, then we will have such an fw s.t. h({α, β}) ⊆ I{fw },T . This constitutes an interaction between α and β which contradicts β ∈ atoms(q) \ int-atoms(T , q). Lemma 5.14. Let f ∈ A be potentially relevant to at least one atom in int-atoms(T , q). Then f is relevant to (T , q) w.r.t. A iff there exists a subset S ⊆ A with f ∈ S and hom |S| ≤ k and hS : int-atoms(Q) −−→ IS,T such that:

1. if x ∈ shared-vars(T , q), then hS (x) ∈ const(A) 2. (A, T ) |= qhS where qhS is obtained by removing all atoms in int-atoms(T , q) and replacing x ∈ shared-vars(T , q) by hS (x) hom 3. there is no S ′ ⊊ S and hS ′ : int-atoms(Q) −−→ IS ′ ,T such that hS ′ (x) = hS (x) for every x ∈ shared-vars(T , q). Proof. First suppose that f is relevant to (T , q) w.r.t. A. Let Sq be a minimal support for (T , q) in A that contains f , hom witnessed by h : q −−→ ISq ,T . Necessarily, every fact in Sq must be potentially relevant to some atom in q w.r.t. S, otherwise it could be removed, contradicting minimality of Sq . Now let S ∗ ⊆ Sq be the set of facts in Sq that are potentially relevant to at least one atom in int-atoms(Q). By definition, we have f ∈ S ∗ . If |S ∗ | > k, then we have more facts than atoms in int-atoms(Q), so we could remove at least one fact from S ∗ and still satisfy all atoms in int-atoms(Q). Note here that we are exploiting the property of core DL-Lite dialects (like DL-LiteR ) where the minimal support of a query cannot contain more facts than the atoms in the query. Moreover, by Lemma 5.12, the facts in S ∗ cannot be used to satisfy the other atoms not in int-atoms(Q). Thus, assuming |S ∗ | > k contradicts our assumption of minimality, which yields |S ∗ | ≤ k, as required. hom Next we note that from h : q −−→ ISq ,T , we obtain a hom ∗ homomorphism h : int-atoms(Q) −−→ IS ∗ ,T , simply by ∗ setting h (x) = h(x) for all variables x in int-atoms(Q). Indeed, as already noted, only the facts in S ∗ are useful for satisfying the atoms in int-atoms(Q), meaning that the image of int-atoms(Q) under h maps within IS ∗ ,T . It remains to prove that S ∗ and h∗ verify the three conditions.

For condition 1, consider some x ∈ shared-vars(T , q). hom Since h : q −−→ ISq ,T , Lemma C.1 is applicable and yields ∗ h (x) = h(x) ∈ const(A). For condition 2, it suffices to consider the homomorphism hom h : q −−→ ISq ,T . Indeed, by definition of h∗ , we have h∗ (x) = h(x) for all variables x in int-atoms(Q), and in hom particular, for x ∈ shared-vars(T , q). Thus, h : qh∗ −−→ ISq ,T , which shows that Sq , T |= qh∗ (hence A, T |= qh∗ ). Finally, to show condition 3, suppose for a contradiction hom that there exist S ′ ⊊ S ∗ and h′ : int-atoms(Q) −−→ IS ′ ,T such that h′ (x) = h∗ (x) for every x ∈ shared-vars(T , q). In this case, let us consider the set of facts Sq− = S ′ ∪ (Sq \ S ∗ ) and define h′′ by setting h′′ (x) = h′ (x) for variables occurring in int-atoms(Q), and h′′ (x) = h(x) for all remaining x ∈ vars(q). By definition, h′′ agrees with hom h on shared-vars(T , q). Thus, from h : qh∗ −−→ ISq ,T hom ′ and h : int-atoms(Q) −−→ IS ′ ,T , we can infer that h′′ hom is a homomorphism q −−→ ISq− ,T . This would mean that Sq− , T |= q, contradicting the minimality of Sq . We thus conclude that there can be no such S ′ ⊊ S ∗ and h′ , so condition 2 is satisfied. For the other direction, let S ⊆ A and hS : hom int-atoms(Q) −−→ IS,T satisfy all requirements of the lemma statement. In particular, f ∈ S and |S| ≤ k. We aim to show that S can be extended to a minimal support of (T , q). To this end, let Sq− be a minimal support for (T , qhS ) hom in A, and h− −→ ISq− ,T a witnessing homomorphism q : qhS − must exist due to condition 2). Letting (such Sq− and h− q hom S ∗ = S ∪ Sq− , we define a homomorphism h : q −−→ IS ∗ ,T by setting h(x) = hS (x) if x appears in int-atoms(Q) and h(x) = h− q (x) otherwise. Indeed, we know that qhS was obtained by replacing each x ∈ shared-vars(T , q) by hS (x), so the homomorphisms hS and h− q are compatible. It follows that S ∗ is a support of (T , q), and it remains to show that S ∗ is minimal. Let us thus suppose for a contradiction that there exists a fact g ∈ S ∗ such that S ∗ \ {g} is still a support for (T , q). If g ∈ S ∗ ∩ Sq− , then this implies that Sq− is not a minimal support. Indeed, we know that the facts in S are not potentially relevant for any atoms in qhS , so Sq− \ {g} must be a support for (T , qhS ), a contradiction. Thus, it must be the case that g ∈ S. Let S ′ = S \ {g} and take any homomorphism hS ′ : hom int-atoms(Q) −−→ IS ′ ,T . Due to condition 2, there must exist x ∈ shared-vars(T , q) such that hS ′ (x) ̸= hS (x). Take β ∈ atoms(q) \ int-atoms(T , q) with x ∈ vars(β). Since β ∈ int-atoms(T , q) and hS (x) ∈ const(A), any homomorphism of q to IS ∗ \{g},T must send x to hS (x), again yielding a contradiction. We can thus conclude that S ∗ is a minimal support for (T , q), and since it contains f , this proves that f is relevant (T , q) w.r.t. S ∗ (and hence A). Theorem 5.15. Query evaluation is in LogCFL for the class of OMQs (T , q) ∈ (DL-LiteR , CQ) with interaction width at most k and treewidth at most m (for any fixed k ≥ 0, m ≥ 1). It is in NL if we further restrict to (T , q) such that q is acyclic and has at most ℓ leaves (for fixed ℓ ≥ 2).

Proof. Fix k ≥ 0, m ≥ 1, and ℓ ≥ 2. Note that it suffices to provide a procedure for OMQs whose component CQ is connected, since an arbitrary OMQ can be evaluated by separately checking whether each of its connected components is entailed. Let us thus take some Q = (T , q) ∈ (DL-LiteR , CQ) with interaction width at most k, and suppose w.l.o.g. that q is a connected CQ. We will devise procedures of the required complexity for testing whether A |= Q, or equivalently, A, T |= q. By Theorem 2.3, the latter holds iff there is a homomorphism of q into IA,T . We shall distinguish two kinds of homomorphisms: those which map at least one variable to an ABox constant, and those which map the whole query within the anonymous part. First, we consider how to check for the existence of a homomorphism which maps at least one variable to an ABox constant. In this case, we can observe that any such homomorphism cannot ‘reach’ an anonymous element aP1 . . . Pn if n > k, because connectedness of the query means that we would also need to map variables onto a, aP1 , . . . , aP1 . . . Pn−1 . This would in turn mean that there would be n role atoms that can all mapped within the anonymous part of a single fact, implying that there are at least n > k atoms in int-atoms(T , q). Since we only need to consider homomorphisms that map to ABox constants and anonymous elements aP1 . . . Pn with n ≤ k, we may reuse an existing procedures for DL-LiteR designed for so-called bounded depth ontologies (Bienvenu et al. 2018), where the maximum length of an anonymous element aP1 . . . Pn cannot exceed a particular bound. In that paper, LogCFL and NL procedures are devised respectively for the classes of OMQs with bounded treewidth CQs and acyclic CQs with bounded numbers of leaves, respectively, under the assumption that there is a constant bound on the ontology depth. Intuitively, these procedures consider mappings of the query variables into the ABox constants and anonymous elements. Crucially, the depth bound ensures that every anonymous element can be represented with logarithmic space, Moreover, it is shown that when restricted to anonymous elements of constant length, it can be tested in NL whether a potential domain element aP1 . . . Pn is actually present in ∆IA,T and whether a given such element (resp. pair of elements) belongs to AIA,T (resp. RIA,T ). Applying these procedures, we are able to determine the existence of a homomorphism that maps at least one variable to an ABox constant (or more generally, maps all query variables to anonymous elements aP1 . . . Pn with n ≤ k), in LogCFL if q has treewidth at most m and in NL if q is acyclic with at most ℓ leaves (recall that m and ℓ are fixed constants). To complete the proof, we must show how to decide the existence of a homomorphism that maps the whole query within the anonymous part, possibly using anonymous elements whose length is greater than k. We first observe that this means that there is a single fact fq ∈ A such that hom q −−→ I{fq },T . This would imply in turn that all atoms in q belong to int-atoms(T , q), and hence |q| ≤ k. Thus, if |q| > k, we can immediately conclude that no such homomorphism exists. Otherwise, if |q| ≤ k, then q has a constant number of atoms. Now if there is a homomor-

phism of q which maps all variables into the anonymous part, then exists some role T such that (a) there is an element w = cP1 . . . Pn ∈ ∆IA,T with Pn = T and (b) it is possible to map q into the subtree rooted at w with some variable v ∈ vars(q) sent to w. Importantly, we may assume w.l.o.g. in (a) that n ≤ 2|T | (due to the way the words in ∆IA,T are defined), and in (b) we don’t actually care about c nor the P1 . . . Pn−1 but only about what holds starting from PN = T . This is because we are considering the subtree rooted of IA,T rooted at w, which is fully determined by the role T . But this means in turn that once we have decided that we map into a tree rooted at w (or any other anonymous element whose final role is T ), then we only need to consider homomorphisms that map at most |q| ≤ k steps deeper into the anonymous part. And since we have only constantly many query atoms (hence variables) to consider, we can actually guess the function h representing a potential homomorphism, by guessing a possibly empty word of length ≤ k over N± R for each variable in q, and then checking whether h is such that: 1. it only maps variables to words R1 . . . Rl such that T |= ∃T − ⊑ ∃R1 , and T |= ∃Ri− ⊆ ∃Ri+1 for 1 ≤ i < l. 2. it satisfies the query atoms, meaning that if A(x) ∈ q and h(x) = R1 . . . Rl , then T |= Rl− ⊑ A (or T |= ∃T − ⊑ A if h(x) = ϵ), and if S(x, y) ∈ q, then either: • h(x) = R1 . . . Rl and h(y) = R1 . . . Rl+1 and T |= Rl+1 ⊑ S, or • h(x) = R1 . . . Rl+1 and h(y) = R1 . . . Rl and T |= − Rl+1 ⊑S

Thus, to sum up, we guess a role T and verify that there exists some element cP1 . . . Pn ∈ ∆IA,T with Pn = T . This can be done in NL by first guessing c and some P1 such that (A, T ) |= ∃P1 (a), and then sequentially guessing each Pi , keeping only two roles in memory at each time, checking whether T |= Pi ⊑ Pi+1 . Then we guess a function h of the form described above and check whether it satisfies the required conditions. The function can be represented in logspace because |q| ≤ k. Moreover, the conditions can also be checked in NL (using the fact that axiom entailment is in NL). If we find a role T and function h satisfying the conditions, then this means that q can be mapped into the anonymous part of the canonical model (we can obtain the witnessing homomorphism by taking any w = cP1 . . . Pn ∈ ∆IA,T with Pn = T and then appending the word given by h). Conversely, if such a homomorphism exists, then we can use it pick T and h. We thus have an NL procedure for checking homomorphisms of this type. By sequentially executing the procedures for the two types of homomorphism, we obtain a procedure that can decide the existence of any homomorphism of q into ∆IA,T . The resulting procedure runs in LogCFL provided q has treewidth ≤ m, and in NL if further q is acyclic and with ≤ ℓ leaves. Further details on the proof of Theorem 5.11 To complete the proof, we need to explain how we can test whether (A, T ) |= qhS , for the queries qhS constructed in Lemma

5.14. Recall first that qhS is obtained from q by (a) removing all atoms in int-atoms(T , q), then (b) replacing x ∈ shared-vars(T , q) by hS (x). Clearly, (a) cannot adversely affect the query structure. So let us now consider qh′ S where we retain (a), but instead of (b), we do the following: add the query atom Ac (x), for each x ∈ shared-vars(T , q) such that h(x) = c, with Ac a fresh concept name. We also define an ABox A′ by extending A with the facts {Ac (c) | h(x) = c, x ∈ shared-vars(T , q)}. It is straightforward to show that (A, T ) |= qhS

iff

(A′ , T ) |= qh′ S

Importantly, however, qh′ S has the same treewidth as q, and if q is acyclic, then qh′ S has the same number of leaves as q. Thus, we can apply the LogCFL and NL procedures from Theorem 5.15 to decide whether (A′ , T ) |= qh′ S . Finally, we note that we can construct A′ from A and qh′ S from qhS by means of a logspace transducer, completing the upper bound argument.

D

Appendix to Section 6 “Minimal Homomorphisms on Graphs”

What we shall call a graph from now on and without further notice, is a simple undirected graph without any loop or isolated vertex, and a digraph the directed counterpart. In particular, a digraph can be seen equivalently either a database or a (constant-free, Boolean) CQ over a signature containing a single binary relation, but we will rather focus on (di)graphs in the developments of this section. Lemma 6.1. There are logspace many-one reductions between MinHomd and the relevance problem for the class of constant-free CQs over a single binary relation. Proof. Let G = (V, E) and G′ = (V ′ , E ′ ) be digraphs, with V = {v1 , . . . , vn } and V ′ = {u1 , . . . , un′ }. Consider the constant-free CQ qG obtained from G by replacing each (vi , vj ) ∈ E with an atom R(xi , xj ), where {xi }i∈[n] are pairwise distinct variables. Consider also DG′ as the database obtained from G′ by replacing each (ui , uj ) ∈ E ′ with a fact R(ci , cj ), where {ci }i∈[n′ ] are pairwise distinct constants. Observe that an edge (ui , uj ) is in a minimal Ghomomorphic image on G′ if, and only if, the fact R(ci , cj ) is relevant for the CQ qG on the database DG . Likewise, from any constant-free CQ q over a single binary relation R and database D, we can produce digraphs Gq , GD by replacing facts or atoms R(t, t′ ) with edges (vt , vt′ ), and it follows that a given fact is relevant iff the corresponding edge is in a minimal Gq -homomorphic image on GD .

D.1

Directed Graphs

Directed graphs are naturally very close to databases and queries on the signature {R}, but we can actually go further, be emulating, using a single relation, any fixed signature that only contains relations of arity 2. Lemma D.1. Let q be a constant-free Boolean CQ and D a database, both on the signature Σ := {R1 , . . . , Rn } only

Cpn+2 Ppn+2

rj c ri

d

η

Cpj

Cpn+2 Ppn+2

uc

ud

Ppn+2 Cpn+1

Cpi

Ppn+2 Cpn+1

Ppn+2

Ppn+2

in a subgraph of GD of the form −−−−→ Cp′ −−−−→ for some p′ . Now the only strongly connected components of such a subgraph is the Cp′ cycle; this means that any Cp homomorphic image on GD , which is a particular case of hom a Cp -homomorphic image since Pp −−→ Cp , must be contained in Cp′ . In fact it must be Cp′ as a whole since no proper subset is strongly connected, and, since p and p′ are hom prime numbers, we have Cp′ −−→ Cp′ iff p = p′ . ♢

Figure 5: Construction for Lemma D.1. The loops labelled Cp are simple cycles of length n, and the arrows labelled Ppn+2 are simple paths of length 7. The two anchor vertices are uc and ud .

Let h(Gq ) be a Gq -homomorphic image on GD . By Claim D.2, it must map every anchor vertex of Gq to some anchor vertex of GD because they are the only constants at the intersection of a Cpn+1 and a Cpn+2 . Then every

containing arity 2 relations. Then there exist two digraphs Gq , GD = (Vq , Eq ), (VD , ED ) such that:

uc −−−−→ Cp −−−−→ ud must map to a uh(c) −−−−→

1. there exists a bijective mapping η from the homomorphic images of q in D to the Gq -homomorphic images on GD that preserves the inclusion relation; 2. for every fact f ∈ D, there exists ef ∈ ED s.t. for every homomorphic image S of q in D, f ∈ S iff ef ∈ η(S); 3. if q is isomorphic to D, then Gq = GD . Proof. We build graphs Gq , GD that precisely encode q and D resp. The construction will be identical for both in order to satisfy condition 3, so we shall focus on D for now. The construction from q is identical except that constants must be replaced with existential variables. For this, we start with a set of vertices that are identical to the constants of D, which we call anchor vertices. Then we connect these vertices with the gadgets depicted in Figure 5, designed to imitate the different relations in Σ. We denote this transformation by η. We can easily see that η is a bijection between the subsets of D and set S of subgraphs S of DG such that:

1. for every anchor vertex in S, S also contains its associated Cpn+1 and Cpn+2 ; 2. for every anchor vertex in S, S also contains at least one Ppn+2 that touches it; 3. for every Ppn+2 in S, S also contains the coupled Ppn+2 and the intermediate Cp .

The image of η always has this structure indeed, and η −1 (S) can be obtained from every S ∈ S by simply removing all Ppn+2

Ppn+2

Cpn+1 s and Cpn+2 s then replacing every −−−−→ Cpi −−−−→ R

i by − −→. We now need to show that every Gq -homomorphic image Ĝ′ on GD is in S, that η −1 (Ĝ′ ) is a homomorphic image of q in D, and vice versa.

Claim D.2. For any prime number p ⩽ pn+2 , the only Cp homomorphic images on GD are the simple Cp . Proof. Let p ⩽ pn+2 be a prime number. Consider the homomorphic image P of a path of length p in GD . Since the anchor vertices are separated by pn+2 ⩾ p edges, P can only contain one of them (or two if they are both its endpoints). Additionally, P cannot contain both the Cpn+1 and the Cpn+2 attached to an anchor vertex because that would require pn+1 + pn+2 > p edges. P is therefore contained

Ppn+2

Ppn+2

Ppn+2

Ppn+2

Cp −−−−→ uh(d) . At last, every anchor vertex in Gq touches Ppn+2

a −−−−→ (otherwise there would be a variable of q that appears in no atom) so the same can be said of their image by h. We have thus established that h(Gq ) ∈ S. Further, observe that the i-th prime number pi can be computed in polynomial time because it is bounded by O(i log(i)) (eg. by (Rosser 1939, Theorem 2)) and testing primality is trivially in polynomial time since we consider i which is smaller or equal to the number of binary relations, hence smaller than the input size. If we now consider the database η −1 (h(Gq )), it will have Ppn+2

Ppn+2

a fact Ri (c, d) iff there is a uc −−−−→ Cpi −−−−→ ud in h(Gq ) iff there exist x, y s.t. h(x) = c, h(y) = d and Ppn+2

Ppn+2

ux −−−−→ Cpi −−−−→ uy in Gq iff there exist x, y s.t. h(x) = c, h(y) = d and Ri (x, y) ∈ q. This means that η −1 (h(Gq )) is a homomorphic image of q in D indeed. Reciprocally, at last, η(S) for any homomorphic image S of q in D is a Gq -homomorphic image on GD by construction. At last, the inclusion relation is trivially preserved since η(S) is always a direct encoding of S. This concludes the proof of condition 1. For condition 2, we simply need to choose ef for f = Ri (c, d) inside Ppn+2

Ppn+2

the corresponding uc −−−−→ Cpi −−−−→ ud , because the whole structure will be present in η(S) iff f ∈ S. As for condition 3, given that the construction on q and D is identical, we only need to make sure that we build Gq and GD on the same set of anchor vertices from the beginning, in accordance with the isomorphism between q and D. We obtain a new graph-theoretic Σp2 -complete problem: Theorem 6.2. MinHomd is Σp2 -complete. Proof. We reduce from the relevance problem for constantfree Boolean CQs of arity 2 (Theorem 4.1). Given a constant-free Boolean CQ q on the signature Σ, a database D and a fact f ∈ D, we can first assume that D is on the same signature because any other fact would be trivially irrelevant to q. Then we can apply Lemma D.1 to get our instance Gq , Gd , ef of MinHomd . From conditions 1 and 2, we get that ef is in some minimal Gq -homomorphic image on GD iff f is relevant to q in D.

D.2

Undirected Graphs

f

G

We show that the Σp2 hardness persists even for the Minimal Homomorphism Problem over undirected graphs.

u

v

u

G′

′

Theorem 6.4. MinHomu is Σp2 -complete.

• h∗J (w) = h(w) for every w ∈ V (H), • for any other vertex w ∈ V (H ∗ J) \ V (H) which is in a Jxy copy in H ∗ J, we define h∗J (w) to be the corresponding vertex of the Jh(x)h(y) copy in H ′ ∗ J. Claim D.3. There exists a replacement graph J, s, t such hom that every graph homomorphism G ∗ J −−→ H ∗ J is equal hom ∗ J to f for some digraph homomorphism f : G −−→ G′ . ′ Further, J does not depend on G, G and contains an edge non-adjacent to {s, t}. Proof. The statement follows directly from well-known results. Without getting into the details of the definitions, it suffices to know that a replacement graph may be strong or not, and that a graph may be rigid or not. There exist replacement graphs which are both strong and rigid. For example, (Hell and Nešetřil 2004, Figure 4.7) defines a family of replacement graphs Gk , a, b which are all both strong (Hell and Nešetřil 2004, Proposition 4.16) and rigid (Hell and Nešetřil 2004, Proposition 4.6) (and contain edges nonincident to a, b). The claim then follows from taking any such Gk , a, b as J, s, t and applying (Hell and Nešetřil 2004, Proposition 4.12), whose statement reads: For every rigid strong replacement graph J, s, t and every pair H, H ′ of dihom graphs, we have that every homomorphism H ∗J −−→ H ′ ∗J hom ∗ is equal to f J for some homomorphism f : H −−→ H ′ . ♢ Consider the graphs G ∗ J, G′ ∗ J given by the claim above, and let {û′ , v̂ ′ } be an edge of the Ju′ v′ copy of J in G′ ∗ J non-adjacent to u′ , v ′ . Claim D.4. G, G′ , (u′ , v ′ ) is a positive instance of the MinHomd problem if, and only if, G ∗ J, G′ ∗ J, {û′ , v̂ ′ } is a positive instance of the MinHomu problem.

v′

∗J J

s

f

∗J

G′ ∗ J

u′ t

s s ′ û

J

v̂ ′

G∗J s

J

u

t

s û

J v̂

v

t s

t

v

t t

J

J

Proof. The upper bound is straightforward. For the lower bound, we reduce from the directed version MinHomd of the problem already shown in Theorem 6.2 to be Σp2 -hard. Let G, G′ , (u′ , v ′ ) be an instance of MinHomd . We shall base the proof on some known graph-theoretic techniques collectively known as ‘replacement methods’. The following preliminary definitions can be found in (Hell and Nešetřil 2004, §4.4). Let us define a replacement graph as any triplet J, s, t where J is a graph and s, t two distinct vertices thereof. For such a replacement graph and a digraph H, we denote by H ∗ J the (undirected) graph obtained from H by replacing each directed edge (x, y) ∈ E(H) by an isomorphic copy Jxy of J, identifying x with s and y with t; assuming that all the copies Jxy are pairwise vertex disjoint (except perhaps for x, y). Observe that in the notation H ∗ J the vertices s, t of J are implicit and shall always be clear from the context. hom For any digraph homomorphism h : H −−→ H ′ let us define hom ∗ J the graph homomorphism h : H ∗ J −−→ H ′ ∗ J as:

J

s t

′

Figure 6: Visual support for proof of Claim D.4

Proof. From left to right, we have that (u′ , v ′ ) belongs to a minimal G-homomorphic image h(G) via the digraph hohom momorphism h : G −−→ G′ . In particular, h(u, v) = ′ ′ (u , v ) for some (u, v) ∈ E(G) – cf. Figure 6 for visual aid. hom The graph homomorphism h∗J : G ∗ J −−→ G′ ∗ J must contain {û′ , v̂ ′ } by definition, since its image onto Juv is precisely the copy Ju′ v′ where {û′ , v̂ ′ } lies. We now show that it is minimal. By means of contradiction, suppose it is not minimal, and hence that there is some graph homomorphism hom g : G ∗ J −−→ G′ ∗ J such that g(G ∗ J) ⊊ h∗J (G ∗ J). By hom Claim D.3 this means that g = f ∗J for some f : G −−→ G′ . ∗ J By definition of f this would imply that f (G) ⊊ h(G) contradicting the minimality of h(G). From right to left, we have that (û′ , v̂ ′ ) belongs to a minimal G ∗ J-homomorphic image h(G ∗ J) via the graph hom homomorphism h : G ∗ J −−→ G′ ∗ J. In particular, ′ ′ h({û, v̂}) = {û , v̂ } for some {û, v̂} ∈ E(G ∗ J) – cf. Figure 6 for visual aid. By Claim D.3, h = f ∗J for some hom f : G −−→ G′ . Let us show that f (G) is a minimal G-homomorphic image containing (u′ , v ′ ). By definition of f ∗J , {û, v̂} is the edge of some copy Juv (for some (u, v) ∈ E(G)) corresponding to {û′ , v̂ ′ } in Ju′ v′ . Hence, h(u, v) = (u′ , v ′ ) and thus (u′ , v ′ ) ∈ f (G). If f (G) is not hom minimal, meaning that there is some g : G −−→ G′ with ∗ ∗ g(G) ⊊ f (G), note that g J (G ∗ J) ⊊ f J (G ∗ J), which is in contradiction with our hypothesis. ♢ Since, by Claim D.3, J is fixed and independent of G, G′ , we have that Claim D.4 yields a polynomial-time reduction and we conclude the proof.