Paper deep dive
How Hard is it to Decide if a Fact is Relevant to a Query?
Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 96%
Last extracted: 4/27/2026, 3:20:11 AM
Summary
The paper investigates the computational complexity of determining if a specific fact is 'relevant' to a Boolean conjunctive query (CQ) or an ontology-mediated query (OMQ). A fact is relevant if it belongs to at least one minimal subset of the database that satisfies the query. The authors identify self-joins as the primary cause of increased complexity (often $\Sigma^p_2$-completeness). They prove that by bounding self-join width or interaction width (in the case of DL-Lite_R ontologies), the complexity of the relevance problem reduces to the complexity of the query evaluation problem itself (e.g., NP or LogCFL).
Entities (6)
Relation Signals (4)
Minimal Support β defines β Query Relevance
confidence 100% Β· f is relevant to q in D if it belongs to some minimal support of q in D.
Interaction Width β generalizes β Self-join Width
confidence 100% Β· interaction width (which generalizes both self-join width and a recently introduced 'interaction-free' condition)
Self-join β increasescomplexityof β Query Relevance
confidence 100% Β· Our work identifies self-joins (multiple atoms with the same relation) as the culprit.
DL-Lite_R β usedin β Ontology-mediated Query
confidence 100% Β· consisting of a CQ and DL-Lite_R ontology
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We consider the following fundamental problem: given a database D, Boolean conjunctive query (CQ) q, and fact f in D, decide whether f is relevant to q wrt. D, i.e., does f belong to a minimal subset S of 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, $\Sigma^p_2$-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-Lite_R 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.
Tags
Links
- Source: https://arxiv.org/abs/2604.22422v1
- Canonical: https://arxiv.org/abs/2604.22422v1
Trouble viewing inline? Open PDF directly β
Full Text
101,961 characters extracted from source content.
Expand or collapse full text
How Hard is it to Decide if a Fact is Relevant to a Query? 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. Rel- evance has already been shown to be harder than query evalu- ation: namely, Ξ£ p 2 -complete for CQs, even over a binary sig- nature. We further observe that NP-hardness applies already to (acyclic) chain CQs. Our work identifies self-joins (multi- ple 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-Lite R ontology, namely that rel- evance 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 meth- ods for explaining why a given query answer holds, re- sulting 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 mea- sures, 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 ontology- mediated query answering (OMQA) (Poggi et al. 2008; Bienvenu and Ortiz 2015; Xiao et al. 2018), where query an- swers are computed by reasoning over the information con- tained 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 com- pute minimal subsets of facts that make the query hold (Bi- envenu, Bourgaux, and Goasdou Μ e 2019; Ceylan et al. 2019; Ceylan et al. 2020; Ceylan et al. 2025), while some re- cent work has begun to explore quantitative responsibil- ity 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 fun- damental 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 on- tology), a fact will be assigned a positive score iff it is rele- vant (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 Μ naloza 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 se- mantics (Bienvenu, Bourgaux, and Goasdou Μ e 2019). We briefly summarize here what is known about the com- plexity of the query relevance task, which has been explored for ontology-mediated queries (OMQs) formulated in de- scription logic and existential rule ontology languages (Cey- lan et al. 2019; Ceylan et al. 2020; Ceylan et al. 2025). For data complexity, in which the size of the query and ontol- ogy are treated as fixed, the task is known to be tractable arXiv:2604.22422v1 [cs.DB] 24 Apr 2026 Query evaluation Relevance sjw<βsjwβ hw<βLogCFL-cLogCFL-cNP-c β hwβNP-cNP-cΞ£ p 2 -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 Ξ£ p 2 -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). In- deed, 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 (ontology- mediated) query languages for which the size of minimal supports is unbounded, the relevance problem becomes NP- hard in data complexity. For combined complexity, the rel- evance task has been proven Ξ£ p 2 -complete for conjunctive queries, even in the absence of an ontology and with only binary relations (Vaicenavi Λ cius 2020). Additional combined complexity results have been established for various kinds of OMQs, with complexities ranging from Ξ£ p 2 to 2EXPTIME, depending on the expressivity of the ontology language. While the preceding results show that relevance is gener- ally harder than query evaluation, to the best of our knowl- edge, there has not been any exploration of what precisely makes relevance harder than query evaluation, nor the re- lated question of which restrictions can lower the complex- ity. 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 rela- tion) that make relevance harder than query evaluation. We start by observing that for βwell-behavedβ classes of con- junctive queries, like acyclic CQs and CQs of bounded hy- pertreewidth, for which query evaluation is tractable, the rel- evance problem is NP-complete. In fact, relevance is NP- hard even for acyclic chain CQs of the form R(x 1 ,x 2 ) β§ R(x 2 ,x 3 ) β§ Β· β§ R(x nβ1 ,x n ) on a single relation (The- orem 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) on- tology. After observing that both conjunction (β) and quali- OMQ evaluationRelevance iw<βiwβiw<βiwβ tw=1, β<βNL-cLogCFL-cNL-cNP-c tw <βLogCFL-cNP-cLogCFL-cNP-h twβNP-cNP-cΞ£ p 2 -c Table 2: Complexity results for classes of ontology-mediated queries in (DL-Lite R , CQ), with (un)bounded treewidth (tw), in- teraction 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-Lite R , 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 consist- ing of a CQ and DL-Lite R ontology, bounding the interac- tion width makes relevance no harder than query evaluation. The obtained results, summarized in Table 2, show that si- multaneously 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 homomor- phisms, which underlies the CQ relevance problem. Con- cretely, we study the question of, given two graphs G and G β² , whether a given edge belongs to a minimal homomor- phic image of G in G β² . We consider both directed and undirected variants of this problem, finding that they are both Ξ£ p 2 -complete, thereby providing natural and simple Ξ£ p 2 - complete problems of independent interest. As a corollary, we obtain that Ξ£ p 2 -hardness of CQ relevance already holds over signatures consisting of a single binary relation. Organization After preliminaries in Section 2, we intro- duce 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 Sec- tion 6, we introduce and study the Minimal Homomorphism Problem for graphs. We conclude in Section 7 with a dis- cussion 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 (Abite- boul, 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 ma- chine, and Ξ£ p 2 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 deci- sion problems reducible to a context-free language, consid- ered highly parallelizable, where Lβ NLβ LogCFLβ AC 1 β NC 2 β Pβ NPβ Ξ£ p 2 . Databases A (relational) database D is a finite set of rela- tional 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 first- order 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 for- mula. By atoms(q) we denote Ξ± i i . We shall only be in- terested 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. A homomorphism q hom ββ 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(t 1 ),...,h(t n )) β D for every atom R(t 1 ,...,t n ) in q. A homomorphism h : q hom ββ q β² between CQs is defined similarly. A CQ is a core if all the homomorphisms h : q hom ββ q are injective. It is known that for any (Boolean) CQ q, D |= q iff there is a homomorphism h : q hom ββ D, and that a CQ q entails another CQ q β² iff q β² hom ββ 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 or CQ X , the notion of homomorphism h : q hom ββ 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 forC 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 other- wise, 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 undi- rected graph, containing the edget,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 read- ers to (Gottlob et al. 2016, Definition 3.1 & following para- graph) 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 log- space 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 ABoxA and a TBox T , constructed from mutually disjoint sets N C of concept names (unary relation names), N R of role names (binary re- lation names), and N I of individual names (here called con- stants). An inverse role has the form R β , with Rβ N R , and we use N Β± R = N R βͺR β | Rβ N R for the set of roles. The ABox is a finite set of facts (i.e., a database) over the binary signature given by N C and N R . 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 DL- Lite family (Calvanese et al. 2007). We shall in particular consider the DL-Lite R 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 β N C and P β N Β± R . The logic DL-Lite core is ob- tained from DL-Lite R by disallowing role inclusions. Another prominent lightweight DL that we shall briefly mention isEL, where the TBox consists of general concept inclusions (GCIs) D 1 β D 2 between concepts of the form: D :=β€| A| Dβ D |βR.D Aβ N C ,Rβ N R 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 β N I to a I β β I , each A β N C to A I β β I , and each R β N R to R I β β 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) β R I , (C β D) I = C I β© D I . An interpretation I satisfies a fact A(a) (resp. P (b,c)) if b I β A I (resp. (b I ,c I ) β P I ). I satisfies a (concept or role) inclusion Gβ H if G I β H I . We callI a model of a KBK, denotedI |=K, ifI satisfies all axioms inT and all facts inA. A KBK is consistent if it has a model. A KBK entails an inclusion or fact Ξ³, writtenK|= Ξ³, if every model I ofK satisfies Ξ³. Likewise, we writeK |= βP (a) to mean a I β (βP ) I in every modelI ofK. Ontology-Mediated Queries We say that a (Boolean) CQ q is entailed from a KBK = (A,T ), writtenK|= q, ifI |= q for every modelI ofK. We may alternatively groupT 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. f 1 f 2 f 3 f 4 q: D: 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 DLL and a queryq β 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 de- fined analogously as before: given an ABoxA 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-Lite R , CQ) (see (Artale et al. 2009; Bienvenu et al. 2018) and references therein). Theorem 2.2. Query evaluation for (DL-Lite R , CQ) is NP- complete. For fixed m β₯ 1, β > 1, the problem is LogCFL- complete for the classes obtained by restricting to (T ,q) s.t. β’ q is acyclic and has at most β leaves, or β’ T is a DL-Lite core TBox and q has treewidth at most m Query evaluation is NL-complete for (DL-Lite R , AQ). Canonical Model Every consistent DL-Lite R KB K = (A,T ) admits a so-called canonical model I A,T , which maps homomorphically into every model ofK. As we shall useI A,T in some of our results, we recall here its definition. For the domain β I A,T ofI A,T , we use the set of all words aP 1 ...P n (nβ₯ 0) such that aβ const(A), P i β N Β± R , and: β’ if nβ₯ 1, then (A,T )|=βP 1 (a) β’ for 1β€ i < n,T |=βP β i ββP i+1 and P β i ΜΈ= P i+1 . Elements in β I A,T (A) will be called anonymous ele- ments. The interpretation function maps each a β const(A) to itself and interprets concept and role names as follows: A I T ,A =aβ const(A)| (A,T )|= A(a)βͺ aP 1 ...P n | nβ₯ 1 andT |=βP β n β A) R I T ,A =(a,b)| R(a,b)βAβͺ (w 1 ,w 2 )| w 2 = w 1 P andT |= P β Rβͺ (w 2 ,w 1 )| w 2 = w 1 P andT |= P β R β ) Our results exploit the following well-known property: Theorem 2.3. For every DL-Lite R KB (A,T ), (A,T )|= q iffI A,T |= q iff there is a homomorphism q hom ββI A,T . 3 Query Relevance Problem To improve the usability of information systems, it is im- portant to be able to explain to users why a given answer a was obtained for the query q. Equivalently, we can rephrase this question in terms of Boolean queries, asking why the Boolean query q(a) obtained by instantiating the free vari- ables 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 f 1 ,f 2 and f 3 . This shows that f 1 , f 2 , and f 3 are all relevant. However, f 4 is not relevant despite ap- pearing in a homomorphic image of q in D, because the only support containing f 4 isf 3 ,f 4 , 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 con- sider minimal inconsistent subsets as supports for an OMQ? We believe it is more natural to separate debugging of in- consistencies 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 inA if f belongs to some minimal support of Q inA. 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. Relevance problem for a classQβ CQ Input:Query q βQ, database D, and fact f β D Question:Is f relevant for q in D? Relevance problem for OMQ class (L,Q) (Qβ CQ) Input:OMQ (T ,q)β (L,Q), ABoxA such that (A,T ) is consistent, and fact f βA Question:Is f relevant for (T ,q) inA? Remark 3.5. We treat these as standard decision problems in the complexity-theoretic sense, rather than βpromise prob- lemsβ. That is, an algorithm forQ must first verify that the input string is a valid encoding of a query fromQ. β³ We conclude this section by stating some easy upper and lower bounds. First, we can observe that the relevance prob- lem 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 forQ is in NP C , where C is the complexity class of the query evaluation problem forQ. 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 com- plexities of the two problems as follows: Proposition 3.7. For any class Q of (ontology-mediated) CQs, the query evaluation problem forQ is in L C , where C is the complexity class of the relevance problem forQ. 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 fol- lowing result provides a more direct (many-one) reduction: Proposition 3.8. LetQ be any class of CQs such that q βQ implies that there exists q β§βx.A(x) β Q, for some rela- tion 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 forQ. 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 Λ cius 2020, Thm. 4.30) 2 The rel- evance problem for CQs is Ξ£ p 2 -complete, and Ξ£ p 2 -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 hyper- tree 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 re- strictions 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(x 1 ,x 2 ) β§ R(x 2 ,x 3 ) β§ Β·β§ R(x nβ1 ,x n ) 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 NP- complete. Hardness holds even for the class of chain CQs. Proof sketch. The minimal supports for the n-atom chain CQ q n 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 q n . 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 q n+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 unbound- edly 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 prob- lem 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 h Ξ± : Ξ± hom ββ D, h Ξ² : Ξ² hom ββ 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 M q : =Ξ±[i] : Ξ±,Ξ± β² are mergeable atoms of q with Ξ±[i]ΜΈ= Ξ± β² [i] and Ξ±[i]β vars(q). This definition can be viewed as a generalization and im- provement of a prior notion of self-join width introduced in (Bienvenu, Figueira, and Lafourcade 2025a), see Re- mark 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 asM q β² =y. β³ For classes of bounded self-join width CQs, the complex- ity of relevance matches that of query evaluation: 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 classSJ 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 CQq is inSJ k belongs to NL. (b) ComputingM q 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 ofM q equal among them or among the con- stants contained in the query. For this, consider the set E q of all equivalence relations overM q βͺ 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 q E be the result of collapsing all the terms in the same equivalence class in q and removing repeated atoms. Let us further define q ΜΈ= E as the result of adding a inequality atom t ΜΈ= t β² to q E for each pair (t,t β² )β (M q Γ (M q βͺ const(q)))\ E. Intuitively, q ΜΈ= E is the query stating that variables ofM q shall be collapsed 3 exactly according to E. Lemma 4.8. The problems of testing, given q β SJ k and two equivalence relations E,E β² from E q , whether q E hom ββ q E β² holds, whether q ΜΈ= E hom ββ q ΜΈ= E β² holds, and whether q E is a core, are all in L. The interest of the q ΜΈ= E queries stems from the fact that, for a well-chosen subset ofE 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 e E q β 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(q E ) for some E β e E q and homomorphism h : q ΜΈ= E hom ββ D. Further, given an equivalence class E βE q , one can test in L whether E β e E q (under the encoding of Remark 4.7). 3 If the equivalence class X contains a constant c, then all vari- ables of X are replaced by c; otherwise, we choose a representative variable xβ X and replace all variables of X by x. Proof. The existence of e E q essentially follows from the de- velopments 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 e E q : =E βE q : q E is a core, and for all E β² βE q , if q ΜΈ= E β² hom ββ q ΜΈ= E then q ΜΈ= E hom ββ q ΜΈ= E β² . Claim 4.10. e E q satisfies the 1β 2 equivalence. Since the cardinalities of the equivalence classes inE q and e E q 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 M q 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 β e E q in L by Lemma 4.9. We next check that there is some R-atom R(t) in q E βconsistentβ with our input fact R(c), that is, so that R(t) hom ββ R(c). Consider now the result Λq of replacing in q ΜΈ= E every t[i] which is a vari- able with the constant c[i]. Observe that, due to Lemma 4.9, any homomorphic image of Λq is a minimal support of q con- taining f , and further if there exists a minimal support of q containing f , there must be some E β e E q and atom con- sistent with f as described before. All these operations can be performed in logarithmic space since there are logspace transductions from q to q ΜΈ= E , and from q ΜΈ= E 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 evalua- tion 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 equiva- lent 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 com- plexity 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 hard- ness for the relevance problem, which make the problem dif- ficult even when restricted to atomic queries. Indeed, a first source of hardness stems from the ability to capture reach- ability in the data, which in DLs can be done using quali- fied existential restrictions, present inEL 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 com- bined complexity) for any DLL that can expressβR.Aβ A. Proof. Any directed graph G can be represented as an ABoxA G which contains R(v 1 ,v 2 ) for each directed edge (v 1 ,v 2 ). Then, to decide whether an edge (v 1 ,v 2 ) 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(v 1 ,v 2 ) is relevant for the OMQ (βR.Aβ A,A(s)) w.r.t. the ABoxA G βͺA(t). Observe that the preceding result precludes the possibility of obtaining tractability for classes of OMQs defined by bound- ing any combination of width notions or any other parame- ters 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 DLL with concept conjunction and GCIs. Proof. We reduce from SAT. Consider a CNF formula Ο : = V m j=1 c j with variables in V : = v 1 ...v n . We build the AQ q : = A(d), the ABoxA : = X(d),P i (d),N i (d) | 1 β€ iβ€ n, and the TBoxT : =T t βͺT p βͺT n βͺT c with: T t :P i β N i β A| iβ [n] T p :P i β C j | v i β c j T c :X β d m j=1 C j β A T n :N i β C j | v i β c j 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 ad- mit 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 TBoxT is formulated in DL-Lite R . We consider DL-Lite R 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-Lite R , CQ), obtaining the same complexity as for CQs in databases: Proposition5.3.Therelevanceproblemfor (DL-Lite R , CQ) is Ξ£ p 2 -complete. 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-Lite R , 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-Lite R , CQ) such that q is acyclic and has at most β leaves (for any fixed β > 1) β’ class of OMQs (T ,q)β (DL-Lite core , 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 ex- isting 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 pos- itive 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-join- free 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 self- joins in q by replacing each instance of a relation R with a fresh R i , along with the axiom R i β R that makes R i a particular instance of a R. Since D does not contain any of those R i , 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 OMQs 4 . 4 We reformulated slightly the original definition to suit our pur- poses, but it yields the same notion of interaction-free OMQ. Ξ± R Ξ² R β² f 1 R f 2 x A y z A c A d f 3 q: A: Figure 2: Interacting atoms whereT : =R β² β R, R β² β R β . Definition 5.6 (Interacting query atoms). Given an OMQ Q = (T ,q) β (DL-Lite R , CQ), we say that distinct atoms Ξ±,Ξ² ofq interact if there exists a factf such that (f,T )|= Ξ± and (f,T )|= Ξ² (with Ξ± and Ξ² treated as Boolean CQs). An atom Ξ± interacts with itself if there exist a fact f , homo- morphisms h 1 : Ξ± hom ββ I f,T and h 2 : Ξ± hom ββ I f,T , and variable x β vars(Ξ±) such that h 1 (x) β const(f ) and h 2 (x)ΜΈ= h 1 (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-Lite R , 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 f 1 , but both also inter- act with themselves by the two distinct homomorphisms that map to (c,d) in either direction, since I f 1 ,T β c R ββ 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 f 1 : the former can only be extended with z 7β d, whose image strictly contains the minimal supportf 2 ,f 3 . β³ We propose to generalize interaction-free OMQs by intro- ducing the notion of interaction width: Definition 5.9 (Interaction width). The interaction width of an OMQ Qβ (DL-Lite R , CQ) is|int-atoms(Q)|. Observe that, as expected, interaction-free OMQs have interaction width zero. It is also worth noting that, differ- ently 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 = (T n ,q n ) where q n : = V n i=1 R i (x iβ1 ,x i ) andT : = R i β R has interaction width n since Ξ± hom ββ 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 estab- lishing the following theorem, which shows that by bound- ing 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 ev- ery subclass of (DL-Lite R , 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 ABoxA. 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) -atoms(Q) (and no other atom), or (i) one or more atoms in int-atoms(Q). We start by testing whether the given fact f βA is poten- tially relevant to some atom of q, and return no if not. This can be done in NL by guessing a query atom and perform- ing atomic query evaluation. We may thus focus on testing relevance for potentially relevant facts of types (i) or (i). Consider first the case where f is potentially relevant to a single atom Ξ± f β atoms(q)\ int-atoms(T ,q). Then there exists h : Ξ± f hom ββ I f,T , and moreover, every such ho- momorphism 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 di- rect 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 sup- port for q. The following lemma makes precise which prop- erties 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 |S|β€ k and h S : int-atoms(Q) hom ββI S,T such that: 1. if xβ shared-vars(T ,q), then h S (x)β const(A) 2. (A,T ) |= q h S where q h S is obtained by remov- ing all atoms in int-atoms(T ,q) and replacing x β shared-vars(T ,q) by h S (x) 3. there is no S β² β S and h S β² : int-atoms(Q) hom ββ I S β² ,T such that h S β² (x) = h S (x) for every x β shared-vars(T ,q). This suggests the following procedure for deciding rele- vance of facts of type (i): iterate (in logspace) over all can- didate sets S and homomorphisms h S and check whether the required conditions hold. We terminate either when some S has been shown to satisfy the conditions (outputting βrele- vantβ) 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 q h S . For the third condition, we must perform a second (logspace) exploration of possible S β² β S and h S β² . 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 non- deterministic guess to verify (A,T )|= q h S in condition 2). For the LogCFL and NL results, we further need to es- tablish 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-Lite R , 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 sep- arately test for the existence of a homomorphism h : q hom ββ I A,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 homomor- phism in NL. For the second kind of homomorphism, we show that all variables are mapped either to an ABox con- stant or to an anonymous element aP 1 ...P n with n β€ k, enabling the reuse of techniques developed for bounded- depth ontologies (Bienvenu et al. 2018). Although Theorem 5.15 cannot be used directly to eval- uate q h S (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 pred- icates, 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 poten- tial relevance), followed by evaluating the OMQ (T ,q -Ξ± f ). This makes relevance for this class of OMQs easily imple- mentable 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 correspond- ing query evaluation problem, and that the Ξ£ p 2 -hardness al- ready 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 Ξ£ p 2 - 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 Λ G β² of G β² such that V ( Λ G β² ) = Im(h) and E( Λ G β² ) = (h(v),h(v β² )) : (v,v β² ) β E(G) for some h : G hom ββ G β² . We shall sometimes write h(G) to de- note Λ G β² . The definition for graphs is analogous. Such G- homomorphic 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 di- rected (MinHom d ) and undirected (MinHom u ) versions. MinHom u (resp. MinHom d ) problem Input:A pair G,G β² of graphs (resp. digraphs), and an edge eβ E(G β² ). Question:Is e in some minimal G-homomorphic im- age on G β² ? The problem MinHom d is the natural equivalent to the relevance problem on a single binary relation: Lemma 6.1. There are logspace many-one reductions be- tween MinHom d and the relevance problem for the class of constant-free CQs over a single binary relation. As we show, it remains Ξ£ p 2 -complete. Theorem 6.2. MinHom d is Ξ£ p 2 -complete. Proof sketch. The upper bound is straightforward. For the lower bound, we reduce from the relevance problem over binary relations R 1 ,...,R n , known to be Ξ£ p 2 -hard (Theo- rem 4.1). Given an input D,q,f of the relevance problem we consider digraphs G q ,G D and an edge e f β E(G D ) so that this is a positive instance of MinHom d iff D,q,f is positive for relevance. The idea is simply to replace each atom or fact R i (a,b) with a long directed path from a to b containing a short directed cycle of a prime length p i in the middle, where p 1 < Β· < p n 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 p n to ensure that the only βshortβ cycles of length β€ p n are the ones of these gadgets. In this way, we can build both G q from q and G D from D. Since prime p i -cycles can only be homo- morphically mapped to p i -cycles, and the long paths prevent creating any other short cycle, a homomorphism q hom ββ D can be equivalently seen as a homomorphism G q hom ββ G D from prime cycles to prime cycles. By taking any edge e f of the cycle contained in the replacement of fact f in G D , we have that e f belongs to a minimal G q -homomorphic image on G D iff f is relevant for q in D. As a corollary, we have that the relevance problem is al- ready hard for CQs using a single binary relation. Corollary 6.3 (of Theorem 6.2 and Lemma 6.1). The rele- vance problem for CQs is Ξ£ p 2 -complete even on signatures having a single binary relation. Theorem 6.4. MinHom u is Ξ£ p 2 -complete. Proof sketch. The lower bound is more involved than for MinHom d 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 MinHom d by making use of graph- theoretic techniques known as βreplacement methodsβ. 5 The i-th prime number p i 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-Lite R -mediated) CQs hinges fundamentally on the number of atoms (or of variables from different atoms) that may interact with a fact in the follow- ing sense: if we restrict the number of self-join variables or interacting atoms, then the complexity of relevance is es- sentially 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 al- gorithms 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 (hy- per)treewidth, then relevance is in polynomial time, and oth- erwise 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 evalu- ation, 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 parame- ter (Grohe 2007). Hence, a promising direction is to investi- gate the parameterized complexity of the relevance problem. Other Ontology Languages We conjecture that the notion of interaction width we introduced for DL-Lite R can be fruitfully applied also to linear existential rules, as they sim- ilarly 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 single- ton support property (since multiple facts may needed to in- fer a query atom), such as DL-Lite Horn , 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 pre- cludes any positive results for classes of DL-Lite Horn OMQs obtained via bounding parameters dominated by the query size. For non-first-order-rewritable DLs like EL, Proposi- tion 5.1 effectively rules out any tractability results in com- bined 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 rele- vance 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 incon- sistency. 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-Lite R , relevance of inconsis- tency 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 un- der inconsistency-tolerant semantics. Interestingly, existing proposals of explanations for repair-based semantics (Bien- venu, Bourgaux, and Goasdou Μ e 2019) are defined via mini- mal 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 iden- tifying 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-Lite R with bounded in- teraction width (in line with an analogous result shown in the database setting for classes of CQs with bounded self- join 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 IN- TENDED (ANR-19-CHIA-0014) and EXPAND (ANR-25- CE23-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+R), 167β182. Artale, A.; Calvanese, D.; Kontchakov, R.; and Za- kharyaschev, 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 cir- cuit complexity. Journal of the ACM 65(5):28:1β28:51. Bienvenu, M.; Bourgaux, C.; and Goasdou Μ e, F. 2019. Com- puting and explaining query answers over inconsistent DL- Lite knowledge bases. Journal of Artificial Intelligence Re- search (JAIR) 64:563β644. Bienvenu, M.; Figueira, D.; and Lafourcade, P. 2024a. Shap- ley value computation in ontology-mediated query answer- ing. In Principles of Knowledge Representation and Rea- soning (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 (PACM- MOD) 2(2:PODS):1β24. Bienvenu, M.; Figueira, D.; and Lafourcade, P. 2025a. Shap- ley 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. Shap- ley revisited: Tractable responsibility measures for query answers. CoRR abs/2503.22358v3. Extended version of (Bi- envenu, Figueira, and Lafourcade 2025a). Bienvenu, M.; Figueira, D.; and Lafourcade, P. 2025c. Tractable responsibility measures for ontology-mediated query answering. In Principles of Knowledge Representa- tion 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 Princi- ples 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. Jour- nal of Automated Reasoning (JAR). Calvanese, D.; Ortiz, M.; Simkus, M.; and Stefanoni, G. 2013. Reasoning about explanations for negative query an- swers in DL-Lite. Journal of Artificial Intelligence Research (JAIR) 48:635β669. Ceylan, Μ I. Μ I.; Lukasiewicz, T.; Malizia, E.; and Vaicenavi- cius, A. 2019. Explanations for query answers under exis- tential rules. In International Joint Conference on Artificial Intelligence (IJCAI), 1639β1646. Ceylan, Μ I. Μ I.; Lukasiewicz, T.; Malizia, E.; and Vaicenavi- cius, A. 2020. Explanations for ontology-mediated query answering in description logics. In Proceedings of the Euro- pean Conference on Artificial Intelligence (ECAI), 672β679. Ceylan, Μ I. Μ I.; Lukasiewicz, T.; Malizia, E.; and Vaicenavi- cius, A. 2025. Explanations for query answers under exis- tential rules. Artif. Intell. 341:104294. Chandra, A. K., and Merlin, P. M. 1977. Optimal imple- mentation of conjunctive queries in relational data bases. In Symposium on Theory of Computing (STOC), 77β90. ACM Press. Chen, J.; Ma, Y.; Pe Μ naloza, R.; and Yang, H. 2022. Union and intersection of all justifications. In International Con- ference on Semantic Web (ESWC), volume 13261 of Lecture Notes in Computer Science, 56β73. Springer. Eiter, T., and Gottlob, G. 1995. The complexity of logic- based 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 Λ set Λ ril, 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. Logi- cal 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 Μ naloza, 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 on- tologies. In Journal on Data Semantics X, 133β173. Rosser, B. 1939. The n-th prime is greater than nlog(n). Proceedings of the London Mathematical Society 2(1):21β 44. Vaicenavi Λ cius, A.2020.Explanations for ontology- mediated 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. Ontology- based data access: A survey. In International Joint Confer- ence on Artificial Intelligence (IJCAI), 5511β5519. e s t G ... Figure 3: Database D G 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 forQ is in L C , where C is the complexity class of the relevance problem forQ. 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 rele- vant. 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 NP- complete. Hardness holds even for the class of chain CQs. Proof. The fact that the problem is in NP is a direct conse- quence 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 HamP s,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 D G : = 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 q G : = r n+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 D G of the form r nβ1 (s,t). P ΜΈ|= q be- cause it is short of two edges, howeverPβͺe,R(t,t β² ) is a minimal support for q G , witnessing that e is relevant. If there exists no hamiltonian path from s to t, any homo- morphic image of q G that contains e will necessarily contain repeated vertices, hence a cycle. Now a minimal support for q G 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 M old 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 M q β M old q . For example, the classC =q n : n > 0 of Boolean CQs q n : =βx β² y 1 ...y n R n (x,y 1 ,...,y n )β§ R n (x β² ,y 1 ,...,y n )β§ S(x,x β² ) has unbounded self-join width with the definition above of (Bienvenu, Figueira, and Lafourcade 2025a) since M old q n = x,x β² ,y 1 ,...,y n . However, it has self-join width 2 with our definition, sinceM q n = x,x β² . In this way, the alter- native 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 setM q 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) check- ing if there is one such E meeting the criteria we describe next. We first check that E β e E q in L by Lemma 4.9. We next check that there is some R-atom R(t) in q E 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 iter- ate, 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 q ΜΈ= E 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 con- taining f .Indeed, if S is a homomorphic image of Λq, there is a homomorphism h : Λq hom ββ S such that h(Λq) = S. Ex- tending h to the variables of q E in the expected way (i.e., by mapping t[i] to c[i] for every variable t[i]) then yields a homomorphism h β² such that h β² : q ΜΈ= E hom ββ S and further h β² (q E ) = S. Then, by Lemma 4.9 (2 β 1), S is a mini- mal support of q. Further, if there exists a minimal support of q containing f , there must be some E β e E q 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 q ΜΈ= E , and from q ΜΈ= E 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 evalua- tion 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 Proposi- tion 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 CQq is inSJ k belongs to NL. (b) ComputingM q from a CQ q βSJ k is in L. Proof. (a)Observe that testing whether two atoms R(t 1 ,...,t n ) and R β² (t β² 1 ,...,t β² m ) are mergeable is equiva- lent to testing that (i) R = R β² , (i) n = m, and (i) the graph G = (V,E) has no two distinct constants in the same connected component, where V = t 1 ,...,t n ,t β² 1 ,...,t β² m and E = t i ,t β² i : i β [n]. For testing (the negation of) (i) 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 Μ enyi Theorem. For testing whether q βSJ k we computeM q 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 computeM q of the previous paragraph be- comes L. Lemma 4.8. The problems of testing, given q β SJ k and two equivalence relations E,E β² from E q , whether q E hom ββ q E β² holds, whether q ΜΈ= E hom ββ q ΜΈ= E β² holds, and whether q E is a core, are all in L. Proof. If such q E hom ββ q E β² exists, then it must be identi- tary on all variables outsideM q . There are constantly many remaining variables, and we can then go through all pos- sible O(|vars(q E β² ) βͺ const(q E β² )| k ) mappings for these in logarithmic space and checking whether some of these map- pings yields a homomorphism. The same argument applies for checking q ΜΈ= E hom ββ q ΜΈ= E β² by restricting the verification to mappings which are injective onM q . Finally, note that q E is not a core if, and only if, there is E β² β E q such that q E hom ββ q E β² , q E β² hom ββ q E , and q E β² has fewer atoms than q E . 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 for hom ββ testing described above. Claim 4.10. e E q satisfies the 1β 2 equivalence. g(q E β² )h(g(q E β² )) (atom injective) hom h / hom g Ξ± h(Ξ±) h(q E ) =S q ΜΈ= E β² q ΜΈ= E β² Figure 4: Visual support for proof of Lemma 4.9. Proof. 1β 2If S β D is a minimal support for q, let h : q hom ββ 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 all t,t β² β M q βͺ const(q)). Hence, Λ h : q ΜΈ= E hom ββ S via the relativization Λ h of h onto the variables of q ΜΈ= E . Observe that Λ h : q ΜΈ= E hom ββ S atom injective, in the sense that the size of S equals the number of atoms of q E (cf. Claim B.2). We need to show that E β e E q . If q E is not a core, then it is easy to see that S cannot be a minimal support; let us hence assume that q E is a core. By contradiction, suppose that g : q ΜΈ= E β² hom ββ q ΜΈ= E but q ΜΈ= E ΜΈ hom ββ q ΜΈ= E β² for some E β² β E q . This means that g(q E β² ) does not contain all atoms of q E : let Ξ± be one of these missing atoms. See Figure 4 for an illustration. Note that h(Ξ±) β S cannot be in h(g(q E β² )) since h atom injective; hence h(g(q E β² ))β S contradicting the fact that S is a minimal support of q. 2β 1By means of contradiction, suppose S is the h- image for h : q ΜΈ= E hom ββ D (i.e., h(q E ) = S) where E β e E q , but S is not minimal since there is some g : q hom ββ S β² with S β² β S. Let E β² β E q be the equivalence relation induced by g, so that f (q E β² ) = S β² for some f : q ΜΈ= E β² hom ββ D β as before, note that f atom injective: |atoms(q E β² )| = |S β² | (cf. Claim B.2). Since f (q E β² ) β h(q E ), it follows that q ΜΈ= E β² hom ββ q ΜΈ= E (cf. Claim B.3), and hence that, since E β e E q , we must also have q ΜΈ= E hom ββ q ΜΈ= E β² . By composing the ho- momorphisms q ΜΈ= E hom ββ q ΜΈ= E β² and f : q ΜΈ= E β² hom ββ S β² we ob- tain that|S β² | is the number of atoms of q E (by Claim B.2). But this is in contradiction with what we have already estab- lished, namely, that the number of atoms of q E is|S| via the atom injective homomorphism h, and that |S| ΜΈ= |S β² | since S β² β S. Claim B.2 (taken from (Bienvenu, Figueira, and Lafourcade 2025b, Claim 50)). If a homomorphism h : q ΜΈ= E hom ββ D is so that h(q E ) = S, then|S| is the number of atoms of q E 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- phisms h : q ΜΈ= E hom ββ D and h β² : q ΜΈ= E β² hom ββ D with h β² (q E β² )β h(q E ), then there is a homomorphism q ΜΈ= E β² hom ββ q ΜΈ= E . 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) -atoms(Q) (and no other atom), or (i) 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 h : q hom ββ I S,T , but minimality implies that q does not em- bed homomorphically into I S\f,T . Due to the canonical model definition, there must thus exist some atom Ξ± f β q such that Ξ± f hom ββ 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 Ξ² f hom ββI f,T , so Ξ± f is the unique atom for which f is po- tentially relevant. Otherwise, Ξ± f β int-atoms(Q), hence f is potentially relevant for at least one atom in int-atoms(Q), as in condition (i). 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 . It follows that there is a homomorphism h : q hom ββ I S,T . Moreover, since f is potentially relevant to Ξ± f β atoms(q)\ int-atoms(T ,q), there is a witnessing homomorphism h β² : Ξ± f hom ββ I f,T . Since Ξ± f β atoms(q)\ int-atoms(T ,q), we know that if x β vars(Ξ± f ) and h β² (x) β const(A), then h β² (x) = h(x). It follows that h also witnesses that q -Ξ± f hom ββ I S,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 ) inA. We claim that Sβͺf is a minimal support for (T ,q) inA: β’ We first show that S βͺ f is a support for (T ,q) in A. Indeed, we know that there is a homomorphism h : q -Ξ± f hom ββI S,T and a second homomorphism h β² : Ξ± f hom ββ 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 see that h β² defines a homomorphism q hom ββ I Sβͺ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 con- tradiction that S βͺ f is not a minimal support, and let S β² β S βͺ f be a stricter smaller support.If f ΜΈβ S β² , then q hom ββ I S,T . By appealing to the canon- ical model construction, there must exist f β² β S such that Ξ± f hom ββ I f β² ,T , which contradicts our assumption that Ξ± f ΜΈβ int-atoms(T ,q). Thus, it must be the case that S β² β S and q hom ββ I S β² βͺ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 witnessing q hom ββ I S β² βͺf,T that sends x β vars(Ξ± f ) to a constant different from h β² (x). Both options are disal- lowed since Ξ± f ΜΈβ int-atoms(T ,q), yielding the desired contradiction. Lemma C.1. Let x β shared-vars(T ,q) and h : q hom ββ I A,T . Then h(x)β const(A). Proof. Assume for a contradiction that h(x) is an anony- mous constant. By construction of the canonical model in DL-Lite R , any anonymous element w = aP 1 ...P n ofI A,T can be generated by a fact f w β A (i.e., w β I f w ,T ) and this f w will also generate all intermediate aP 1 ...P k with 1 β€ k < n as well as all facts of I A,T over these ele- ments. In particular, if we take Ξ± β int-atoms(Q) and Ξ² β atoms(q)\ int-atoms(T ,q) that contain x (as per the defini- tion of shared-vars(T ,q)), and denote by w the anonymous constant of h(Ξ±,Ξ²) that is the furthest into the anony- mous region, then we will have such an f w s.t. h(Ξ±,Ξ²)β I f w ,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 |S|β€ k and h S : int-atoms(Q) hom ββI S,T such that: 1. if xβ shared-vars(T ,q), then h S (x)β const(A) 2. (A,T ) |= q h S where q h S is obtained by remov- ing all atoms in int-atoms(T ,q) and replacing x β shared-vars(T ,q) by h S (x) 3. there is no S β² β S and h S β² : int-atoms(Q) hom ββ I S β² ,T such that h S β² (x) = h S (x) for every x β shared-vars(T ,q). Proof. First suppose that f is relevant to (T ,q) w.r.t.A. Let S q be a minimal support for (T ,q) in A that contains f , witnessed by h : q hom ββI S q ,T . Necessarily, every fact in S q must be potentially relevant to some atom in q w.r.t. S, oth- erwise it could be removed, contradicting minimality of S q . Now let S β β S q be the set of facts in S q 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 di- alects (like DL-Lite R ) where the minimal support of a query cannot contain more facts than the atoms in the query. More- over, by Lemma 5.12, the facts in S β cannot be used to sat- isfy the other atoms not in int-atoms(Q). Thus, assuming |S β | > k contradicts our assumption of minimality, which yields|S β |β€ k, as required. Next we note that from h : q hom ββ I S q ,T , we obtain a homomorphism h β : int-atoms(Q) hom ββ I S β ,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 im- age of int-atoms(Q) under h maps withinI S β ,T . It remains to prove that S β and h β verify the three conditions. For condition 1, consider some x β shared-vars(T ,q). Since h : q hom ββI S q ,T , Lemma C.1 is applicable and yields h β (x) = h(x)β const(A). For condition 2, it suffices to consider the homomorphism h : q hom ββ I S q ,T . Indeed, by definition of h β , we have h β (x) = h(x) for all variables x in int-atoms(Q), and in particular, for x β shared-vars(T ,q). Thus, h : q h β hom ββ I S q ,T , which shows that S q ,T |= q h β (henceA,T |= q h β ). Finally, to show condition 3, suppose for a contradiction that there exist S β² β S β and h β² : int-atoms(Q) hom ββ I S β² ,T such that h β² (x) = h β (x) for every x β shared-vars(T ,q). In this case, let us consider the set of facts S β q = S β² βͺ (S q \ S β ) and define h β² by setting h β² (x) = h β² (x) for vari- ables occurring in int-atoms(Q), and h β² (x) = h(x) for all remaining x β vars(q). By definition, h β² agrees with h on shared-vars(T ,q). Thus, from h : q h β hom ββ I S q ,T and h β² : int-atoms(Q) hom ββ I S β² ,T , we can infer that h β² is a homomorphism q hom ββ I S β q ,T . This would mean that S β q ,T |= q, contradicting the minimality of S q . We thus conclude that there can be no such S β² β S β and h β² , so con- dition 2 is satisfied. For the other direction, let S β A and h S : int-atoms(Q) hom ββ I S,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 S β q be a minimal support for (T ,q h S ) inA, and h β q : q h S hom ββI S β q ,T a witnessing homomorphism (such S β q and h β q must exist due to condition 2). Letting S β = SβͺS β q , we define a homomorphism h : q hom ββI S β ,T by setting h(x) = h S (x) if x appears in int-atoms(Q) and h(x) = h β q (x) otherwise. Indeed, we know that q h S was ob- tained by replacing each x β shared-vars(T ,q) by h S (x), so the homomorphisms h S and h β q are compatible. It fol- lows 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 β β©S β q , then this implies that S β q is not a minimal sup- port. Indeed, we know that the facts in S are not potentially relevant for any atoms in q h S , so S β q \g must be a support for (T ,q h S ), a contradiction. Thus, it must be the case that g β S. Let S β² = S\g and take any homomorphism h S β² : int-atoms(Q) hom ββ I S β² ,T . Due to condition 2, there must exist x β shared-vars(T ,q) such that h S β² (x) ΜΈ= h S (x). Take Ξ² β atoms(q) \ int-atoms(T ,q) with x β vars(Ξ²). Since Ξ² β int-atoms(T ,q) and h S (x) β const(A), any ho- momorphism of q toI S β \g,T must send x to h S (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 henceA). Theorem 5.15. Query evaluation is in LogCFL for the class of OMQs (T ,q) β (DL-Lite R , 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 suf- fices 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 com- ponents is entailed. Let us thus take some Q = (T ,q) β (DL-Lite R , CQ) with interaction width at most k, and sup- pose 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 intoI A,T . We shall distinguish two kinds of homomor- phisms: 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 ho- momorphism which maps at least one variable to an ABox constant. In this case, we can observe that any such homo- morphism cannot βreachβ an anonymous element aP 1 ...P n if n > k, because connectedness of the query means that we would also need to map variables onto a, aP 1 , . . . , aP 1 ...P nβ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 homo- morphisms that map to ABox constants and anonymous el- ements aP 1 ...P n with n β€ k, we may reuse an existing procedures for DL-Lite R designed for so-called bounded depth ontologies (Bienvenu et al. 2018), where the maxi- mum length of an anonymous element aP 1 ...P n 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. Cru- cially, the depth bound ensures that every anonymous ele- ment 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 aP 1 ...P n is actually present in β I A,T and whether a given such element (resp. pair of elements) be- longs to A I A,T (resp. R I A,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 aP 1 ...P n 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 el- ements whose length is greater than k. We first observe that this means that there is a single fact f q β A such that q hom ββ I f q ,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 ho- momorphism 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 ele- ment w = cP 1 ...P n β β I A,T with P n = 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 β I A,T are defined), and in (b) we donβt actually care about c nor the P 1 ...P nβ1 but only about what holds starting from P N = T . This is because we are considering the subtree rooted ofI A,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 anony- mous 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 poten- tial 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 R 1 ...R l such thatT |= βT β ββR 1 , andT |=βR β i ββR i+1 for 1β€ i < l. 2. it satisfies the query atoms, meaning that if A(x)β q and h(x) = R 1 ...R l , thenT |= R β l β A (orT |= βT β β A if h(x) = Ξ΅), and if S(x,y)β q, then either: β’ h(x) = R 1 ...R l and h(y) = R 1 ...R l+1 and T |= R l+1 β S, or β’ h(x) = R 1 ...R l+1 and h(y) = R 1 ...R l and T |= R β l+1 β S Thus, to sum up, we guess a role T and verify that there exists some element cP 1 ...P n β β I A,T with P n = T . This can be done in NL by first guessing c and some P 1 such that (A,T ) |= βP 1 (a), and then sequentially guessing each P i , keeping only two roles in memory at each time, checking whether T |= P i β P i+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 = cP 1 ...P n β β I A,T with P n = 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 de- cide the existence of any homomorphism of q into β I A,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 com- plete the proof, we need to explain how we can test whether (A,T ) |= q h S , for the queries q h S constructed in Lemma 5.14. Recall first that q h S is obtained from q by (a) re- moving all atoms in int-atoms(T ,q), then (b) replacing x β shared-vars(T ,q) by h S (x). Clearly, (a) cannot ad- versely affect the query structure. So let us now consider q β² h S where we retain (a), but instead of (b), we do the following: add the query atom A c (x), for each x β shared-vars(T ,q) such that h(x) = c, with A c a fresh concept name. We also define an ABox A β² by extending A with the facts A c (c) | h(x) = c,x β shared-vars(T ,q). It is straight- forward to show that (A,T )|= q h S iff (A β² ,T )|= q β² h S Importantly, however, q β² h S has the same treewidth as q, and if q is acyclic, then q β² h 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 ) |= q β² h S . Finally, we note that we can constructA β² fromA and q β² h S from q h S 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 fur- ther 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 be- tween MinHom d 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 = v 1 ,...,v n and V β² = u 1 ,...,u n β² . Con- sider the constant-free CQ q G obtained from G by replacing each (v i ,v j ) β E with an atom R(x i ,x j ), wherex i iβ[n] are pairwise distinct variables. Consider also D G β² as the database obtained from G β² by replacing each (u i ,u j ) β E β² with a fact R(c i ,c j ), where c i iβ[n β² ] are pairwise distinct constants. Observe that an edge (u i ,u j ) is in a minimal G- homomorphic image on G β² if, and only if, the fact R(c i ,c j ) is relevant for the CQ q G on the database D G . Likewise, from any constant-free CQ q over a single bi- nary relation R and database D, we can produce digraphs G q , G D by replacing facts or atoms R(t,t β² ) with edges (v t ,v t β² ), and it follows that a given fact is relevant iff the corresponding edge is in a minimal G q -homomorphic im- age on G D . D.1 Directed Graphs Directed graphs are naturally very close to databases and queries on the signatureR, 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 Ξ£ : = R 1 ,...,R n only Ξ· r i r j P p n+2 C p i P p n+2 P p n+2 C p j P p n+2 C p n+2 C p n+1 C p n+2 C p n+1 c d u c u d Figure 5: Construction for Lemma D.1. The loops labelled C p are simple cycles of length n, and the arrows labelled P p n+2 are simple paths of length 7. The two anchor vertices are u c and u d . containing arity 2 relations. Then there exist two digraphs G q ,G D = (V q ,E q ), (V D ,E D ) such that: 1. there exists a bijective mapping Ξ· from the homomorphic images of q in D to the G q -homomorphic images on G D that preserves the inclusion relation; 2. for every fact f β D, there exists e f β E D s.t. for every homomorphic image S of q in D, f β S iff e f β Ξ·(S); 3. if q is isomorphic to D, then G q = G D . Proof. We build graphs G q ,G D 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 fromq 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 dif- ferent relations in Ξ£. We denote this transformation by Ξ·. We can easily see that Ξ· is a bijection between the subsets of D and setS of subgraphs S of D G such that: 1. for every anchor vertex in S, S also contains its associated C p n+1 and C p n+2 ; 2. for every anchor vertex in S, S also contains at least one P p n+2 that touches it; 3. for every P p n+2 in S, S also contains the coupled P p n+2 and the intermediate C p . The image of Ξ· always has this structure indeed, and Ξ· β1 (S) can be obtained from every S β S by simply removing all C p n+1 s and C p n+2 s then replacing every P p n+2 ββ C p i P p n+2 ββ by R i ββ. We now need to show that every G q -homomorphic image Λ G β² on G D is in S , that Ξ· β1 ( Λ G β² ) is a homomorphic image of q in D, and vice versa. Claim D.2. For any prime number p β©½ p n+2 , the only C p - homomorphic images on G D are the simple C p . Proof. Let p β©½ p n+2 be a prime number. Consider the ho- momorphic image P of a path of length p in G D . Since the anchor vertices are separated by p n+2 β©Ύ p edges, P can only contain one of them (or two if they are both its end- points). Additionally, P cannot contain both the C p n+1 and the C p n+2 attached to an anchor vertex because that would require p n+1 + p n+2 > p edges. P is therefore contained in a subgraph of G D of the form P p n+2 ββ C p β² P p n+2 ββ for some p β² . Now the only strongly connected components of such a subgraph is the C p β² cycle; this means that any C p - homomorphic image on G D , which is a particular case of a C p -homomorphic image since P p hom ββ C p , must be con- tained in C p β² . In fact it must be C p β² as a whole since no proper subset is strongly connected, and, since p and p β² are prime numbers, we have C p β² hom ββ C p β² iff p = p β² . β’ Let h(G q ) be a G q -homomorphic image on G D . By Claim D.2, it must map every anchor vertex of G q to some anchor vertex of G D because they are the only constants at the intersection of a C p n+1 and a C p n+2 . Then every u c P p n+2 ββ C p P p n+2 ββ u d must map to a u h(c) P p n+2 ββ C p P p n+2 ββ u h(d) . At last, every anchor vertex in G q touches a P p n+2 ββ (otherwise there would be a variable of q that ap- pears in no atom) so the same can be said of their image byh. We have thus established that h(G q ) β S . Further, observe that thei-th prime numberp i 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 poly- nomial 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(G q )), it will have a fact R i (c,d) iff there is a u c P p n+2 ββ C p i P p n+2 ββ u d in h(G q ) iff there exist x,y s.t. h(x) = c, h(y) = d and u x P p n+2 ββ C p i P p n+2 ββ u y in G q iff there exist x,y s.t. h(x) = c, h(y) = d and R i (x,y) β q. This means that Ξ· β1 (h(G q )) is a homomorphic image of q in D indeed. Re- ciprocally, at last, Ξ·(S) for any homomorphic image S of q in D is a G q -homomorphic image on G D by construc- tion. 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 e f for f = R i (c,d) inside the corresponding u c P p n+2 ββ C p i P p n+2 ββ u d , 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 iden- tical, we only need to make sure that we build G q and G D 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 Ξ£ p 2 -complete problem: Theorem 6.2. MinHom d is Ξ£ p 2 -complete. Proof. We reduce from the relevance problem for constant- free 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 ir- relevant to q. Then we can apply Lemma D.1 to get our instance G q ,G d ,e f of MinHom d . From conditions 1 and 2, we get that e f is in some minimal G q -homomorphic image on G D iff f is relevant to q in D. D.2 Undirected Graphs We show that the Ξ£ p 2 hardness persists even for the Minimal Homomorphism Problem over undirected graphs. Theorem 6.4. MinHom u is Ξ£ p 2 -complete. Proof. The upper bound is straightforward. For the lower bound, we reduce from the directed version MinHom d of the problem already shown in Theorem 6.2 to be Ξ£ p 2 -hard. Let G,G β² , (u β² ,v β² ) be an instance of MinHom d . We shall base the proof on some known graph-theoretic techniques collec- tively known as βreplacement methodsβ. The following pre- liminary definitions can be found in (Hell and Ne Λ set Λ ril 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 J xy of J , identifying x with s and y with t; assuming that all the copies J xy 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. For any digraph homomorphism h : H hom ββ H β² let us define the graph homomorphism h β J : H β J hom ββ H β² β J as: β’ h β J (w) = h(w) for every w β V (H), β’ for any other vertex w β V (H β J )\ V (H) which is in a J xy copy in H β J , we define h β J (w) to be the corre- sponding vertex of the J h(x)h(y) copy in H β² β J . Claim D.3. There exists a replacement graph J,s,t such that every graph homomorphism G β J hom ββ H β J is equal to f β J for some digraph homomorphism f : G hom ββ G β² . Further, J does not depend on G,G β² and contains an edge non-adjacent tos,t. Proof. The statement follows directly from well-known re- sults. 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 Λ set Λ ril 2004, Figure 4.7) defines a fam- ily of replacement graphs G k ,a,b which are all both strong (Hell and Ne Λ set Λ ril 2004, Proposition 4.16) and rigid (Hell and Ne Λ set Λ ril 2004, Proposition 4.6) (and contain edges non- incident to a,b). The claim then follows from taking any such G k ,a,b as J,s,t and applying (Hell and Ne Λ set Λ ril 2004, Proposition 4.12), whose statement reads: For every rigid strong replacement graph J,s,t and every pair H,H β² of di- graphs, we have that every homomorphism H β J hom ββ H β² β J is equal to f β J for some homomorphism f : H hom ββ H β² . β’ Consider the graphs G β J, G β² β J given by the claim above, and letΛu β² , Λv β² be an edge of the J u β² 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 MinHom d problem if, and only if, G β J,G β² β J,Λu β² , Λv β² is a positive instance of the MinHom u problem. J s t J s t J s t J s t J s t J s t J s t f f βJ βJ uvu β² v β² uv u β² v β² G G β² GβJ G β² βJ Λu Λv Λv β² Λu β² 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 ho- momorphism h : G hom ββ G β² . In particular, h(u,v) = (u β² ,v β² ) for some (u,v)β E(G) β cf. Figure 6 for visual aid. The graph homomorphism h β J : G β J hom ββ G β² β J must con- tain Λu β² , Λv β² by definition, since its image onto J uv is pre- cisely the copy J u β² v β² whereΛu β² , Λ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 g : G β J hom ββ G β² β J such that g(G β J)β h β J (G β J). By Claim D.3 this means that g = f β J for some f : G hom ββ G β² . By definition of f β J this would imply that f (G)β h(G) contradicting the minimality of h(G). From right to left, we have that (Λu β² , Λv β² ) belongs to a min- imal G β J-homomorphic image h(G β J) via the graph homomorphism h : G β J hom ββ G β² β J. In particular, h(Λu, Λv) = Λu β² , Λv β² for some Λu, Λv β E(G β J) β cf. Figure 6 for visual aid. By Claim D.3, h = f β J for some f : G hom ββ G β² . Let us show that f (G) is a minimal G-homomorphic image containing (u β² ,v β² ). By definition of f β J , Λu, Λv is the edge of some copy J uv (for some (u,v) β E(G)) corresponding to Λu β² , Λv β² in J u β² v β² . Hence, h(u,v) = (u β² ,v β² ) and thus (u β² ,v β² ) β f (G). If f (G) is not minimal, meaning that there is some g : G hom ββ 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.