Target Set Selection Parameterized by Clique-Width and Maximum Threshold

Abstract

The Target Set Selection problem takes as an input a graph G and a non-negative integer threshold $\mathsf {thr}(v)$ for every vertex v. A vertex v can get active as soon as at least $\mathsf {thr}(v)$ of its neighbors have been activated. The objective is to select a smallest possible initial set of vertices, the target set, whose activation eventually leads to the activation of all vertices in the graph.

We show that Target Set Selection is in FPT when parameterized with the combined parameters clique-width of the graph and the maximum threshold value. This generalizes all previous FPT-membership results for the parameterization by maximum threshold, and thereby solves an open question from the literature. We stress that the time complexity of our algorithm is surprisingly well-behaved and grows only single-exponentially in the parameters.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

The Target Set Selection problem (TSS) suits to model irreversible propagation of all sorts of conditions or information in a network. This may be for example a word-of-mouth-effect, disease spreading or fault influence in distributed systems [15]. The input is an undirected graph $G$ and a non-negative integer threshold $\mathsf {thr}(v)$ for every vertex $v$. The task is to select a smallest possible set $S$ of initially active vertices, the target set, whose activation eventually leads to the activation of all vertices in the graph. A vertex v can become active as soon as at least $\mathsf {thr}(v)$ of its neighbors have been activated.

Our view on the activation of a vertex is that it is allowed to become active if enough neighbors are active before, in contrast to that it is obligated to get active as soon as possible. We ask for a smallest possible set $S$, the target set, and a permutation of the vertices ${\pi }$, which is the ordering in which the vertices get active. Then, for every non-target set vertex $v$, to assure its activation we require that at least threshold $\mathsf {thr}(v)$ many neighbors of $v$ are ordered before $v$. In particular, our permutation may order the target set vertices $S$ not at the beginning. This definition is more robust towards re-orderings of the permutation of vertices. We can re-order the permutation and not have to bother that for example the target set no longer consists of the very first vertices of the ordering. In the literature the problem is commonly defined via rounds of activations that define sets of active vertices for each round. Our definition is equivalent while being much more convenient for our techniques.

The problem was first introduced by Kempe et al. [14]. It proves to be computationally extremely difficult. It is NP-hard even for the restriction to split-graphs of diameter two [15]. Chen showed that minimizing the size of the target set is APX-hard [4]. More recently, Bazgan et al. showed that for every functions $f$ and $\rho$ this problem cannot be approximated within a factor of $\rho (k)$ in $f(k) \cdot n^{\mathcal {O}(1)}$ time [1]. The parameterized complexity studies focus on the original problem and two variants that limit the allowed thresholds. These are constant thresholds, where all thresholds are at most a constant $t_{\max }$, and majority thresholds, where a vertex can get active as soon as at least the majority of its neighborhood is active before. The general TSS is -hard for each of the parameterization, “distance to cluster,” [5] “distance to forest” and pathwidth [15]. The strongest positive FPT-membership results for constant thresholds are the parameterization by treewidth [2], the parameterization by “distance to cluster” [5], and the parameterization by neighborhood diversity [11]. There are a lot more parameterized complexity results for these three variants of TSS [5, 15]. Further, Cicalese et al. study a variant of TSS which asks if a set of vertices $A$ can be activated in a given number of activation rounds [6]. They give a polynomial time algorithm when the number of activation rounds and the clique-width of the input graph are constant. Their exponential dependency on the clique-width is unlikely to be improved, as even TSS for one activation round is -hard with respect to the treewidth [3]. For a more extend introduction to the history of the problem as well as other algorithmic aspects and similar models see for example [5, 15].

Dvořák et al. raised the question of the complexity of the parameterization by the modular-width [11]. The structural graph parameter modular-width was introduced by Gajarský et al. [13]. We give a positive answer by showing FPT-membership for a more general question. We consider the clique-width which is upper bounded by the parameters modular-width and treewidth [7], and by further common structural parameters for which the parametrized complexity of TSS was open. Thereby, we generalize all positive FPT-memberships results for TSS with constant thresholds. Further, our result does not rely on the maximum threshold $t_{\max }$ being a constant, but allows that $t_{\max }$ is a parameter. Moreover, the time complexity of our algorithm behaves surprisingly well and grows only single-exponentially in the parameters clique-width and maximum threshold.

A related result is that TSS is in FPTwhen parameterized by treewidth and maximum threshold, by Ben-Zwi et al. [2]. They use a dynamic program that works along the bags of a computed tree decomposition. They fix the local ordering in which the vertices of the currently observed bag get active. Our approach also uses such an recursive approach, while working on a computed $\ell$-expression. Informally, an $\ell$-expression is a tree-decomposition in the context of clique-width. Such an $\ell$-expression $f$ uses three types of recursive operations that work on labeled vertices using at most $\ell$ different labels. Analogously to the approach for a tree decomposition, for every subexpression a current state fixes a part of the global ordering of the vertices.

However, the described vertices of a current subexpression is not bounded by our parameters. Our algorithm has to remember an ordering of a limited number of vertices and further has to address these vertices indirectly. Crucial for the activation of a vertex is its threshold and neighborhood. However, we cannot address the neighborhood even for vertices of currently equal label and threshold since they can have very different neighborhoods as subexpression may reveal. Consequently, our approach explores the $\ell$-expression top down, and fixes an ordering of the important vertices of the up to now described graph. The up to now encountered operations define a common neighborhood for all vertices of a fixed label. This is because for every outer operations, vertices of the same label behave equally. Thus, our local ordering indirectly references the vertices solely by their label and threshold.

Further, vertices of the same label that occur late enough in a global ordering behave equally. There is only one type of edge operation of $\ell$-expression, namely $\eta _{\alpha ,\beta }$ adding all edges between vertices of some labels $\alpha$ and $\beta$. There, for a vertex $v$ of label $\alpha$ we have to account the contribution to the activation of $v$ due to vertices of label $\beta$. Only the first $\mathsf {thr}(v) \le t_{\max }$ active vertices of label $\beta$ are important. If the activation of $v$ is between the activation of the first $t_{\max }$ of label $\beta$, we fix their relative positioning in our local ordering. Otherwise, the activation of $v$ does not differ from other late vertices of label $\alpha$.

However, we need to guarantee that a vertex $v$ of label $\alpha$ that is not referenced by our local ordering is indeed ordered late enough. That is, the first $t_{\max }$ vertices of label $\beta$ occur before vertex $v$. We denote such a global ordering as nice to the current subexpression $\eta _{\alpha ,\beta }f'$. It is possible to modify any valid global ordering to be nice to all subexpressions. We extend our local ordering to also include the $(t_{\max }+1)$-st vertex of every label. Then, whether the underlying global ordering ${\pi }$ is nice, is reflected in our local ordering. Therefore, we can restrict our algorithm to consider nice global orderings only.

The resulting procedure for our algorithm at each operation of the given $\ell$-expression then is as follows. For a current edge operation $\eta _{\alpha ,\beta }$, for each vertex $v$ we simply have to adjust the number of neighbors contributing to the activation of $v$ according to our fixed local ordering. We remember this contribution as the activation from outside. For a current operation that combines two subgraphs, consider the unknown partition of the vertices fixed by the local ordering in either subgraph. In that case, the algorithm tries all possibilities. The approach for the operation that re-labels a label is very similar. For every subexpression, the number of possible states is single-exponentially bounded by our parameters, which yields to an overall FPT-runtime.

Theorem 1

Let $t_{\max }, \ell \in \mathbb {N}$. There is an algorithm that, given a graph $G$, a threshold for each vertex $\mathsf {thr}: V(G) \rightarrow [0, t_{\max }]$ and an $\ell$-expression $f$ of $G$, computes the minimal size of a target set in time $\mathcal {O}( \ell ^{3 \ell t} \cdot t^{\ell (4t+1) } \cdot |f| )$, where $t := t_{\max }+1$ and $|f|$ is the length of $f$.

An easy upper bound for the length of the $\ell$-expression $f$ is $|V(G)|^2$. Further, one can obtain a minimum target set, and not only its size, by tracking such sets throughout our dynamic program.

Oum gave an algorithm that either outputs an $(8^\ell -1 )$-expression of graph $G$ or confirms that the clique-width of $G$ is larger than $\ell$, and that runs in time $\mathcal {O}( g(\ell ) \cdot |V(G)|^3 )$, where $g(\ell )$ only depends on the clique-width $\ell$ [17]. Combined with the algorithm of Theorem 1 it follows that TSS parameterized by the clique-width and the maximum threshold is in FPT.

Corollary 1

Target Set Selection is in FPT with respect to the combined parameters clique-width of the given graph and the maximum threshold.

Following the preliminaries in Sect. 2, we prove Theorem 1 in Sect. 3. We conclude in Sect. 4. Due to space constraints, we omit some proofs or only give a proof sketch. For the full proof, we refer to an online version at https://arxiv.org/abs/1710.00635.

2 Preliminaries

For integers $i < j$, let $[i] := \{1,2,\dots ,i\}$ and $[i,j] := \{i,(i\!+\!1),\dots ,j \}$. For a list (or vector) $A$, we describe the $i$-th element as $A[i]$.

All our graphs are simple, finite and undirected. For a graph $G$, we denote by $V(G)$ its set of vertices. We use $\mathsf {N}_{G}(v)$ as the neighborhood of vertex $v \in V(G)$. Usually we consider graphs with thresholds for each vertex $\mathsf {thr}: V(G) \rightarrow [0,t_{\max }]$ which are at most a constant $t_{\max }$, and assume that its thresholds $\mathsf {thr}$ and $t_{\max }$ are given, if needed.

In this work, we consider parameterized complexity. For an introduction see for example [9, 10, 12, 16]. For a graph class, for example clusters (the disjoint union of cliques), the parameter “distance to cluster” is the minimal number of vertices one needs to delete from the input graph in order to obtain a cluster.

The clique-width $\mathsf {cw}(G)$ of a graph $G$ was introduced in [8]. A graph has clique-width at most $\ell \in \mathbb {N}$, if it can be constructed by an $\ell$-expression that uses four types of operations and a labeling of the vertices of at most $\ell$ labels, as we describe in the following. Let $\mathsf {labels}(f)$ be the set of labels used by $f$. To avoid confusion with thresholds, we use small Greek letters $\alpha , \beta , \gamma$ for the labels. An $\ell$-expression defines a graph $G(f)$ with labels per vertex $\mathsf {lab}_G: V(G) \rightarrow \mathsf {labels}(f)$. The graph $G(f)$ is recursively defined as

• $G(v(\alpha ))$, a single vertex $v$ of label $\alpha \in \mathsf {labels}(f)$,

• $G(f_1 \oplus f_2)$, the disjoint union of $G(f_1)$ and $G(f_2)$ for $\ell$-expressions $f_1$, $f_2$,

• $G( \eta _{\alpha , \beta } f' )$, the graph $G(f')$ where there is an edge between every vertex of label $\alpha$ and every vertex of label $\beta$, for $\ell$-expression $f'$, and

• $G(\rho _{\alpha \rightarrow \beta } f')$, the graph $G(f')$ where all vertices of label $\alpha$ are re-labeled to label $\beta$, for $\ell$-expression $f'$.

The subexpressions of $f$ are all expressions $f_1, f_2, f'$ used in the recursive definition of $f$. Especially $f$ is a subexpression of $f$. We drop the $G( \cdot )$ when using $G(f)$ as a nested term. For example, instead of $V(G(f))$, we simply write $V(f)$. Further, we also refrain from specifying the set of labels $\mathsf {labels}(f)$ if it is clear from the context.

An $\ell$-expression is irredundant if for every subexpression $\eta _{\alpha ,\beta }f'$ the graph $G(\eta _{\alpha ,\beta }f' )$ has no edge between vertices of label $\alpha$ and $\beta$. We assume that the given $\ell$-expression is irredundant, which we can assure by a simple preprocessing step [8].

3 Dynamic Program

A good way to convince someone that a graph $G$ with thresholds has a target set of size at most $k$ is to state a complete ordering in which the vertices get active. We denote this permutation of the vertices as a global ordering ${\pi }: V(G) \rightarrow [|V(G)|]$. We say that ${\pi }$ is $k$-activating for graph $G$ if there is a $k$-vertex set $S \subseteq V(G)$, the target set, such that for every other vertex $v$ the neighbors of $v$ that are ordered before $v$ outnumber the threshold $\mathsf {thr}(v)$.

Definition 1

A global ordering of a graph $G$ is a permutation of the vertices ${\pi }: V(G) \rightarrow [|V(G)|]$. Further, ${\pi }$ is $k$-activating (for $G$) if there is a $k$-vertex set $S \subseteq V(G)$ such that for every vertex $v \in V(G) \setminus S$ we have

$$ {{\pi }}^{<}_{G}(v) \; := \; \big | \big \{ u \in \mathsf {N}_{G}(v) \; \big | \; {\pi }(u) < {\pi }(v) \big \} \big | \; \ge \; \mathsf {thr}(v) . $$

Graph $G$ has a target set of size $k$ if there is a global ordering ${\pi }$ such that ${\pi }$ is $k$-activating for $G$.

Example 1

The following graph $G$ has global ordering ${\pi }: v_i \mapsto i$, which is 1-activating (for $S = \{ v_1 \}$). Further, $f = \eta _{\beta ,\gamma } f' = \eta _{\beta ,\gamma } ( v_6(\gamma ) \oplus v_8(\gamma ) \oplus v_{11}(\gamma ) \oplus v_9(\gamma ) \oplus v_7(\beta ) \oplus \rho _{\gamma \rightarrow \alpha } \eta _{\beta ,\gamma } ( v_{10}(\gamma ) \oplus \rho _{\gamma \rightarrow \alpha } \eta _{\alpha , \beta } \eta _{\alpha ,\gamma } \eta _{\beta , \gamma } ( v_2(\gamma ) \oplus v_1(\beta ) \oplus v_3(\beta ) \oplus v_4(\alpha ) \oplus v_5(\alpha ) ) ))$ is a $3$-expression of $G$. For each vertex, the label among $\{\alpha ,\beta ,\gamma \}$ and threshold at most $t_{\max }= 2$ is given as a tuple.

For later examples, let $A := \big ( (\beta ,1),(\alpha ,1),(\beta ,1),(\alpha ,2),(\alpha ,2),(\gamma ,2),(\beta ,1),(\gamma ,2),(\gamma ,2) \big )$, and further $\eta _{\alpha ,\beta }f'$, $G$ and ${\pi }$ be as defined here.

An $\ell$-expression $f$ describes a graph $G(f)$ with three types of recursive operations that rely on $\ell$ different labels assigned to the vertices. We formulate a dynamic program over the subexpressions of $f$. At a current subexpression $f$, a state fixes a part of a global ordering ${\pi }$. Whether such a state is a part of a $k$-activating global ordering, is verified by considering the subexpressions with suitable states.

In order to obtain the desired FPT-runtime, we may only work with states that fix an ordering of a number of vertices bounded by our parameters, which are maximum threshold $t_{\max }$ and clique-width $\ell$. However, the number of all vertices described by a current subexpression is not bounded by our parameters. Our algorithm thus can only remember an ordering of a limited number of vertices and further cannot address these vertices directly. We identify the important verices and a suitable way to remember them. Crucial for the activation of a vertex is its threshold and neighborhood. Our local ordering can very well remember the threshold of vertices. However, it cannot address the neighborhood even for vertices of currently equal label and threshold since they can have very different neighborhoods as subexpression may reveal.

Consequently, our approach explores the given $\ell$-expression top down, and fixes an ordering of the important vertices of the graph described by the up to now seen part of the $\ell$-expression. The up to now seen operations define a common neighborhood for all vertices of a fixed label. This is because for every outer operation, two vertices of equal label behave equally. Thus, our local ordering can indirectly reference the vertices solely by their label and threshold.

Now, let us identify the vertices whose relative ordering is crucial. We can observe that vertices of the same label that occur late enough in a global ordering behave equally. An $\ell$-expression has only one type of operation that adds edges, namely $\eta _{\alpha ,\beta }$ for some labels $\alpha$ and $\beta$, which adds all edges between vertices of labels $\alpha$ and $\beta$. There, for a vertex $v$ of label $\alpha$ we have to account for the contribution to the activation of $v$ by the vertices of label $\beta$. Only the first $\mathsf {thr}(v) \le t_{\max }$ vertices of label $\beta$ of the global ordering ${\pi }$ are important. Consequently, if ${\pi }$ orders $v$ somewhere between the first $t_{\max }$ vertices of label $\beta$, the local ordering fixes the ordering of $v$ relatively to those first vertices of label $\beta$ as well. If ${\pi }$ orders $v$ after the first $t_{\max }$ of label $\beta$, we can neglect its exact ordering. This is because the number of neighbors of label $\beta$ that contribute to its activation do not differ from other such late vertices of label $\alpha$. Our plan therefore is that the local ordering fixes the relative positioning of these crucial first $t_{\max }$ vertices of every label.

Doing so, we need to guarantee that a vertex $v$ of label $\alpha$ that is not referenced by our local ordering is indeed ordered late enough. That is, the first $t_{\max }$ vertices of label $\beta$ occur before vertex $v$. In particular, the first $t_{\max }$ vertices of label $\beta$ are ordered before the $(t_{\max }+1)$-st of label $\alpha$. Then, given that $v$ is not referenced by our local ordering, there are at least $t_{\max }$ of label $\beta$ ordered before, or if there are not even as many of label $\beta$, accordingly less. We denote such an ordering as nice to the current subexpression $\eta _{\alpha ,\beta }f'$. It is possible to modify any valid global ordering such that it is nice to every subexpression. Therefore, our algorithm may only consider nice global orderings. We extend our local ordering to also include the $(t_{\max }+1)$-st vertex of every label. Then, whether the underlying global ordering ${\pi }$ is nice to a current expression $\eta _{\alpha ,\beta }f'$, is reflected in our local ordering. Our algorithm may then ignore states with such not nice local orderings.

We define the local ordering $A$ for a current $\ell$-expression $f$ that fixes the relative ordering of the first $(t_{\max }+1)$ activate vertices for each label $\alpha$ (or if there are not even as many vertices of label $\alpha$, accordingly less), which we denote by $t^{\alpha }$. We indirectly remember a vertex $v$ by fixing the label and threshold of $v$. For technical reasons, we define a local ordering as possibly incomplete. Our algorithm only considers complete local orderings.

Definition 2

Let $G$ be a graph with labels $\mathsf {lab}: V(G) \rightarrow \mathsf {labels}(G)$. For label $\alpha$, let $t^{\alpha }(G) :=\min \{ t_{\max }( G)+1,\; | \{ v \in V(G) \; | \; \mathsf {lab}(v) = \alpha \} | \}$. A local ordering $A$ of $G$ is a list of tuples of label and threshold $(\alpha , a) \in \mathsf {labels}(G) \times [0,t_{\max }(G)]$ such that for every label $\alpha$ there are at most $t^{\alpha }$ tuples of label $\alpha$; and $A$ is complete if, for every label $\alpha$, there are exactly $t^{\alpha }$ tuples of label $\alpha$.

The local ordering $A$ is our limited view on a global ordering ${\pi }$. Let $\mathsf {condense}({\pi })$ be the ordered list of vertices consisting of the first $t^{\alpha }$ vertices of each label $\alpha$. A global ordering ${\pi }$ extends $A$ if the tuples of label and threshold of $\mathsf {condense}({\pi })$ are equal to $A$. As a technical tool, we also define $\mathsf {condense}({\pi },A)$ as the first ordered vertices consisting of each label $\alpha$, such that the number of vertices labeled $\alpha$ is equal to as there are in $A$.

Definition 3

Let graph $G$ have global ordering ${\pi }$. Consider the list of vertices according to the global ordering ${\pi ^{-1}}(1), \dots ,{\pi ^{-1}}(|V(G)|)$. For every label $\alpha$, remove all vertices of label $\alpha$ but the first $t^{\alpha }$ vertices of label $\alpha$. Then, the resulting list is $\mathsf {condense}({\pi })$. Global ordering ${\pi }$ extends a local ordering $A$ (for $G$) if the list tuples of label and threshold of $\mathsf {condense}({\pi })$ is equal to $A$.

Let $\mathsf {condense}({\pi }, A)$ be the remaining list, after, for every label $\alpha$, removing all vertices of label $\alpha$ but the first $| \{ i \; | \; \mathsf {lab}(A[i]) = \alpha \} |$ of label $\alpha$.

Example 2

We have $t^{\alpha }, t^{\beta }, t^{\gamma } = 3$ and $A$ is a complete local ordering of $G$. Further, $\mathsf {condense}({\pi }) = \mathsf {condense}({\pi },A) = (v_1, \dots ,v_9)$, whose list of tuples of label and threshold is equal to $A$. Thus, $A$ extends ${\pi }$. Let incomplete local ordering $A^*$ contain only one tuple per label. Then, $\mathsf {condense}({\pi }, A^*)$ is the list of vertices $(v_1, v_2, v_6)$. The list of tuples of label and threshold is equal to $A^*$.

For an edge operation $\eta _{\alpha ,\beta }$, which adds all edges between vertices of two distinct labels, we simply have to adjust the number of neighbors contributing to an activation of a vertex according to our fixed local ordering. We remember this contribution as the activation from outside. The mapping $\mathsf {afo}$ maps to a value $[0,t_{\max }]$ for each position of the local ordering $A$, as well as maps to a value for each label. That way we have a value for every vertex indirectly referenced by $A$. Further, there is a value for every vertex $v$ not referenced by $A$, which we identify via the label of $v$.

A state of a current subgraph $G(f)$ is a tuple consisting of a local ordering $A$ and an activation from outside $\mathsf {afo}$. To reference the activation from outside for a concrete vertex $v$ we define ${A}^{{\pi }}(v)$ such that $\mathsf {afo}({A}^{{\pi }}(v) )$ is the activation from outside for $v$. Thus, ${A}^{{\pi }}(v)$ maps $v$ to its according position in $A$ if it exists and otherwise to the label of $v$. A global ordering ${\pi }$ is $k$-activating for a state $(A,\mathsf {afo})$ of $G$ if it is $k$-activating for $G$ while supported by the activation from outside $\mathsf {afo}$.

Definition 4

Let $f$ be an $\ell$-expression, and graph $G(f)$ have local ordering $A$. An activation from outside for $A$ is a mapping $\mathsf {afo}: [|A|] \cup \mathsf {labels}(f) \rightarrow [0,t_{\max }]$. Then, the tuple $(A,\mathsf {afo})$ is a state of $G(f)$. For a global ordering ${\pi }$ of $G(f)$, let ${A}^{{\pi }}: V(f) \rightarrow [|A|] \cup \mathsf {labset}f)$,

$$ {A}^{{\pi }}(v) \mapsto {\left\{ \begin{array}{ll} i, &{} i \in [|A|], \; v = \mathsf {condense}({\pi },A)[i], \\ \mathsf {lab}(v), &{} {else.} \end{array}\right. } $$

A global ordering ${\pi }$ of $G(f)$ is $k$-activating for $(A,\mathsf {afo})$ if there is $k$-vertex set $S \subseteq V(G)$ such that for every vertex $v \in V(G) \setminus S$ we have that

$$\begin{aligned} {{\pi }}^{<}_{G}(v) \; \ge \; \mathsf {thr}(v) - \mathsf {afo}({A}^{{\pi }}(v)) . \end{aligned}$$

Example 3

Let $\mathsf {afo}(1) = 1$, and for $x \in \{2,\dots ,6,\alpha ,\beta , \gamma \}$, let $\mathsf {afo}(x) = 0$. The activation from outside for vertex $v_1$ is $\mathsf {afo}( {A}^{{\pi }}( v_1 ) ) = \mathsf {afo}(1) = 1$ and for vertex $v_{10}$ it is $\mathsf {afo}( {A}^{{\pi }}(v_{10} )) = \mathsf {afo}( \alpha ) = 0$. Further, ${\pi }$ is $0$-activating for state $(A,\mathsf {afo})$.

We define nice orderings, analogously for global orderings ${\pi }$ and local orderings $A$. As we show in the following, for every $k$-activating global ordering ${\pi }$ there is a slightly modified $k$-activating global ordering ${\pi }$ which is nice to every subexpression of $f$. Our local ordering $A$ includes the $(t_{\max }+ 1)$-st vertex of every label. Thus, whether ${\pi }$ is to nice the current expression $f$ is expressed in the ordering of $A$. Therefore, our algorithm can avoid not nice global orderings by ignoring states where the local ordering $A$ is not nice to $f$.

Definition 5

Let $G$ be a graph with global ordering ${\pi }$. Let $f$ be an $\ell$-expression describing a subgraph of $G$. For label $\alpha$, let $v_\alpha [1], v_\alpha [2], \dots \in V(f)$ be the vertices of label $\alpha$ of $G(f)$ ordered ascending according to ${\pi }$. For every label $\alpha$, let $t_{\max }^{\alpha } :=\min \{ t_{\max }( G),\; | \{ v \in V(G) \; | \; \mathsf {lab}(v) = \alpha \} | \}$. Then, ${\pi }$ is nice to $f$ if $f = \eta _{\alpha ,\beta }f'$ implies that (if those respective positions exist)

$$ {\pi }( {v_\alpha }[t_{\max }\! + \! 1] ) \;> \; {\pi }( {v_{\beta }}[t_{\max }^{\beta }] ) \; \; \; { and } \; \; \; {\pi }( {v_\beta }[t_{\max }\! + \! 1] ) \; > \; {\pi }( {v_{\alpha }}[t_{\max }^{\alpha }] ) . $$

Let $A$ be the list of tuples of label and threshold of $\mathsf {condense}({\pi }\! \upharpoonright _{V(f)} )$ for graph $G(f)$, where ${\pi }\! \upharpoonright _{V(f)}$ is ${\pi }$ restricted to vertices $V(f)$. Then, $A$ is nice to $f$ if (and only if) ${\pi }$ is nice to $f$.

Example 4

Global ordering ${\pi }$ is not nice to $\eta _{\beta ,\gamma } f'$ since ${\pi }( {v_\beta }[t_{\max }+1] ) = {\pi }( v_7) = 7 \ngtr 8 = {\pi }(v_8) = {\pi }( {v_{\gamma }}[t_{\max }] )$. By switching the 7th and 8th position ${\pi }$ becomes nice to $\eta _{\beta ,\gamma } f'$. Likewise, $A$ is not nice to $\eta _{\beta ,\gamma } f'$, but $A' = \big ( (\beta ,1),(\alpha ,1),(\beta ,1),(\alpha ,2),(\alpha ,2),(\gamma ,2),\varvec{(\gamma ,2),(\beta ,1)},(\gamma ,2) \big )$ is nice to $\eta _{\beta ,\gamma } f'$.

Lemma 1

Let $f$ be an $\ell$-expression and ${\pi }$ a global ordering that is $k$-activating for graph $G(f)$. Then, there is a global ordering ${\pi }'$ that is $k$-activating for graph $G(f)$ and nice to every subexpression of $f$.

Proof

(Sketch). There may be subexpressions $\eta _{\alpha ,\beta }f'$ where the $(t_{\max }+ 1)$st vertex of label $\alpha$ is ordered before the first $t_{\max }$ vertices of label $\beta$, formally ${\pi }( v_\alpha [t_{\max }+ 1] ) =: i < {\pi }( v_\beta [t_{\max }^{\beta }])$. We repair such a violation by moving all vertices of $v_\beta [1], \dots , v_\beta [t_{\max }^\beta ]$ that did not occur already between positions $(i - 1)$ and $i$. Since there are $t_{\max }$ vertices of label $\alpha$ ordered before position $i$, the modified local ordering is still activating. We repair all such violations top-down. Following this order prevents recursive violations for already fixed subexpression $\eta _{\alpha ' \! , \beta '}$. For a full proof see online version.

Definition 6

Graph $G(f)$ is $k$-activating for a state $(A,\mathsf {afo})$ if there is a global ordering ${\pi }$ that extends $A$, is $k$-activating for $(A,\mathsf {afo})$, and is nice to every subexpression of $f$.

Lemma 2

Let $f$ be an $\ell$-expression. Then, graph $G(f)$ has a target set of size $k$ if and only if there is a complete local ordering $A$ of $G(f)$ such that $G(f)$ is $k$-activating for state $(A,\mathbf 0 )$, where $\mathbf 0 : [|A|] \cup \mathsf {labels}(G) \rightarrow \{0\}$.

Proof

(Sketch). Use Lemma 1. For a full proof see online version.

It remains to specify the recursive dependency of our computation. We distinguish the three operations, which are adding edges if $f = \eta _{\alpha ,\beta }f'$, taking the disjoint union if $f = f_1 \oplus f_2$, and re-labeling if $f = \rho _{\alpha \rightarrow \beta }f'$.

Consider a current $\ell$-expression $\eta _{\alpha ,\beta }f'$ and a state $(A,\mathsf {afo})$. The operation $\eta _{\alpha ,\beta }$ adds the edges between all vertices of label $\alpha$ and $\beta$. We adjust the activation from outside such that it replaces the edges between vertices of label $\alpha$ and $\beta$. The relative ordering of the first $(t_{\max }+1)$ vertices of label $\alpha$ and label $\beta$ is already fixed by the local ordering $A$. We increase the activation from outside of a position $y$ of $A$ of label $\beta$ for every prior position $x$ of $A$ of label $\alpha$. For the activation from outside for vertex $v$ of label $\alpha$ that is not referenced by $A$, every position $x$ of $A$ of label $\beta$ increases the activation from outside. We denote the result as $\eta _{\alpha ,\beta }\mathsf {afo}$.

Definition 7

Let graph $G$ with labels $\alpha$ and $\beta$ have local ordering $A$. For $y \in [|A|] \cup \mathsf {labels}(G)$, let

$$\begin{aligned}&(\eta _{\alpha ,\beta }\mathsf {afo}) (y) := \min \!\big \{ t_{\max }, \; \mathsf {afo}( y ) + \mathsf {add}({y}) \big \}, \; \; {where} \\&\mathsf {add}({y}) := | \big \{ x \in [|A|] \; \big | \; \; x<y, \; \{\mathsf {lab}(x),\mathsf {lab}(y)\} = \{\alpha ,\beta \} \big \} |, \end{aligned}$$

where $1< 2< \dots< |A| < \gamma$, for every label $\gamma$; and where $\mathsf {lab}(x)$, for $x \in [|A|]$, is defined as $\mathsf {lab}(A[x])$. For every vertex $v \in V(G)$, let

$$\begin{aligned} \mathsf {e}_{{\pi }}(v) := | \big \{ u \in V(G) \; \big | \; {\pi }(u) < {\pi }(v), \; \{ \mathsf {lab}(u), \mathsf {lab}(v) \} = \{\alpha ,\beta \} \big \} |. \end{aligned}$$

The number of edges that additionally contribute to the activation of a vertex $v$, denoted by $\mathsf {e}_{{\pi }}(v)$, is equal to the increase of the activation from outside $\mathsf {add}({v})$ (while ignoring an overall activation exceeding $t_{\max }$).

Lemma 3

Let global ordering ${\pi }$ extend local ordering $A$, which is nice to $\eta _{\alpha ,\beta }f'$. For every vertex $v \in V(\eta _{\alpha ,\beta }f')$, we have that

$$\begin{aligned} \min \{ t_{\max }, \; \mathsf {afo}({A}^{{\pi }}(v)) + \mathsf {e}_{{\pi }}(v) \} = (\eta _{\alpha ,\beta }\mathsf {afo}) ({A}^{{\pi }}(v)) . \end{aligned}$$

Proof

(Sketch). We need to show for every vertex $v$ that the number of new neighbors ordered before, $\mathsf {e}_{{\pi }}(v)$, is equal to how much we increase $\mathsf {afo}({A}^{{\pi }}(v))$, when capped by $t_{\max }$. Since $A$ is nice to $\eta _{\alpha ,\beta }f'$, this number of new neighbors is correctly expressed by comparing $v$ with its neighbors of label $\beta$ in $A$, which is how $\mathsf {add}({ {A}^{{\pi }}(v) })$ is computed. For a full proof see online version.

Lemma 4

Graph $G( \eta _{\alpha ,\beta }f' )$ is $k$-activating for state $(A,\mathsf {afo})$ if and only if $A$ is nice to $\eta _{\alpha ,\beta }f'$ and $G(f')$ is $k$-activating for $(A, \eta _{\alpha ,\beta }\mathsf {afo})$.

Proof

(Sketch). We assume that the $\ell$-expression $\eta _{\alpha ,\beta }f'$ is irredundant as mentioned in the preliminaries. Then, every edge between vertices of label $\alpha$ and $\beta$ is new to $G(f')$ such that ${{\pi }}^{<}_{\eta _{\alpha ,\beta }f'}(v) \; = \; {{\pi }}^{<}_{f'}(v) + \mathsf {e}_{{\pi }}(v)$. For the forward direction, let $G(\eta _{\alpha ,\beta }f)$ have global ordering ${\pi }$ that extends $A$, is $k$-activating for state $(A,\mathsf {afo})$ and nice to every subexpression of $\eta _{\alpha ,\beta }f'$. It follows directly that $A$ is nice to $\eta _{\alpha ,\beta }A$. We in particular show that the same ordering ${\pi }$ is $k$-activating for the modified state $(A,\eta _{\alpha ,\beta }\mathsf {afo})$. That is, every non-target set vertex $v$ has ${{\pi }}^{<}_{f'}(v) \ge \mathsf {thr}(v) - (\eta _{\alpha ,\beta }\mathsf {afo})({A}^{{\pi }}(v))$. We can follow this result from our initial observation and by applying Lemma 3. The backward direction is similar. For a full proof see online version.

In case of a current expression $f = f_1 \oplus f_2$, we have to show how to recursively rely on the subexpressions $f_1$ and $f_2$, analogously for $f = \rho _{\alpha \rightarrow \beta }f'$, on subexpression $f'$. For both cases, vertices of label $\beta$ potentially come from different sets of vertices. In case of a re-labeling form $\alpha$ to $\beta$, a vertex of label $\beta$ possibly had label $\alpha$ before or already had label $\beta$. In case of a disjoint union of subgraphs, a vertex of label $\beta$ (or any other label) can be from either subgraph $G(f_1)$ or $G(f_2)$. For our indirect referenced vertices of our local ordering $A$, we do not know the true origin. Thus, we have to try all possible partitions of label $\beta$ into labels $\alpha$ and $\beta$, respective all partitions of label $\beta$ (and every other label) into either subgraph. As the possible local orderings $A$ are bounded by our parameters, also the possible partitions are bounded by our parameters.

Definition 8

• (1) A state $(A,\mathsf {afo})$ of graph $G(f)$ completes a state $(A^*, \mathsf {afo}^*)$ if $A$ is complete, and removing from $A$, for every label $\alpha$, the last tuples of label $\alpha$ from $A$ until as many as in $A^*$ remain, results in $A^*$; and $\mathsf {afo}: [|A|] \cup \mathsf {labels}(f) \rightarrow [0,t_{\max }],$ maps $x$ to $\mathsf {afo}^*(x)$, if defined for $x$, and otherwise to $\mathsf {afo}^*\big ( \mathsf {lab}(A[x]) \big )$.

• (2) Let $(f_1 \oplus f_2)$ be an $\ell$-expression. Then, $\mathcal {S}[f_1 \oplus f_2,(A,\mathsf {afo})]$ is the family of every pair of states $\big ( (A_1,\mathsf {afo}_1), (A_2, \mathsf {afo}_2) \big )$ that complete the possible incomplete states $(A_1^*, \mathsf {afo}_1^*)$ and $(A_2^*, \mathsf {afo}_2^*)$ that can be constructed as follows. Start with states $(A_1^*, \mathsf {afo}_1^*)$, $(A_2^*, \mathsf {afo}_2^*)$ where $A_1^*= A_2^*= ()$ and, for every label $\alpha$, we have $\mathsf {afo}_i^*(\alpha ) = \mathsf {afo}(\alpha )$. For position $j$, beginning from $1$ to $|A|$, add $A[j]$ to the end of either list $A_i^*\in \{A_1^*, A_2^*\}$ where possible. For position $j \in [|A|]$, tuple $A[j]$ is added to list $A^*_i$, and let $j'$ be the position of $A[j]$ in $A^*_i$. Then, let $\mathsf {afo}_i^*(j') := \mathsf {afo}(j)$.

• (3) Let $(A,\mathsf {afo})$ be a state of $G( \rho _{\alpha \rightarrow \beta }f' )$. Then, $\mathcal {S}[\rho _{\alpha \rightarrow \beta }f',(A,\mathsf {afo})]$ is the family of every state $(A', \mathsf {afo}')$ that completes a state $(A^*,\mathsf {afo}^*)$ that can be constructed as follows. Re-label $s \in [0, t_{\max }^{\alpha }( f' )]$ many tuples of $A$ of label $\beta$ to $\alpha$, while at most $t_{\max }^{\beta }(f')$ of label $\beta$ remain, resulting in $A^*$. Let $\mathsf {afo}^*$ be defined as $\mathsf {afo}$ but where $\mathsf {afo}^*( \alpha ) = \mathsf {afo}(\beta )$.

Lemma 5

Graph $G( f_1 \oplus f_2 )$ is $k$-activating for state $(A,\mathsf {afo})$ if and only if there are states $\big ( (A_1,\mathsf {afo}_1),(A_2,\mathsf {afo}_2) \big ) \in \mathcal {S}[f_1 \oplus f_2,(A,\mathsf {afo})]$ and partition $k_1 + k_2 = k$ such that, for $i \in \{1,2\}$, graph $G(f_i)$ is $k_i$-activating for $(A_i, \mathsf {afo}_i)$.

Lemma 6

Graph $G( \rho _{\alpha \rightarrow \beta }f' )$ is $k$-activating for state $(A,\mathsf {afo})$ if and only if there is a state $(A',\mathsf {afo}') \in \mathcal {S}[\rho _{\alpha \rightarrow \beta }f',(A,\mathsf {afo})]$ such that $G(f')$ is $k$-activating for $(A',\mathsf {afo}')$.

Finally, we can show our main theorem, which was stated in the introduction.

Theorem 2

(Theorem 1 restated). Let $t_{\max }, \ell \in \mathbb {N}$. There is an algorithm that, given a graph $G$, a threshold for each vertex $\mathsf {thr}: V(G) \rightarrow [0, t_{\max }]$ and an $\ell$-expression $f$ of $G$,computes the minimal size of a target set in time $\mathcal {O}( \ell ^{3 \ell t} \cdot t^{\ell (4t+1) } \cdot |f| )$, where $t := t_{\max }+1$ and $|f|$ is the length of $f$.

Proof

The minimal size of a target set is the minimal $k$ of all local orderings $A$ of $G(f)$ such that $G(f)$ is $k$-activating for $(A,\mathbf 0 )$, as seen in Lemma 2.

Our algorithm computes the minimal $k$ for possibly each subexpression $f'$ of $f$ and state $(A,\mathsf {afo})$ of $G(f')$, in the fashion of dynamic programming. The minimum for a subexpression $f'$ and state $(A,\mathsf {afo})$ of $G(f')$ is remembered for future queries. There are at most $( \ell t )^{\ell t}$ possible local orderings $A$ for a subgraph $G(f')$. And there are at most $t^{ \ell t + \ell }$ possible activations from outside $\mathsf {afo}: [|A|] \cup \mathsf {labels}(f) \rightarrow [0,t_{\max }]$. Thus, there are at most $( \ell t )^{\ell t} \cdot t^{ \ell t + \ell }$ different states for a fixed subexpression. Further, every computation is the minimum of at most $(\ell t )^{2 \ell t}$ entries (an upper bound is guessing $A_1,A_2$ respectively $A'$ from scratch), and the minimum can be found in linear time. Therefore, the algorithm runs in time $\mathcal {O}( ( \ell t )^{\ell t} \cdot t^{ \ell t + \ell } \cdot (\ell t )^{2 \ell t} ) \cdot |f| = \mathcal {O}( \ell ^{3 \ell t} \cdot t^{\ell (4t+1) } \cdot |f| )$. If $(A,\mathsf {afo})$ is not a correct state for $G(f')$, set its minimum to $\infty$.

If $f$ contains only one operation, then $f = v(\alpha )$ and the only possible global ordering is ${\pi }: \{v\} \rightarrow \{1\}$. Graph $G(f)$ is at least $1$-activating, and possibly $0$-activating if $\mathsf {thr}(v) \ge \mathsf {thr}(v) - \mathsf {afo}(1)$. Answer accordingly in time $\mathcal {O}(1)$.

Otherwise, if $f$ consists of more than one operation, we have either of the recursive cases that $f$ is $\eta _{\alpha ,\beta }f'$, $f_1 \oplus f_2$ or $\rho _{\alpha \rightarrow \beta }f'$. According to Lemmas 5 and 6 respectively, graph $G(f_1 \oplus f_2)$ is $k$-activating for state $(A, \mathsf {afo})$ if and only if there is a pair of states $\big ( (A_1,\mathsf {afo}_1),(A_2,\mathsf {afo}_2) \big ) \in \mathcal {S}[f_1 \oplus f_2,(A,\mathsf {afo})]$ and partition $k_1 + k_2 = k$ such that, for $i \in \{1,2\}$, the graph $G(f_i)$ is $k_i$-activating for $(A_i,\mathsf {afo}_i)$;and graph $G(f\rho _{\alpha \rightarrow \beta }f')$ is $k$-activating if and only if there is a state $(A',\mathsf {afo}') \in \mathcal {S}[\rho _{\alpha \rightarrow \beta }f',(A,\mathsf {afo})]$ such that $G(f')$ is $k$-activating for $(A',\mathsf {afo}')$. Therefore, in those two cases we can recursively obtain a minimum size of a target set by querying for the according subgraphs $G(f'), G(f_1), G(f_2)$ and states $\big ( (A_1,\mathsf {afo}_1), (A_2,\mathsf {afo}_2) \big ) \in \mathcal {S}[f_1 \oplus f_2,(A,\mathsf {afo})]$ and $(A',\mathsf {afo}') \in \mathcal {S}[\rho _{\alpha \rightarrow \beta }f',(A,\mathsf {afo})]$, respectively. In case of $f = f_1 \oplus f_2$ the minimum size of a target set is the minimum of the sum of the minimum sizes for $f_1$ and $f_2$. For $f = \rho _{\alpha \rightarrow \beta }f$ the minimum size is equal to the minimum for $f'$.

According to Lemma 4, graph $G(\eta _{\alpha ,\beta }f')$ is $k$-activating for state $(A,\mathsf {afo})$ if and only if $A$ is nice $\eta _{\alpha ,\beta }f'$ and graph $G(\eta _{\alpha ,\beta }f')$ is $k$-activating for state $(A, \eta _{\alpha ,\beta }\mathsf {afo})$. Thus, in case of that $A$ is not nice to $f$ we can discard the current computation for a minimal size of a target set for the graph $G(\eta _{\alpha ,\beta }f')$ and state $(A, \mathsf {afo})$. Otherwise, the minimum size of a target set is equal to the minimum size of subgraph $G(f)$ with state $(A,\eta _{\alpha ,\beta }\mathsf {afo})$.

4 Conclusion

In this work, we gave an FPT-algorithm for TSS for the combined parameters clique-width and maximum threshold. This result generalizes all previous FPT-membership results of TSS with constant thresholds. It would be interesting to explore the whole dichotomy of constant TSS for common structural parameters. Is there a different dichotomy when the maximum threshold is a parameter and not a constant?