Maximizing the Spread of an Opinion in Few Steps: Opinion Diffusion in Non-Binary Networks

1 Introduction

Analyzing the diffusion of opinions in social networks is an important topic with obvious applications to marketing, disease spreading, and news propagation (we refer to a recent survey by Grandi [2017] for a comprehensive overview on the general topic of opinion diffusion in social networks).

As up-to-date social network data is becoming more and more readily available, as urgent is attaining an understanding for diffusion processes, as well as having algorithms that help to predict how opinions change over time. In particular, being interested in a specific opinion, answering the following questions is critical, and the main focus of our paper.

(1) What is the maximum possible spread of the opinion in the network? (2) How many update steps are needed to reach a stable state with maximum spread of some opinion? (3) What is the computational complexity of computing the maximum spread of the opinion in the network?

∗Contact Author

Exhaustive work was done with respect to these three questions with main focus on the case of two opinions (in the following called black and white) and when agents update their opinions according to the majority of their neighbors. Goles and Olivos [1980] showed that a sequence of synchronous updates always converges to a stable state or cycles with period two. Moreover, their analysis provides an upper bound of O(n2 ) on the number of updates with n being the number of agents. Frischknecht et al. [2013] showed that this quadratic bound is essentially tight, both for the synchronous model and for the asynchronous model. Note that the number of update steps for the synchronous update only depends on the network and the initial opinions. For the lower bound on the number of asynchronous update steps, one assumes that the sequence of updates is selected adversarially. In the synchronous model it is NP-hard to decide if there exists an initial opinion assignment for some given network such that convergence (to the two-periodic stable state) takes more than k rounds [Kaaser et al., 2016]. Kralovic [2001] studies a variant where changes from black to white are irreversible and where the social network is acylic. He develops an algorithm that tests whether a given configuration on an arbitrary tree evolves into an allblack state; the algorithm runs in time O(t log t), where t is the number of black nodes.

Probably closest to our work is that of Bredereck and Elkind [2017], in which all three questions are answered for the binary case. In particular, they show that one can compute an asynchronous update sequence that maximizes the number of black nodes in O(n) time. The sequence computed by their algorithm is of length at most 2n. Moreover, to maximize the number of black nodes, every agent needs to change its opinion at most twice.

Opinions have been modeled binary [Goles and Olivos, 1980], ternary [Auletta et al., 2019], as arbitrary finite set with a distance metric between the opinions [Chierichetti et al., 2013], via continuous values from the interval [0, 1] [Clifford and Sudbury, 1973], by rankings of alternatives [Brill et al., 2016], or even via collections of propositional formulas [Grandi et al., 2015; Slavkovik and Jamroga, 2016]. With respect to our three questions, however, little is known beyond the case of binary opinions. The result of Goles and Olivos [1980] for synchronous updates was subsequently extended to more general settings including an arbitrary number of opinions as well as weights on opinions and relations between agents [Goles and Tchuente, 1983]. Auletta et al. [2019] have considered the case of three opinions and showed that computing a sequence that maximizes the spread a specific opinion becomes more involved with a third opinion. They show, first, that a greedy algorithm as used in the binary case may fail dramatically, and second, that finding an update sequence that maximizes the number of black nodes is NP-hard.

In this paper we contribute to our three main questions with the following results. First, we extend the results of Frischknecht et al. [2013] and show that an update sequence is of length at most quadratic in the number of agents even if there are more than two opinions. Further we show that the lower bound of Ω(n2 ) on the number of updates holds even for spread-maximizing update sequences. Moreover we show that in acyclic influence networks, the length of a spreadmaximizing update sequence may be linear in the number of agents, and there may exist an agent whose opinion is changed a linear number of times. Towards the third question, we show multiple hardness results: First of all we show that there is (presumably) no efficient algorithm for finding a spread-maximizing update sequence on influence networks with more than two opinions, even if we require the sequence length to be short, or if we want to find an approximate spread-maximizing update sequence, or if every agent has at most three neighbors.

2 Model and Notation

An (undirected) k-opinion influence network (InfNet) is a pair (G, ◦) where G = (V (G), E(G)) is a simple, undirected graph and ◦: V (G) → {0, . . . , k - 1} is an opinion mapping that describes the initial opinions of all nodes. We set n = |V (G)| and m = |E(G)|. Without loss of generality we only consider InfNets (G, ◦) where G is connected. 1 For simplicity of illustration, if k = 3, then we say node v is black if ◦(v) = b = 0, white if ◦(v) = w = 1 and gray if ◦(v) = g = 2. For a non-black opinion x ∈ {w, g} we denote by x ∈ {w, g} \ {x} the non-black opinion opposing x.

For a node v ∈ V (G), we denote by N(v) := {u ∈ V (G) | {u, v} ∈ E(G)} the (open) neighborhood of v, that is, the set of all nodes that are connected to v by an edge. The degree of a node is the number of its neighbors. The maximum degree of G is the highest degree of a node in G.

During an update step, a node v in an influence network G changes its opinion if more than half of the nodes in its neighborhood N(v) have the same opinion which differs from the opinion of v. Updates are performed asynchronously, that is, the updates are performed one after another. We describe the order of updates by a sequence σ of nodes; the i-th node considers changing its opinion at step i. We denote by ◦[G, σ, z] the opinion mapping resulting from ◦ after z updates following the sequence σ. We use ◦[G, σ] as shortcut for the final outcome ◦[G, σ, |σ|]. A node v is stable if not more than half of the nodes in the neighborhood agree on a different opinion, and unstable otherwise. An opinion mapping ◦ is stable in a network G if every node is stable. A sequence is stable if the corresponding final outcome is stable. A node v is permanently stable if there exists no sequence such that the opinion of v is changed. We say that an update sequence is optimistic if it is stable and maximizes the number of black nodes in the final outcome.

1 If the InfNet consists of more than one connected component, we can find an optimistic sequence for each InfNet separately and concatenate them in an arbitrary order.

3 Lengths of Optimistic Sequences

This section deals with bounds on the lengths of optimistic update sequences. First, we provide upper bounds on the length of stable update sequences (which, of course, also bound the length of optimistic sequences). Second, we show lower bounds on the length of optimistic sequences. We provide a tight linear bound for acyclic influence networks and a tight quadratic bound for general influence networks.

3.1 Upper Bounds

As a warm-up we generalize two sequence length bounds provided by Frischknecht et al. [2013]. We first show that no sequence can be longer than the number of edges, essentially following the proof line of Frischknecht et al. [2013].

Proposition 1. A k-opinion InfNet on m edges reaches stability after at most m updates.

Frischknecht et al. proved the existence of 2-opinion InfNets that do not admit stable update sequences shorter than Ω(n) (clearly this holds for k > 2 as well). We provide an algorithm to match this lower bound for any k.

Proposition 2. For a k-opinion InfNet one can compute a stable update sequence of length at most n in O(kn) time.

Proof. We start with a greedy sequence σ: For i = 0, 1, . . . , (k - 1), in that order, update all nodes that can be updated to opinion i. Observe that nodes being updated to i either could have updated to i at any prior point in σ (this is always true for the first node to update to i), or can update to i only after some of their neighbors updated to i. We call these nodes fixed, resp. loose. Now we do the following for i = (k - 1), . . . , 0, for every loose node v being updated to i, for every opinion j < i: If v is updated to j, then remove this update, and remove all updates of nodes v′ that cannot be updated to j due to this removal. Note that v′ indeed is stable in this point of the sequence. After completing this for i, the nodes that are updated to j ≥ i are updated at most once and are all stable at the end of the sequence. As their update can only depend on updates of nodes to j, they are not affected by the following iterations. After having iterated through all i, every node was updated at most once; thus the sequence length is at most n. The claimed running time follows trivially.

Note that Proposition 2 does not show a linear upper bound for optimistic update sequences. Indeed, in the next section, we show that to maximize the number of black nodes, one may indeed need to update a quadratic number of nodes.

3.2 Lower Bounds

We now focus on optimistic update sequences and show lower bounds on the required number of updates on general and acyclic influence networks. For both results we only require three opinions, so throughout this section we assume that the opinion mapping maps to the opinions black, white and gray.

We start showing a tight linear lower bound on the minimum length of optimistic sequences for acyclic influence networks. While just a linear lower bound for acylic influence networks easy to see, our construction has the interesting property that it contains one node that needs to update its opinion a Ω(n) times.

Theorem 1. There exists a family of acyclic 3-opinion InfNets on O(n) nodes for which every optimistic update sequence updates at least one node Ω(n) times.

Proof sketch. Let c ∈ N. We construct an acyclic InfNet with O(c) nodes. First, we introduce a root node x with ◦(x) = w. Attached to x are c + 1 absorbing gadgets with opinion g, c absorbing gadgets with opinion w and two emitting gadgets.

An absorbing gadget with opinion z is constructed as follows. The root has opinion z, and two children: one path on two nodes with opinion z and one child with opinion z. The latter also has two children: one path on two nodes with opinion z and one child with opinion b. Attached to the latter is a path on two nodes with opinion z.

An emitting gadget is constructed as follows. The root has opinion g, and 2c children with opinion g, each of which have two paths on two nodes with opinion w attached to them, as well as 2c + 2 children with opinion w, each of which have two paths on two nodes with opinion g attached to them. Figure 1 shows the construction of the influence network.

Observe first that the black opinion cannot spread within this network. Next, note that in order to make the black node within an absorbing gadget with opinion z stable, the opinion of the two ancestors with opinion z must be changed to z. In order to do so, node x must acquire opinion z. Note though that only one absorbing gadget with opinion z can be updated at a time, since otherwise, x cannot update to z and the black nodes of all absorbing gadgets with opinion z cannot be made stable. Thus, x must change its opinion to white c times, and to gray c times. The task of the emitting gadgets is to change the opinion of their respective root node such that the majority of neighbors of x can be shifted from opinion z to z. In order to change the opinion of the root of an emitting gadget from z to z, two of its children with opinion z must update their opinion (recall that these children have two children on their own with opinion z).

Note that, since in acyclic InfNets we have n = m-1, the lower bound in Theorem 1 is tight up to a constant.

We now present a family of influence networks for which the length of any shortest optimistic update sequence is quadratic in the number of nodes. One component of our network is the two-opinion network (called snake graph in the following) introduced by Frischknecht et al. [2013] (Lemma 2) to show that there exists a (not necessarily optimistic) update sequence whose length is quadratic in the number of its nodes. Our goal is to enforce that every optimistic update sequence must have Ω(n2 ) updates. To this end, we add synchronization gadgets to the snake graph. We first present the construction of the two parts.

Snake graph. Let n ∈ N. We construct the following graph G on 6n nodes v0, . . . , v6n-1: If i ≤ 2n - 1, then we connect vi to vj for all j whose parity is different from the parity of i. For all even i ≤ 2n - 2 we connect vi to the nodes {v0, v2, v4, . . . , v6n-2i-2}. For all odd i ≤ 2n - 1 we connect vi to the nodes {v1, v3, v5, . . . , v6n-2i-3}. Finally, the nodes vi with even 2n ≤ i ≤ 6n - 2 form a clique, as do the nodes vi with odd 2n + 1 ≤ i ≤ 6n - 1. Initially, ◦(vi) = g if i is even, otherwise ◦(vi) = w.

For a node v we define the potential P(v) as

In our InfNet we initially have P(vi) = i + 1 if i is even, and P(vi) = i + 2 otherwise. Since the nodes v0, . . . , v2n-1 induce a complete graph we can observe the following.

Observation 1. Let 0 ≤ i ≤ 2n - 1. If vi changes its opinion to x ∈ {w, g}, then for all 0 ≤ j ≤ 2n - 1, j ̸= i, P(vj) increases by two if ◦(vj) ̸= x and decreases by two otherwise.

Synchronization gadgets. The adversary sequence presented by Frischknecht et al. performs 2n2 + n updates on v0, . . . , v2n-1 in a snake-like order. We now present the construction of the synchronization gadgets that ensure that every optimistic update sequence has at least Ω(n2 ) updates.

For 0 ≤ i ≤ n - 1 we introduce a white synchronization gadget SGwi and a gray synchronization gadget SGgi .

Let x ∈ {g,w}. Then, for 0 ≤ i ≤ n - 1 the synchronization gadget SGxi is constructed as follows: We introduce two main nodes axi and bxi with ◦(axi ) = x and ◦(bxi ) = x. Both axi and bxi have edges to the nodes inNi = c0∪ci-1∪ci (thus N0 = c0, N1 = c0 ∪ c1, and for i ≥ 2, |Ni| = 6). We add |Ni| + 4 paths on two nodes with opinion x, and connect one endpoint of each of the paths to axi . Analogously, we add |Ni| paths on two nodes with opinion x, and connect one endpoint for each of the paths to bxi . Next, we add a path on three nodes with one black endpoint and the other two nodes having opinion x, and add an edge between the black endpoint and aix . We do the same for bwi , but the two non-black nodes have opinion x. Lastly, we add two edges that start in bxi . If x = g then we add edges to bwi and to awi . If x = w then we add edges to bgi-1 and to agi-1 . For the special case of bw0 , we add a path on two nodes with opinion g and a path on two nodes with opinion w, and connect one endpoint of each to bw0 . Finally, we add one path on two nodes with opinion g and connect one endpoint to bgn-1 . Figure 2 shows the first six synchronization gadgets for i ≤ 2.

Sequence length. The general idea of the synchronization gadgets is the following. Observe first that the black opinion cannot spread within our network. In order to save the two black nodes of a synchronization gadget SGxi for x ∈ {w, g} and 0 ≤ i ≤ n-1, the node axi must change its opinion to x, and the node bxi must change its opinion to x. If bxi is updated to x, then we say that the synchronization gadget SGxi is fulfilled. But this is only possible if all neighbors of bxi in the snake graph have opinion x, and if all synchronization gadgets are updated in the correct order.

We first show that there actually exists an update sequence that preserves all black nodes in our constructed InfNet.

Lemma 1. There is an optimistic update sequence that keeps all black nodes stable.

Proof sketch. We denote by σ the reverse of the sequence σ. The sequence is the concatenation

We now show that the black nodes can only be rescued completely only if all synchronization gadgets are fulfilled in the correct order. For that we introduce some auxiliary notation: Let Y = {axi , bxi | 1 ≤ i ≤ n - 1, x ∈ {w, g}}. Next, for 1 ≤ i ≤ n - 1 and x ∈ {w, g} we denote by NY (bxi ) = N(bxi ) ∩ Y the set of "a" and "b" nodes that are neighbors of bxi .

Lemma 2. Every optimistic update sequence updates agi and bgi to white, resp. gray, after awi and bwi are updated to gray, resp. white, for 0 ≤ i ≤ n - 1. Every optimistic update sequence updates awi′ and bwi′ to gray, resp. white, after agi′-1 , and bgi′-1 are updated to white, resp. gray, for 0 < i′ ≤ n-1.

Proof sketch. We prove this lemma by proving the following two statements for a fixed j, 2 ≤ j ≤ n - 1:

• then agj-1 and bgj-1 must be updated after awj-1 and bwj-1 .
• If awj and bwj must be updated after agj-1 and agj-1 ,
• If agj and bgj must be updated after awj and bwj , then awj and bwj must be updated after agj-1 and bgj-1 .

We show how to prove (1) only; the correctness of statement (2) can be proven analogously. We first postulate first that, if bwj-1 is updated before bgj-1 , then awj-1 must be updated before bgj-1 , and agj-1 must be updated after bgj-1 : In order to set ◦(bgj-1 ) = g we require that all but one of the nodes in Nj-1 ∪ NY (bgj-1 ) are gray (this holds since |NY (bgj-1 )| = 4, and bgj-1 has |Nj-1| stable white neighbors, and a black neighbor). Note that, by assumption, ◦(bwj-1 ) = w; thus we must have ◦(u) = g for all u ∈ Nj-1 ∪ NY (bgj-1 ) \ {bwj-1 }, and specifially the nodes agj-1 and awj-1 must be gray (we know ◦(bwj = g) by assumption of statement (1)). So agj-1 must have already been updated, and awj-1 can only be updated after bgj-1 .

So to prove the correctness of (1), it suffices to show that bgj-1 is updated after bwj-1 . Assume towards a contradiction that this is not the case. In order to set ◦(bwj-1 ) = w we require that all but one of the nodes in Nj-1 ∪NY (bwj-1 ) are white. But ◦(bgj-1 ) = g; thus the rest of the nodes in Nj-1 ∪ NY (bwj-1 ) must be white; specifically, ◦(awj-1 ) = ◦(agj-2 ) = ◦(bgj-2 ) = w. But then, after the update of bwj-1 , its neighbor bgj-2 must be updated to gray. Again, for this we require that al but one of the nodes in Nj-2 ∪NY (bgj-2 ) are gray. Observe that the two nodes in the latter set, agj-2 and bwj-1 are both white. Clearly, the former of the two is stable, and from this it follows that the latter is stable as well. Hence, bgj-2 is stable and cannot be updated to gray; thus the update sequence is not optimistic-a contradiction.

We use the two statements as steps of an induction, the base case of which is that agj-1 and bgj-1 must be updated after awj-1 and bwj-1 . The correctness of the base case is similar to the correctness of statement (1) with j = n; note that bgn-1 does not have a neighbor bwn , but it does have a stable gray neighbor in its place. The last step of the induction (showing that aw0 and bw0 are updated before all other nodes in Y ) uses statement (2) with j = 1; note that bw0 does not have neighbors ag-1 and bg-1 , but it does have a stable gray neighbor and a stable white neighbor in their place.

Let us introduce the notion of phases. For 0 ≤ i ≤ n - 1, phase i ends with the update of bwi , that is, when SGwi is fulfilled. Phase 0 starts before the first update of the update sequence. For 1 ≤ i ≤ n - 1, phase i starts after the last update of phase i - 1.

Lemma 3. In phase i there are Ω(i) many updates within the snake graph.

Proof sketch. Throughout this proof we assume that node axi was updated immediately after bxi . Then, within the snake gadget, the potential of the nodes v0, . . . , v2n-1 is not affected by the opinions of the nodes in the snake gadgets. Note though that if axi is updated at another point in the sequence, this changes the number of required updates in phase i only by a constant.

Let nx = |{vi | 0 ≤ i ≤ 2n-1∧◦(vi) = x}| be the number of nodes within v0, . . . , v2n-1 with opinion x. We take a close look at v2i-1 just after phase i-1 ended. Note that at the end of phase i - 1, the nodes v0, v1, v2i-2, v2i-1, v2i, v2i+1 must have opinion white. Let x = P(v2i-1) = 2i + ng -

nw + 1 Note that nw - ng = 2i + 1 - x. So

We consider three cases and show that in each case we require Ω(i) updates during phase i.

(1) Suppose x ≤ 1. Then P (v2i-2) ≤ -4i+x, and in order to update v2i-2 to gray (which is required to fulfill SGi(g)), at least 2i = Ω(i) nodes must be updated to gray to make v2i-2 unstable, that is, to make the potential of v2i-2 positive.

(2) Suppose x = 4i - c > 1, where 0 ≤ c ≤ 4i is an odd integer number. It suffices to consider odd c since the degree of all nodes in the snake graph is odd; thus their potential is odd as well. Observe that P (v2i-2) ≤ -4i + x = -c, and in order to update v2i-2 to gray, at least (c + 1)/2 nodes must be updated to gray in order to make v2i-2 unstable.

Note that in order to fulill SGgi we must have updated v2i-2 as well as at least (c + 1)/2 other nodes (including v2i-1) to gray. Suppose that we did this; more specifically, suppose that between the end of phase i - 1 and fulfilling SGgi we updated y ≥ 0 nodes to white and z ≥ (c + 1)/2 + y + 1 nodes to gray. Then ng increases by z - y and nw increases by y-z. Thus nw -ng increases by 2(y-z) ≤ 2y-2((c+ 1)/2 + y + 1) = -c - 1 + 2. Then

and in order to fulfill SGwi+1 and thus to end phase i, we require at least 2i - 1 = Ω(i) updates from gray to white. (3) Suppose x = 4i + c where c ≥ 0 is an odd integer number. Observe that P(v2i-2) ≤ -4i + x = c. Then, in order to fulfill SGgi , the six nodes controlled by said synchronization gadget must be updated from white to gray. Suppose that between the end of phase i - 1 and fulfilling SGgi we updated y ≥ 0 nodes to white and z ≥ y + 6 nodes to gray. Then ng increases by z - y and nw increases by y - z.

Thus nw - ng increases by 2(y - z) ≤ -12. Then

and in order to fulfill SGi+1(w) and thus to end phase i, we require at least (4i+c+10+1)/2 = 2i+5+(c+1)/2 = Ω(i) updates from gray to white.

Thus, overall, an optimistic update sequence must be of length at least ∑n-1 i=0 Ω(i) = Ω(n2 ).

Theorem 2. There exists a family of 3-opinion InfNets on n nodes for which every optimistic update sequence updates at least one node Ω(n) times, and is of length Ω(n2 ).

4 Computing Optimistic Sequences

In this section, we analyze the computational complexity of computing a optimistic update sequence. Formally, we consider the following decision problem.

• k-OPTIMISTIC UPDATE SEQUENCE (k-OPT-SEQ)

Given an InfNet (G, ◦), with k opinions, and a positive integer q, is there a stable update sequence σ such that the final number of black nodes is at least q, i.e., |{v ∈ V (G) | ◦[G, σ](v) = 0}| ≥ q?

Auletta et al. [2019] have shown NP-hardness for a very related problem. The main difference is that in their diffusion model, an agent might even update its opinion when only a weak majority of neighbors agrees on a different opinion. Moreover, they assume that every agent updates its opinion only a constant number of times (and this constant is given as a parameter to their problem name). We remark that it seems possible to adapt their hardness proof for our model so that general NP-hardness of 3-OPT-SEQ is not surprising.

What might, however, be unexpected is that we can show intractablity of 3-OPT-SEQ for highly restricted cases. In the next theorem, we show this problem remains intractable even if the InfNet has few black nodes, few initially unstable nodes, and short optimistic update sequences, while aiming only for an approximate solution.

Theorem3. 3-OPT-SEQ is NP-hard andW[2]-hard parameterized by sequence length |σ|. Both holds even if the number of black nodes in the given InfNet is two and the number of initially unstable nodes is three.

Proof. We showW[2]-hardness using a parameterized reduction from SET COVER, which is defined as follows: Given a finite set U = {u1, . . . , ut}, a family S = {S1, . . . , Sr} of subsets of U, and a nonnegative integer h, SET COVER asks whether there is a set cover of size h, that is, whether there is a size-h set S ′ ⊆ S such that ⋃S∈S ′ S = U. Let (U, S, h) be a SET COVER instance. We construct an equivalent 3-OPTSEQ instance as follows (see Figure 3 for an illustration).

For each element ui ∈ U, create an element node vi with opinion ◦(vi) = g. For each subset Sj ∈ S, create one subset node wj with opinion ◦(wj) = w. For each i ∈ [t], j ∈ [r] with ui ∈ Sj add the edge {vi, wj}.

We create two covering nodes c1 with ◦(c1) = b and c2 with ◦(c2) = g as well as two budget nodes b1 with ◦(b1) = b and b2 with ◦(b2) = w. Finally, we create four activator nodes a0, a′0 , a1, and a′1 with ◦(a0) = g and ◦(a′0 ) = g, ◦(a1) = w, and ◦(a′1 ) = g.

We connect the covering node c2 with every element node vi, the budget nodes b2 as well as activator nodes a1 and a′1 , with every subset node wj, as well as c1 with c2, b1 with b2, and c1 with b1. The activator nodes a0 and a′0 are both connected to every element node. The subset node wj is connected to element node vi if and only if ui ∈ Sj.

Each node has a certain number of stable leaf nodes. Technically, a stable leaf node ℓ with opinion ◦(ℓ) = x attached to some node v in fact has a second neighbor ℓ′ (besides neighbor v) with the same opinion ◦(ℓ′ ) = x. In effect, both ℓ and ℓ′ are permanently stable.

To describe the leaf nodes, let #(ui) := |{Sj ∈ S | ui ∈ Sj}| be the number of occurrences of element ui. Node c1 has one stable leaf with opinion w and node b1 has one stable leaf with opinion g. Node c2 has t stable leaves with opinion w, node a0 has t + 1 stable leaves with opinion w, node a′0 has t + 1 stable leaves with opinion g, node a1 has r + 1 stable leaves with opinion g, and node a′1 has r + 1 stable leaves with opinion w. Every element node vi has #(ui) - 2 stable leaves with opinion g and every subset node wj has |Sj| - 1 stable leaves with opinion w. Finally, node b2 has r-h stable leaves with opinion g and h leaves with opinion w.

Setting q := 2 finishes the construction which can clearly be performed in polynomial time.

Let us sketch the idea and basic observations of the correctness. Observe that no node can change its opinion to black. So we need to ensure that c1 and b1 remain black. For this we must ensure that c2 and b2 will also keep their opinions. However, node c2 can only keep its opinion if all element nodes keep their opinion, which in turn is only possible if every element node has at least one neighboring subset node that changes its opinion to g (corresponding to a set cover). Moreover, if more than h subset nodes change their opinions, then b2 must also change. Initially, only a0, a1 and a′1 are unstable. At some point, a0 must change its opinion to w so that, every element node, to keep opinion g, needs at least one neighboring subset node that changes its opinon to g. Nodes a1 and a′1 will swap their opinions. If we update a1 before a′1 , we can change the opinion of arbitrary subset nodes to g between the two updates, while we require for our graph to update at most h subset nodes such that every element node is neighboring one of the updated ones. Further, to keep the chosen subset nodes stable, at least one of the neighboring leaves has to update at any later point eventually as we require these subset nodes to be of opinion gray at the end of the update sequence, also requiring them to be stable.

Chen et al. [2006] show that, unless the Exponential Time Hypothesis (ETH) breaks, there is no f(h)ro(h) -time algorithm for SET COVER. Consequently we obtain:

Corollary 1. There is no f(|σ|)no(|σ|) -time algorithm for 3-OPT-SEQ unless ETH breaks.

We can actually show that the reduction behind Theorem 3 still works when setting q = 1. This excludes approximation algorithms even if they may use f(|σ|) · no(|σ|) time.

Corollary 2. Let (G, ◦) be an InfNet. Finding a stable update sequence σ with |{v ∈ V (G) | ◦[G, σ](v) = 0}| ≥ 1 is NPhard and W[2]-hard with respect to |σ|.

Finally, using a reduction from MAX 2-SAT we show that 3-OPT-SEQ remain hard even if every node has degree three.

Theorem 4. 3-OPT-SEQ is NP-hard, even if the maximum degree of G is at most three.

5 Conclusion

This paper essentially shows that few steps are not enough for optimistic update sequences, first in the sense that computing (even approximate) optimistic update sequences is highly intractable, and second in the sense that in general networks optimistic sequences may have to be of quadratic length and that even in acylic networks single nodes may have to update their opinions many times. The last result is of particular interest since it answers an open question implied by Auletta et al. [2019]: They formulated a polynomial-time algorithm for finding a spread-maximizing update sequence on acyclic three-opinion influence networks in which agents may change their opinion a constant number of times. Thus, our result shows that this algorithm cannot be used on acyclic networks in general, and whether one can find optimistic sequences on acyclic networks efficiently remains open.

Acknowledgements

Lilian Jacobs was supported by the DFG project "FPTinP" (NI 369/16).