The Parameterized Complexity of Finding Concise Local Explanations

1 Introduction

Explainable AI aims to help humans understand the complex decisions made by the opaque inner workings of machine learning (ML) models. Ideally, one tries to explain the entire ML model (global explanation) or replace an opaque model with an interpretable one [Angelino et al., 2017; Hu et al., 2019; Rudin, 2019; Ignatiev et al., 2021]. However, this approach has limits, as many applications require using non-interpretable models such as Neural Networks. In such cases, one can fall back to a local model-agnostic approach, which generates post-hoc explanations of individual decisions made by the opaque model (local explanation), treating the model as a black box [Ribeiro et al., 2016; Lundberg and Lee, 2017; Shrikumar et al., 2017; Shrotri et al., 2022].

A central concept for local model-agnostic explanations is the notion of an anchor [Ribeiro et al., 2018]. An anchor provides a local explanation in terms of a subset of features that "anchors" the prediction or classification of a given data point (or example) locally. That means changes to the rest of the feature values of the example do not matter. Thus, an anchor determines a small set of features sufficient to anchor the prediction. Practical heuristics for computing anchors have been successfully applied in many scenarios and come with the advantage of offering human-understandable explanations. For this reason, one prefers anchors that are small, providing concise explanations, while still applying to a large region.

For instance, assume a loan application has been declined, and we want to compute an anchor that could consist of two features, say, the applicant's income and age. Ideally, there should be no other applicants with the same income and age whose application has been accepted. The anchor's robustness can be measured in terms of the anchor's coverage (previous applicants with the same income and age whose application has been rejected), either in absolute numbers or as the fraction between the size of the coverage and the total number of applications.

In this paper, we provide the first study of the computation complexity of computing small anchors. We show that the exact computation of small anchors is NP-hard. Based on this insight, we roll out a systematic investigation of the parameterized complexity of this problem by taking various properties of the sought-for anchor or structural properties of the input data in terms of problem parameters into account. Our results draw a detailed complexity-landscape of the problem (see Figure 1), indicating regions where the problem is

1. fixed-parameter tractable (i.e., solvable in uniform polynomial time for fixed parameter values),
2. XP-tractable (i.e., solvable in nonuniform-polynomial time for fixed parameter values), and
3. paraNP-hard (remains NP-hard even for fixed parameter values).

Parameterized complexity considers problems in a twodimensional setting, where a problem instance is a pair (I, k), where I is the main part and k is the parameter. A parameterized problem is fixed-parameter tractable if there exists a computable function f such that instances (I, k) can be solved in time f(k)∥I∥O(1) ; one can show that a problem is unlikely to be fixed-parameter tractable by showing it to be hard for the complexity classes W[1] or W[2]. The problem is XP-tractable if it can be solved in time ∥I∥f(k) . Finally, a parameterized problem is paraNP-hard if the problem is NP-hard if the parameter is replaced by some constant. paraNP-hard problems are not XP-tractable unless P = NP. For a more in-depth treatment of parameterized complexity we refer to other sources [Cygan et al., 2015; Downey and Fellows, 2013].

Our results extend a recent line of research that investigates explainability and interpretability of ML models from a (parameterized) complexity theoretic perspective [Barcel´o et al., 2020; Ganian et al., 2018; Kobourov et al., 2022; Ordyniak and Szeider, 2021; Simonov et al., 2019].

2 ProblemDefinition

A classified data set (CDS) is a triple (E, F,m) where E is a multi-set of examples over the set F of features and m is a mapping, called classification, that assigns each example e ∈ E a non-negative integer m(e). Here, an example is a mapping e : F → Z. We think of m as being computed by a black-box model that has been trained earlier from a separate set of examples and whose classifications we want to explain. We say that two examples e1, e2 agree on a feature f ∈ F

if e1(f) = e2(f); otherwise they disagree on f.

Given a CDS (E, F,m), an anchor for an example x ∈ E is a set A ⊆ F of features such that all e ∈ E with m(x) ̸= m(e) disagree with x on some feature in A. The coverage of A is the number of all examples e ∈ E \ {x} with m(e) = m(x) that agree with x on all features in A. We can now formulate our central computational problem:

MINIMUM ANCHOR (MA)

Input: A CDS (E, F,m), an example x ∈ E, and two integers k, c.

Question: Is there an anchor A for x of size at most k and coverage at least c?

For an instance I = ((E, F,m), x, k, c) of MA, we denote by pE and nE the subsets of E containing all examples e ∈ E such that m(e) = m(x) and m(e) ̸= m(x), respectively. We will refer to the examples in pE and nE as positive and negative examples, respectively. Instead of the size c of the coverage we might want to achieve a coverage that includes a certain fraction q of the examples in E; in this case, we can put c = q · |pE|. Interestingly, since our results show that the parameter c is not necessary for any of our tractability results as can seen from Figure 1, i.e., for all considered parameterization the complexity remains the same after adding c as an additional parameter, it follows that all our results still hold when we require the coverage to have a certain fraction q instead of a size c.

Let I = ((E, F,m), x, k, c) be an instance of MA. In the following we will show that we can normalize I into an equivalent instance of MA that has only two classes and where the domain of every feature is Boolean. We denote by N(I) = ((E′ , F,m′ ), x′ , k, c) the normalized instance of I that is defined as follows. E′ is the set {e′ | e ∈ E} such that, for every f ∈ F, e′ (f) = 0 if e(f) = x(f) and e′ (f) = 1 otherwise. Moreover, m′ (e′ ) = 0 if m(e) ̸= m(x) and m′ (e′ ) = 1 otherwise. Note that x′ now satisfies that m(x′ ) = 1 and x(f) = 0 for every f ∈ F. We say that I is normalized if I = N(I). Thus, all the features of a normalized instance are Boolean, i.e., range over the domain {0, 1} and m is Boolean as well, i.e., m(e) ∈ {0, 1} for all e ∈ E. The following lemma shows that I and N(I) are equivalent instances of MA.

Lemma 1. An instance I = ((E, F,m), x, k, c) of MA has a solution if and only if so does the instance N(I).

We will consider several parameters that restrict the graphical structure of the MA instance I by means of its incidence graph GI (I). This is the bipartite graph with vertex-partition (E, F ) having an edge between an example e ∈ E and a feature f ∈ F iff e(f) ̸= x(f), i.e., the edge indicates that the example e disagrees with x on feature f .

Finally, we would like to note that MA is computational equivalent to the following interesting and natural generalization of the well-known DOMINATING SET problem.

MA DOMINATING SET

Input: A graph G = (V,E), where V is partitioned into B, P , and N, and two integers k and c.

Question: Is there a set D ⊆ B with |D| ≤ k that dominates N, i.e., N ⊆ NG(D), and leaves at least c vertices in P not dominated, i.e., |P \ NG(D)| ≥ c? Here, NG(D) denotes the set of all neighbors of any vertex in D.

The equivalence between the two problems follows because there is a one-to-one correspondence between the incidence graph of an MA instance and an instance of MA DOMINATING SET; after setting B to the set of features, P to the positive examples, and N to the set of negative examples.

3 Structural Parameters

Besides the anchor size k and the coverage size c, we consider structural parameters that depend on the given instance I = ((E, F, m), x, k, c) of MA.

We first consider maximum difference, which has been used in a related context by Ordyniak and Szeider [2021]. The maximum difference δmax(X) of a CDS X = (E, F, m) is the largest number of features on which any two examples e, e′ ∈ E disagree on. This parameters is attractive as it has been observed that for real-world instances, the maximum difference tends to be surprisingly small [Ordyniak and Szeider, 2021]. In our setting, we define the maximum difference δmax(I) of an MA instance I = ((E, F,m), x, k, c) as the largest number of features any example e ∈ E \ {x} with m(e) ̸= m(x) differs from x. Consequently δmax(I) ≤ δmax(X), thus it is likely that the parameter is even smaller than the one considered by Ordyniak and Szeider.

The following observation (whose proof follows along the same lines as the proof of Lemma 1) shows that neither the parameter δmax(I) nor the incidence graph of I change after normalization. This will later allow us to work solely on the simpler normalized instances.

Observation 2. Let I = ((E, F,m), x, k, c) be an instance of MA. Then, GI(I) = GI(N(I)) and δmax(I) = δmax(N(I)).

There is a plethora of width parameters for graphs that we can utilize for MA by means of the incidence graph. We cover this field of width parameters by considering three of the most fundamental ones. For comparing the generality of width parameters p and q, the following notion is useful. We say that p dominates q if, for every class of instances for which q is bounded, p is also bounded; p strictly dominates q if p dominates q, but q does not dominate p. If p and q dominate each other, they are domination-equivalent.

treewidth (tw) is perhaps the most famous width parameter which measures how "tree-like" a graph is. Graphs of bounded treewidth are sparse [Bodlaender, 2007].

rank-width (rw) strictly dominates treewidth, as also dense graphs (even cliques) can have small rank-width, but any class of graphs of bounded treewidth has also bounded rank-width [Oum and Seymour, 2006].

twin-width (tww) has been recently introduced [Bonnet et al., 2022b]. It strictly dominates rank-width, as any class of graphs of bounded rank-width has also bounded twinwidth, but the reverse isn't true. For instance, planar graphs have bounded twin-width but can have arbitrarily high rank-width 1 .

Thus, for an instance I = ((E, F,m), x, k, c) of MA we simply write tw(I) = tw(GI(I)), rw(I) = rw(GI(I)), and tww(I) = tww(GI (I)).

The following is now a direct consequence of Observation 2 and implies that none of our parameters changes after normalization.

Corollary 3. Let I = ((E, F,m), x, k, c) be an instance of MA. Then, δmax(I) = δmax(N(I)), tw(I) = tw(N(I)), rw(I) = rw(N(I)), and tww(I) = tww(N(I)).

1 Bonnet et al. [2022b; 2021a; 2021b] list more than a dozen of diverse fundamental graph classes which have bounded twinwidth, and for all of them corresponding decompositions can be fptapproximated.

Therefore, in the following (and throughout the rest of the paper), we can assume that any instance I = ((E, F, m), x, k, c) of MA is normalized.

By the notion of renaming, borrowed from a similar notion for propositional CNF formulas [Lewis, 1978], we can further strengthen width parameters for MA instances. A renaming IR of a normalized MA instance I = ((E, F,m), x, k, c) with respect to a subset R ⊆ F is the MA instance IR = ((ER, F,mR), xR, k, c) where ER = {eR | e ∈ E } with eR(f) = 1 - e(f) if f ∈ R and eR(f) = e(f) if f /∈ R; mR(eR) = m(e). For each of the above width measures w ∈ {tw, rw, tww}, we define a renaming variant w∗ where w∗ (X) = minR⊆F w(XR).

tw∗ strictly dominates tw (domination follows by definition, to see that the domination is strict, construct a normalized MA instance I = ((E, F,m), x, k, c), |E| = |F| = n where e(f) = 1 ̸= x(f) = 0 for all e ∈ E \ {x} and f ∈ F ; the incidence graph of I is a complete bipartite graph and thus tw(I) = n; however the incidence graph of IF is edge-less and thus tw∗ (I) = 0). rw and tww, however, are dominationequivalent with their renaming variants, since these two parameters are known to be closed under local complementation [Oum, 2005; Bonnet et al., 2023]. We therefore have the relationship in terms of domination as indicated in Figure 2.

4 Hardness Results

Here, we show our hardness results for the MA problem. We start by giving a simple polynomial-time reduction from the well-known HITTING SET (HS) problem to the MA problem. In the HS problem one is given a family S of sets over some universe U and an integer h and one asks whether S has a hitting set of size at most h, i.e., a set H ⊆ U (with |H| ≤ h) such that H ∩ S ̸= ∅ for every S ∈ S. For a given instance I = (S, U, h) of HS, we construct the instance ((E, F,m), x, k, c) of MA, denoted by LA(I), as follows. We set c = 0, k = h, F = U and for every set S ∈ S, E contains the example eS with m(eS) = 0 such that eS(f) = 1 if f ∈ S and eS(f) = 0 otherwise for every f ∈ F. Finally, let x be the example with x(f) = 0 for every f ∈ F and m(x) = 1; note that x is also part of E. Clearly, LA(I) can be computed in polynomial-time. The following lemma shows that LA(I) is indeed a reduction from HS to MA.

Lemma 4. An instance I = (S,U, h) of HS has a solution if and only if the instance LA(I) of MA does.

Proof. Towards showing the forward direction, let H ⊆ U be a hitting set of size at most h for I. Then, H is an anchor for x, because for every example eS for some S ∈ S, it holds that H ∩ S ̸= ∅ and moreover eS disagrees with x on all features in H ∩ S. Because |H| ≤ h = k and c = 0, we obtain that H is a solution for LA(I).

Towards showing the reverse direction, let A be an anchor of x of size at most k. Then, A is a hitting set for I, because for every set S ∈ S, the example eS disagrees with x on some feature f ∈ A, which implies that f ∈ S and therefore A ∩ S ̸= ∅. Because |A| ≤ k = h, it follows that A is a solution for I.

Because HS is W[2]-hard parameterized by solution size h and because the reduction LA(I) maps the parameter h to k, we obtain.

Corollary 5. MA is W[2]-hard parameterized by k even if c = 0.

We will show one more related hardness result for MA in Section 7, i.e., we will show that MA is NP-hard even if δmax ≤ 2, c = 0, and the incidence graph has bounded twin-width.

5 Algorithms Using δmax and k

In this section we show that MA is in XP parameterized by k alone and fpt parameterized by δmax + k. The former algorithm is a simple brute-force algorithm that uses the fact that we can enumerate all potential anchors A in time O(|F|k ) and that we can then check whether A is indeed an anchor having the required coverage in time O(|E||A|) = O(|E|k). This gives us the following theorem.

Theorem 6. MA can be solved in time O(|F|k |E|k) and is therefore in XP parameterized by k.

The remainder of this section is devoted to a proof of the following theorem, which shows that MA can be solved efficiently for instances with small δmax + k.

Theorem 7. MA can be solved in time O(δkmax |I||E|k) and is therefore fpt parameterized by δmax + k.

The main idea behind the algorithm is to show that we can efficiently enumerate all (minimal) anchors of size at most k. Towards showing this, we use a simple reduction to the HS problem and the following well-known result.

Proposition 8 (Downey and Fellows 2013). Let I = (S, U, h) be an instance of HS with all sets in S having size at most γ. Then, there is an algorithm that enumerates all minimal hitting sets of size at most h for I in time O(γ h |I|).

Consider an instance I = ((E, F,m), x, k, c) of MA. Then, a set A of features is an anchor of x if and only if for every example e ∈ nE, A contains a feature f with e(f) ̸= x(f). In other words, for every example e ∈ nE, an anchor A has to contain (hit) at least one feature from the set X(e) = {f | e(f) ̸= x(f) }. Therefore, A is an anchor for x if and only if A is a hitting set of (S(nE), F) with S(nE) = {X(e) | e ∈ nE }. Because the cardinality of every set in S(nE) is at most δmax, we obtain from Proposition 8 that:

Lemma 9. Let I = ((E, F,m), x, k, c) be an instance of MA. Then, there is an algorithm that enumerates all minimal anchors of size at most k for I in time O(δkmax |I|).

We are now ready to prove Theorem 7.

Proof of Theorem 7. Given an instance I = ((E, F,m), x, k, c) of MA, we use Lemma 9 to enumerate all minimal anchors of I in time O(δkmax |I|). Then, for every such anchor A, we count the number n(e) of examples e ∈ pE that agree with x on all features in A in time O(|E|k). If n(e) ≥ c for one of those anchors, we return yes. Otherwise, we continue with the next anchor. Finally, if none of the anchors covers at least c examples, we return no. The total run-time of the algorithm is therefore O(δkmax |I||E|k) as stated.

6 An Algorithm for Rank-width

In this section, we provide an fpt-algorithm for MA parameterized by the rank-width of the incidence graph of the input instance. Indeed, we will show something slightly stronger, namely, that given an instance I = ((E, F,m), x, k, c) of MA we can find an anchor for x of minimum size that has coverage at least c or output correctly that no such anchor exists. Throughout this section, we will assume that I is normalized, which we are allowed to do due to Lemma 1 and Corollary 3. The following is the main result of this section.

Theorem 10. MA is fixed-parameter tractable parameterized by the rank-width of GI(I).

The remainder of this section is devoted to a proof of Theorem 10. At a first glance one might be tempted to think that Theorem 10 can be obtained by a simple application of Courcelle's theorem or more specifically by the known extensions of Courcelle's theorem for optimization problems [Arnborg et al., 1991]. Unfortunately, on a second glance, this does not seem to be the case because the MA problem has two orthogonal optimization criteria, i.e., we want to minimize the size of the anchor while at the same time maximizing the coverage of the anchor. We therefore have to resort to provide a dedicated algorithm that is based on a dynamic programming algorithm. along a given rank decomposition; indeed for simplicity we will provide the algorithm on a NLCdecomposition, which is known to be asymptotically equivalent to rank-width [Wanke, 1994]. Before we start with an informal description of the algorithm in Subsection 6.3, let us first fix the main notation required to describe the algorithm.

6.1 Graphs and NLC-width

We will assume that the reader is familiar with basic graph theory (see e.g., [Bang-Jensen and Gutin, 2009; Diestel, 2017]). We consider (vertex and edge labelled) undirected graphs. Let G = (V,E) be a graph. We write V (G) = V and E(G) = E for the sets of vertices and edges of G, respectively. We denote an edge between u ∈ V and v ∈ V by {u, v}. For a set V ′ ⊆ V of vertices, we let G[V ′ ] denote the graph induced by the vertices in V ′ , i.e. G[V ′ ] has vertex set V ′ and edge set E ∩ { {u, v} | u, v ∈ V ′ } and we let G-V ′ denote the graph G[V \ V ′ ]. For a set E′ ⊆ E of edges we let G- E′ denote the graph with vertex set V and edge set E \ E′ .

A ω-graph is a pair (G, λ), where G = (V,E) is a graph and λ : V → [ω] is a vertex label mapping that labels every vertex v ∈ V with a label λ(v) from [ω] = {1, . . . , ω}. An initial ω-graph is a ω-graph consisting of exactly one vertex v (say, with label i) which is denoted by i(v).

Node label control-width (NLC-width) is a graph parameter defined as follows [Wanke, 1994]: let ω ∈ N be a positive integer. A ω-NLC-expression tree of a graph G = (V, E) is a subcubic tree B, where every node b of B is associated with a ω-graph (denoted by (Gb, λb)), such that:

1. Every leaf represents an initial ω-graph i(v) with i ∈ [ω] and v ∈ V .
2. Every non-leaf node b with one child c is a relabelling node and has an associated relabelling function γb : [ω] → [ω]. Moreover, (Gb, λb) is obtained from (Gc, λc) by relabelling all vertices of Gc with label i to label γb(i) for every i ∈ [ω].
3. Every non-leaf node b with two children, i.e. a left child l and a right child r, is a join node and has an associated join matrix, i.e. a binary ω × ω matrix Mb. Moreover, (Gb, λb) is obtained from the disjoint union of (Gl, λl) and (Gr, λr) by adding an edge from all vertices labeled i in Gl to all vertices labelled j in Gr whenever Mb[i, j] = 1.
4. G is equal to the Gr for the root node r of B.

The NLC-width of a graph G, denoted by nlcw(G), is the minimum ω for which G has a ω-NLC-expression tree. A ωNLC-expression tree is nice if every relabelling node b has a relabelling function γb : [ω] → [ω] such that for some i, j ∈ [ω], γb(i) = j and γb(c) = c for all c ∈ [ω] \ {i}. Let b be a node in a ω-NLC-expression tree of a graph G. We let Vb denote the set of vertices of Gb. By the definition of a ω-NLC-expression tree, if u, v ∈ Vb have the same label in (Gb, λb) and w ∈ V (G) \ Vb, then u is adjacent to w in G if and only if v is. Computing the NLC-width of a graph is NP-hard [Gurski and Wanke, 2005], however, we have the following.

Proposition 11. Let G be a graph and ω be an integer. There is an fpt-algorithm (w.r.t. ω) which either correctly concludes that G has NLC-width larger than ω or outputs a nice 2ω - NLC-expression tree for G with O(2ω n) nodes.

6.2 Main Notation

To simplify the description of the proof, we will show the result for NLC-width, which is known to be asymptotically equivalent to rank-width [Wanke, 1994]. Because of Proposition 11, it suffices to show the result for the case when we are provided with a nice ω-NLC-expression tree.

Lemma 12. Let I = ((E, F,m), x, k, c) be an instance of MA and let B be a nice ω-NLC-expression tree for GI(I). Then, finding an anchor of smallest size, whose coverage is at least c or deciding correctly that no such anchor exists, is fixed-parameter tractable parameterized by ω.

The remainder of this section is devoted to a proof of Lemma 12, which implies Theorem 10. Let I = ((E, F,m), x, k, c) be a normalized instance of MA. Let G be the graph GI(I) after removing the isolated example x. Recall that we denote by pE and nE the subsets of E containing all examples e ∈ E such that m(e) = m(x) and m(e) ̸= m(x), respectively, and that we refer to the examples in pE and nE as positive and negative examples, respectively.

Let B be a ω-NLC-expression tree for G and let b be a node of B. Recall that (Gb, λb) is the ω-graph associated with node b and that Vb is the set of vertices of Gb. We denote by Ib the MA instance associated with b, i.e., Ib contains all features and examples in Vb and the feature values of the examples in Ib are given by the edge relation of Gb, i.e., e(f) = 1 if Gb has an edge between e and f and otherwise e(f) = 0. We denote by λ-1 b (c) the set of features and examples v in Vb with λb(v) = c for every c ∈ [ω]. For convenience, we denote by feat(b) and exam(b) the set of features and examples in Vb respectively, i.e., feat(b) = F ∩ Vb and exam(b) = E ∩ Vb. Moreover, we denote by pexam(b) and nexam(b) the set of all positive and negative examples in exam(b), respectively, i.e., pexam(b) = exam(b) ∩ pE and nexam(b) = exam(b) ∩ nE. With a slight abuse of notation, we will in the following assume that the feature values for any example in exam(b) are defined with respect to the instance Ib; if not explicitly stated otherwise.

6.3 Overview and Informal Description of the Algorithm

As is usual for algorithms exploiting NLC-width, the algorithm uses a dynamic programming approach to compute a set of valid records for every node b of the decomposition B in a leaf-to-root manner. The crucial part of the algorithm is the correct definition of the records. Informally, a (valid) record for a node b of B represents a compact representation of an equivalence class of solutions (anchors) for the whole instance from the perspective of the subinstance Ib. For the purpose of the DP algorithm, it is best to think of a solution for I = ((E, F,m), x, k, c) in terms of a pair (A, P), where A ⊆ F with |A| ≤ k is an anchor for x and P ⊆ pexam with |P| = c is a set of positive examples that are not distinguished from x by any feature in A and that witnesses that A has coverage at least c. Then, the first question is what information do we need to store for such a solution (A, P), when viewed from the perspective of the subinstance Ib? Consider the part (Ab, Pb) of the solution (A, P) that lives inside Ib, i.e., Ab = A∩feat(b) and Pb = P ∩pexam(b). Then, (Ab, Pb) is not necessarily a solution for the subinstance Ib, because Ab is not necessarily an anchor for x in Ib; this is because there can be negative examples e ∈ nexam(b) that are not yet distinguished from x by Ab (but are only latter distinguished from x using some feature in A \ Ab). To take this into account, one also needs to consider the set Nb ⊆ nexam(b) of negative examples in Ib that are not yet distinguished from x by Ab in Ib. Therefore, the triple (Ab, Pb,Nb) now provides a complete representation of the solution (A, P) from the perspective of Ib and we will therefore refer to it as a partial solution. Unfortunately, it is not possible to store every such triple for b, because the number of those triples is too large (the size is at least Ω(|Ib|k+c )). However, because of the properties of an NLC-decomposition and in particular the fact that every feature (or example) of Ib with the same label will behave the same w.r.t. every example (or feature) that is not yet in Ib, it is not necessary to remember the exact sets of features and examples. In particular, instead of storing the partial solution (Ab, Pb,Nb), it is sufficient to store the tuple (C, C-, C+, p, s), where:

• C ⊆ [ω] is the set of all labels in Gb that contain a feature in Ab,
• C- ⊆ [ω] is the set of all labels in Gb that contain a negative example in Nb,
• C+ ⊆ [ω] is the set of all labels in Gb that contain a positive example in Pb,
• p and s are integers with p = |Pb| and s = |Ab|.

We will later refer to the tuple (C,C-,C+, p, s) as a record and we will refer to a partial solution (Ab, Pb, Nb) that is represented by the record as a witness. Clearly, we are only interested in records that represent some partial solution and we will refer to such records as semi-valid. Note that a record can be seen as a compact representation of an equivalence class of partial solutions since many partial solutions can result in the same record. However, since all partial solutions that result in the same record behave in the same manner due to the properties of an NLC-decomposition it is sufficient to represent all those partial solutions by a record. More importantly, if we have two semi-valid records that only differ in the size s of the (partial) anchor, then it is sufficient to remember only the tuple with the smaller (partial) anchor. This now provides us with the notion of a valid record, i.e., a record (C, C-, C+, p, s) is valid for a node b if s is equal to the minimum number s′ such that (C, C-, C+, p, s′ ) is semi-valid.

6.4 Formal Definition of Records and Preliminary Results

We are now ready to define the records and their semantics. A record for b is a tuple (C, C-, C+, p, s) where C, C- and C+

are set of labels (subsets of [ω]) and p and s are integers with p ≤ c. We say that a record (C,C-,C+, p, s) is semi-valid for b if there is a set of features A ⊆ feat(b) of size s and a set of positive examples P ⊆ pexam(b) of size p such that:

• (a) C is the set of all labels c ∈ [ω] such that λ-1 b (c) ∩A ̸= ∅.
• (b) C- is the set of all labels c ∈ [ω] such that λ-1 b (c)∩N ̸= ∅. Here, and in the following, N is the set of all negative examples in nexam(b) that are not yet distinguished from x by a feature in A w.r.t. Ib, i.e., N = {e ∈ nexam(b) | e(f) = x(f) for every feature f ∈ A}; recall the the feature values of e are defined with respect to Ib.
• (c) C+ is the set of all labels c ∈ [ω] such that λ-1 b (c)∩P ̸= ∅.
• (d) the examples in P agree with x on all features in Awith respect to Ib.

Let R = (C, C-, C+, p, s) be a semi-valid record for node b. A witness for R is a pair (A, P), where A ⊆ feat(b) is a set of features of size s and P ⊆ pexam(b) is a set of positive examples of size p that satisfy all the conditions (a)-(d).

We say that a record (C, C-, C+, p, s) is valid if s is equal to the minimum number s′ such that (C,C-,C+, p, s′ ) is semi-valid. We denote by R(b) the set of all valid records for the node b. The following corollary follows immediately from the definition of valid records and gives an upper bound on the size of R(b).

Observation 13. |R(b)| ≤ 23ω c.

6.5 Putting It All Together

We will now show that we can compute R(b) for each of the three node types of a nice ω-NLC expression tree provided that R(c) has already been computed for every child c of b. Recall that b is either a leaf node associated with a ω-graph i(v), a relabelling node with one child and with relabelling function γb, or a join node with a left child, a right child and a join matrix Mb. Moreover, recall that (Gb, λb) is the ω-graph associated with b (whose unlabelled version is a subgraph of G) and Vb is the set of vertices of Gb.

Lemma 14 (leaf node). Let b ∈ V (B) be a leaf node. Then R(b) can be computed in O(1) time.

Proof. Let i(v) be the initial ω-graph associated with b. We distinguish the following cases. If v is a feature, then R(b) contains the following two records: The record (∅, ∅, ∅, 0, 0) which is witnessed by the set A = ∅ of features and the set P = ∅ of positive examples and the record ({i}, ∅, ∅, 0, 1), which is witnessed by the sets A = {v} and P = ∅.

If v is a negative example, then R(b) contains the record (∅, {i}, ∅, 0, 0), which is witnessed by the sets A = ∅ and P = ∅.

If v is a positive example, then R(b) contains the two records (∅, ∅, {i}, 1, 0), which is witnessed by the sets A = ∅ and P = {v}, and (∅, ∅, ∅, 0, 0), which is witnessed by the sets A = ∅ and P = ∅.

Clearly, R(b) can be computed in constant time. Moreover, the correctness of the definition of R(b) follows directly from the definition and the given witnesses.

Lemma 15 (join node). Let b ∈ V (B) be a join node. Then R(b) can be computed in O((23ω c)2 ) time.

Proof Sketch. Let bl and br be the left and right child of b in B, respectively. Let Mb be the join matrix for the node b, i.e. Mb is a ω × ω binary matrix.

Let Rl = (C l ,C l-,C l+, pl , sl ) ∈ R(bl ) and Rr = (C r ,C r-,C r+, pr , sr ) ∈ R(br ) be two records. Let Ql be the set of all labels c ∈ [ω] such that there is a label c′ ∈ C r with Mb[c, c′ ] = 1, i.e., informally Ql is the set of all labels occurring in Gbl that are connected to at least one label in C r . Note that if e is an example in Ibl whose label is in Ql , then e is distinguished from x in the instance Ib by any feature with label c′ ∈ C r . We say that Rl is compatible with Rr if they satisfy:

Intuitively, Rl and Rr are compatible if all positive examples in C l+ and C r+ are not distinguished from x in the instance Ib; assuming that those examples were not distinguished from x already in the instance Ibl and Ibr , respectively.

We are now ready to define R(b). A record R = (C,C-,C+, p, s) is valid for b, that is, belongs to R(b) if and only if there is a pair of compatible records Rl = (C l ,C l-,C l+, pl , sl ) ∈ R(bl ) and Rr = (C r , C r-, C r+, pr , sr ) ∈ R(br ) such that:

• (i) C = C l ∪C r ;
• (ii) C- = (C l- \ Ql ) ∪ (C r- \ Qr );
• (iii) C+ = C l+ ∪C r+;
• (iv) p = pl +pr and s = sl + sr .

We now show how and in what time R(b) can be computed. We compute R(b) as follows. First we compute Ql and Qr in time O(ω2 ). Then, for every pair of records Rl ∈ R(bl ) and Rr ∈ R(br ), we do the following. First we check whether both records are compatible in time O(ω). If not, we continue with the next pair. Otherwise, we compute R from Rl and Rr in time O(ω + log c + log k) and add it to R(b). Therefore, the total run-time for computing R(b) is at most O(ω2 + |R(bl )||R(br )|(ω + log c + log k)), which because of Observation 13 is at most O((23ω c)2 ). The correctness-proof of the definition of R(b) can be found in the supplementary material.

Lemma 16 (relabel node). Let b ∈ V (B) be relabelling node in B. Then R(b) can be computed in O(23ω cω) time.

We are now ready to prove the main result of this section.

Proof of Lemma 12. Given I = ((E, F,m), x, k, c) and B, we use Lemmas 14, 15 and 16 to compute the set R(b) of valid records for every node b of B in a leaf-to-root manner. We then go through all records in R(r) for the root r of B to find a record R such that s is minimum among all records of the form (C, ∅,C+, c, s). If no such record R exists or the size s for R is larger than k, we correctly output no. Otherwise, we use standard dynamic programming methods to obtain a witness (A, P) for R and output A. The correctness of the algorithm follows directly from the definition of the valid records together with Lemmas 14, 15 and 16. Moreover, we obtain the run-time of the algorithm as follows. The maximum time spent on any of the nodes b (which is achieved for a join-node) is O((23ω c)2 ). Because B has at most O(ω|E ∪ F |) (see Proposition 11) nodes, we obtain O((23ω c)2ω|E ∪ F|) as the total run-time of the algorithm, which shows that MA is fixed-parameter tractable parameterized by the NLC-width of GI (I).

7 Twin-Width

In this section, we provide our complexity results for twinwidth. In particular, we show that the fpt-result of the previous section for rank-width cannot be extended to the more general (less restrictive) parameter twin-width; indeed we show that MA is paraNP-hard parameterized by twinwidth alone. However, we also show that MA becomes fixed-parameter tractable parameterized by twin-width plus k (given that a witness for small twin-width is provided), which given the generality of twin-width is an encouraging result. We start with our hardness result.

Theorem 17. MA is paraNP-hard parameterized by the twin-width of its incidence graph even if c = 0 and δmax(I) = 2.

We are now ready to show that MA is fixed-parameter tractable parameterized by twin-width plus k. While it is relatively straightforward to show that MA is fixed-parameter tractable when additionally parameterized by c (this follows immediately from the recently shown first order logic metatheorem for twin-width [Bonnet et al., 2022b]), this is no longer the case if one merely parametrizes by tww+ k. We therefore developed a tailor-made dynamic programming algorithm, which we believe to be interesting in its own right; an alternative proof can be obtained using a very recently established meta-theorem [Bergougnoux et al., 2023].

Theorem 18. MA is fpt parameterized by the twin-width of GI(I) plus k provided that one is given an optimal contraction sequence of the incidence graph.

8 Conclusion

We have provided the first complexity analysis of finding concise local explanations (MA), a central computational problem in explainable AI. Starting from an NP-hardness result of the problem in general, we have studied it in a parameterized complexity setting with several natural parameters. Our results drawn a comprehensive complexity landscape for all combinations of the considered parameters. Particularly interesting is our finding that adding the coverage size c to any of the considered parameterizations does not change the complexity of the MA problem. On a more technical level and of independent interest is that our fpt-results for rank-width and twin-width can both not be obtained via the corresponding meta-theorems but require a tailor-suited dynamic programming approach. We hope that our study stimulates further research on the computational complexity of problems arising in explainable AI.

Acknowledgements

Stefan Szeider acknowledges support by the Austrian Science Fund (FWF, project P32441) and the Vienna Science and Technology Fund (WWTF, project ICT19-065). Giacomo Paesani and Sebastian Ordyniak acknowledge support from the Engineering and Physical Sciences Research Council (EPSRC, project EP/V00252X/1).