Paper deep dive
What Makes Majority Illusion Easy to Detect?
Šimon Schierreich, Ildikó Schlotter
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 7/9/2026, 1:17:25 AM
Summary
The paper investigates the computational complexity of detecting majority illusion in social networks, where agents incorrectly perceive a minority opinion as dominant. It formally studies the q-Majority Illusion problem and systematically analyzes how various structural graph parameters (e.g., vertex integrity, feedback edge set, feedback vertex set, vertex cover, neighborhood diversity) influence tractability. The authors establish fixed-parameter tractable (FPT) algorithms for some parameters, while proving W[1]-hardness or XP complexity for others, providing a detailed map of the problem's computational landscape.
Entities (10)
Relation Signals (8)
Šimon Schierreich → authored → q-Majority Illusion Problem
confidence 98% · What Makes Majority Illusion Easy to Detect? Šimon Schierreich1, Ildikó Schlotter2,3
q-Majority Illusion Problem → studies → Majority Illusion
confidence 97% · We study the fundamental question of detecting whether a social network allows for a majority illusion.
Social Network → modeledas → Undirected Graph
confidence 95% · Lerman, Yan, and Wu (2016) suggest representing the social network as an undirected graph G where vertices correspond to agents
Vertex Integrity → parameterizes → q-Majority Illusion Problem
confidence 94% · We begin with parameterization by vertex integrity. This parameter lies between vertex cover number, which yields an FPT algorithm, and treewidth, which is known to be in XP.
Vertex Integrity → yieldscomplexity → Fixed-Parameter Tractability
confidence 93% · We show that this parameterization also admits an FPT algorithm by formulating our problem as an N-fold integer linear program
Feedback Vertex Set → yieldscomplexity → W[1]-hardness
confidence 93% · Namely, both the vertex-distance to disjoint paths and the vertex-distance to disjoint stars parameterizations are W[1]-hard.
Feedback Edge Set → yieldscomplexity → Fixed-Parameter Tractability
confidence 92% · if the social network has small edge-distance from being a tree (i.e., has small feedback edge set number), then an FPT algorithm is possible.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Majority illusion is an undesirable phenomenon in social networks in which agents incorrectly perceive a minority opinion as dominant. This can severely distort collective behavior and decision-making. We study the fundamental question of detecting whether a social network allows for a majority illusion. Formally, in the $q$-Majority Illusion problem, we ask whether there exists a binary labeling of agents in which at least a $q$-fraction of agents have the majority of neighbors with the minority label. We investigate how various structural properties of the underlying social network influence the tractability of this question, and provide a detailed map of its computational complexity.
Tags
Links
- Source: https://arxiv.org/abs/2606.04260v1
- Canonical: https://arxiv.org/abs/2606.04260v1
PDF not stored locally. Use the link above to view on the source site.
Full Text
150,135 characters extracted from source content.
Expand or collapse full text
What Makes Majority Illusion Easy to Detect? Šimon Schierreich1, Ildikó Schlotter2,3 Abstract Majority illusion is an undesirable phenomenon in social networks in which agents incorrectly perceive a minority opinion as dominant. This can severely distort collective behavior and decision-making. We study the fundamental question of detecting whether a social network allows for a majority illusion. Formally, in the q-Majority Illusion problem, we ask whether there exists a binary labeling of agents in which at least a q-fraction of agents have the majority of neighbors with the minority label. We investigate how various structural properties of the underlying social network influence the tractability of this question, and provide a detailed map of its computational complexity. 1 Introduction It is well-known in social sciences and behavioral economics literature that people tend to adapt their preferences to preferences of their “neighbors” (Asch 1951; Banerjee 1992; Cialdini and Goldstein 2004). Nowadays, this effect is drastically amplified by social networks. According to a recent survey by UNESCO (2023), over 56% of people worldwide consider social media as their primary source of information. This means that their opinions, beliefs, and worldviews are mostly formed on social media. However, social networks are well known to suffer from various undesirable phenomena, from echo chambers (Garimella et al. 2018; Cinelli et al. 2021), through polarization (Musco, Musco, and Tsourakakis 2018), misinformation spread (Vosoughi, Roy, and Aral 2018), to fake accounts (Ferrara et al. 2016; Yang et al. 2020), and many others (Woolley and Howard 2018). An important example of such phenomena is the so-called majority illusion. Intuitively, an agent is under majority illusion if they wrongly perceive the minority viewpoint as prevailing in society. More formally, Lerman, Yan, and Wu (2016) suggest representing the social network as an undirected graph G where vertices correspond to agents and there is an edge between two agents if they have some social relationship—they are, e.g., friends, colleagues, or neighbors. Moreover, there is a labeling f that assigns each agent one of two possible viewpoints, say blue and red. Assume that the majority of agents are labeled blue. Then an agent a is under majority illusion if the strict majority of their neighbors in G are labeled red. See Figure˜1 for an instance where every agent is under majority illusion. Figure 1: An example of a social network where all agents are under majority illusion. There are 44 red (light) agents and 66 blue (dark) agents, so blue is the majority label. Every blue agent has exactly one neighbor, which is red. Every red agent has exactly three red neighbors and at most two blue neighbors. Thus, each agent incorrectly perceives the majority label to be red. Building on the work of Lerman, Yan, and Wu (2016), who mainly focused on computational simulations to observe how common majority illusion is in random graphs, Grandi et al. (2025) initiated the formal study of the computational complexity of detecting majority illusion in social networks. In the q-Majority Illusion problem, we are given a social network, and the task is to decide whether a labeling f exists such that at least a q-fraction of agents are under majority illusion. In particular, they showed that detecting majority illusion is computationally intractable. Later, Venema-Los, Christoff, and Grossi (2025) extended the work of both Lerman, Yan, and Wu (2016) and Grandi et al. (2025) by studying, both theoretically and experimentally, which graph classes guarantee that at least a q-fraction of agents are under majority illusion. We now describe the results of Grandi et al. (2025) in more detail, as our work directly builds on theirs. They showed that q-Majority Illusion is NP-complete in general, even if the underlying social network is bipartite, of maximum degree 66, or planar. In contrast, they proved that the problem is in XP when parameterized by the treewidth of G, and provided FPT algorithms for parameterization by the vertex cover number and neighborhood diversity. While these results give us a basic understanding of structural restrictions that render the problem (in)tractable, they do not resolve the crucial question: What structural restrictions make the majority illusion easy to detect? And indeed, Grandi et al. (2025) specifically call for “another good parametrization.” Our Contribution vc [C1] mln cdn [T10] dcq fes [T2]ddp [T7]3pvctcnddds [T3]4pvcvi [T1]fvstd [T4]dcg [T8,T9] tw Figure 2: An overview of our results. q-Majority Illusion is in FPT for parameters shown in green, while it is W[1]-hard and in XP for orange ones. A yellow background indicates parameters that are only known to be in XP without matching W[1]-hardness. An arrow from parameter p to parameter p′p means that p′p is bounded by a function of p, and thus fixed-parameter tractability for p′p implies the same for p. Solid borders indicate results proved in this paper; dashed borders indicate improved running times over previous algorithms. All parameters are formally defined in Section˜2. We address the challenge posed by Grandi et al. (2025) and investigate what makes majority illusion tractable. To do so, we systematically study the problem from the perspective of structural graph parameters, significantly improving our understanding of the tractability landscape; see Figure˜2 for a basic overview of our results. Such approach is very common in computational social choice and social networks analysis; see, e.g., the survey by Bredereck, Chen, and Woeginger (2013). We begin with parameterization by vertex integrity. This parameter lies between vertex cover number, which yields an FPT algorithm, and treewidth, which is known to be in XP. Informally, vertex integrity measures the number of vertices one must remove to obtain disjoint components of bounded size. This parameter is expected to be bounded for social networks containing a group of “super-stars” while the remaining agents form small and independent communities. We show that this parameterization also admits an FPT algorithm by formulating our problem as an N-fold integer linear program—a technique that may be of independent interest. Our algorithm also yields an exponential speedup for parameterization by vertex cover number over the approach of Grandi et al. (2025). Next, we turn our attention to parameters based on small edge- or vertex-distance to some graph class for which computing majority illusion is polynomial-time solvable. First, we show that if the social network has small edge-distance from being a tree (i.e., has small feedback edge set number), then an FPT algorithm is possible. However, perhaps surprisingly, this approach does not generalize to graphs with small vertex-distance to a tree (i.e., the feedback vertex set). In fact, we show even stronger intractability results. Namely, both the vertex-distance to disjoint paths and the vertex-distance to disjoint stars parameterizations are W[1]-hard. These two results also resolve the probably most important open question left by Grandi et al. (2025) about the parameterization by treewidth: the above results imply that for this parameterization, an FPT algorithm is, under standard complexity-theoretic assumptions, unlikely. Finally, we turn our attention to dense social networks, i.e., networks that are highly connected. Intuitively, one could expect that for such networks, the detection of majority illusion will be much easier from the computational complexity perspective, as the agents have knowledge about the labels of a significant fraction of the other agents. And indeed, Grandi et al. (2025) showed that if the network is of bounded neighborhood diversity, majority illusion detection is fixed-parameter tractable. We complement their results by showing that for the parameterization by the vertex distance to disjoint cliques, the problem is in XP and, at the same time, is W[1]-hard. We complement this result with an FPT algorithm for social networks of bounded edge distance to disjoint cliques. Related Work Apart from works directly related to the detection of majority illusion described above (Lerman, Yan, and Wu 2016; Grandi et al. 2025; Venema-Los, Christoff, and Grossi 2025), there are several papers studying the elimination of majority illusion. In this line of research, initiated by Grandi et al. (2025), we are given a social network together with a majority-illusion labeling, and the goal is to alter a small number of agents (Fioravantes et al. 2025b), edges (Grandi et al. 2025; Dippel et al. 2025), or labels (Jana and Roy 2026) so that the majority illusion is completely eliminated. All of these works use the framework of parameterized complexity to characterize social networks that allow for efficient illusion elimination. However, we note that illusion elimination is substantially different from the detection problem we study in this work, so the results do not carry over to our setting. Majority illusion is also closely related to models of social influence in social networks (Kempe, Kleinberg, and Tardos 2015; Grandi 2017; Doucette et al. 2019; Auletta, Ferraioli, and Greco 2020). In these works, agents have some initial belief, and, in discrete steps, their beliefs update based on the majority belief in their neighborhood. Many works study the computational complexity of deciding how to initially label the social network so that the spread of the preferred opinion is maximized (Kempe, Kleinberg, and Tardos 2015; Bredereck and Elkind 2017; Wilder and Vorobeychik 2018; Faliszewski et al. 2018; Bredereck, Jacobs, and Kellerhals 2020; Castiglioni et al. 2021; Schierreich 2023; Knop, Schierreich, and Suchý 2026). Clearly, if one can find a labeling such that each agent is under majority illusion, then in one step, all agents hold the minority opinion. 2 Preliminaries Let G be a social network represented as an undirected graph over a set N of agents. For an agent a∈Na∈ N, let G(a)N_G(a) denote the set of its neighbors in G; we let degG(a)=|G(a)| _G(a)=|N_G(a)|. If G is clear from the context, we may drop the subscript. Additionally, we let S(a)=S∩(a)N_S(a)=S (a) for any subset S of agents. We say that two agents a,a′∈Na,a ∈ N are twins if (a)∖a′=(a′)∖aN(a) \a \=N(a ) \a\. In this paper, a labeling of a set A⊆NA N of agents is a mapping from A to ,\ red, blue\, classifying each agent in A as either red or blue; a labeling for G is one for N. For a set A of agents and a labeling f of G, let #f(A)\# r_f(A) and #f(A)\# b_f(A) denote the number of red and blue agents within A, resp. We will usually assume that blue is the majority color in f, that is, #f(N)>#f(N)\# b_f(N)>\# r_f(N). Some agent a has majority-red neighborhood if #f((a))>#f((a))\# r_f(N(a))>\# b_f(N(a)), and a is under majority illusion if the majority color for f is blue but a has majority-red neighborhood (or vice versa). For a set A⊆NA N of agents, we let μf(A) _f(A) denote the number of agents under majority illusion in A under f, and μ^f(A) μ_f(A) the number of agents in A with a majority-red neighborhood. Structural Graph Parameters Let us briefly summarize the key graph parameters that we use in our study to describe the structural properties of a social network. Given a graph G=(V,E)G=(V,E) and a set S of vertices (or edges), let G−SG-S denote the graph obtained from G by deleting all vertices (or edges, resp.) of S. The feedback vertex (or edge) set number of G, denoted by fvs(G)fvs(G) (or fes(G)fes(G)), is the minimum size of a set S of vertices (or edges, resp.) such that G−SG-S is acyclic. The distance to cluster graphs, to disjoint paths, or to disjoint stars of G, denoted by dcg(G)dcg(G), ddp(G)ddp(G), or dds(G)dds(G), is the minimum size of a vertex set S such that G−SG-S is the disjoint union of cliques, paths, or stars, respectively. The twin-cover (tctc) of G is a variant of the distance to cluster graph where all vertices of G−SG-S are twins in G. An edge equivalent of dcg(G)dcg(G) is cluster edge deletion number cdn(G)cdn(G), which is the minimum number of edges we need to remove from G to obtain a disjoint union of cliques. The vertex cover number of G, denoted by vc(G)vc(G) is the minimum size of set S⊆VS V such that G−SG-S has no edges. The vertex integrity of G, denoted by vi(G)vi(G), is the value minS⊆N|S|+ccmax(G−S) _S N|S|+c (G-S) where ccmax(G−S)c (G-S) is the size of a largest connected component in G−SG-S; a vivi-set of G is then a set S for which this expression takes the minimum. The maximum leaf number (mlnmln) of a graph G is the maximum number of leaves in a spanning tree of G. The distance to clique of G is the minimum number of vertices whose deletion from G results in a single clique. The ℓ -path vertex cover of G for some integer ℓ is the minimum number of vertices whose deletion from G results in a graph in which no simple path contains ℓ vertices. The neighborhood diversity of G is the minimum number of vertex sets into which the vertex set of G can be partitioned such that all vertices within each set are twins. The span of a rooted tree is the graph constructed from that tree by adding an edge u,v\u,v\ for each pair of vertices u and v where u is an ancestor of v. The treedepth of G is then the smallest height of a rooted tree T such that G is a subgraph of the span of T. A tree-decomposition of G is a pair (T,(Bt)t∈V(T))(T,(B_t)_t∈ V(T)) where T is a tree whose each node t is associated with a subset BtB_t of vertices in G, called a bag, in a way that (i) each vertex of G appears in some bag, (i) for each edge in G there is a bag containing both of its endpoints, and (i) for each vertex v of G, the set t∈V(T):v∈Bt\t∈ V(T):v∈ B_t\ induces a subtree of T. The width of a tree-composition is the size of its largest bag minus 11, and the treewidth of G is the minimum width of any tree-decomposition of G. Parameterized Complexity The framework of parameterized complexity allows us to examine computationally hard problems in a detailed fashion. In a parameterized problem Q, each input instance I is associated with an integer parameter k, and an algorithm’s running time is measured as a function of both |I||I| and k. An algorithm for Q is fixed-parameter tractable (FPT) if it runs in f(k)|I|(1)f(k)|I|^O (1 ) for some computable function f. By contrast, an XP algorithm runs in |I|(f(k))|I|^O (f(k) ) time for some computable function f. The class of parameterized problems admitting an FPT (or XP) algorithm is denoted by FPT (or XP, respectively). Showing that some problem is not likely to be in FPT can be done by proving its W[1]-hardness, via a parameterized reduction from some parameterized problem already known to be W[1]-hard. For an introduction and more details on this framework, see e.g., the book (Cygan et al. 2015). N-fold Integer Programming In an N-fold IP, the goal is to minimize a linear objective f over a set of structured constraints. Formally, let r,D∈ℕr,D and si,ti∈ℕs_i,t_i for every i∈[D]i∈[D]. An N-fold IP contains d=∑i∈[D]tid= _i∈[D]t_i variables partitioned into D bricks; let vector ()x^(i) denote be the i-th brick. Then, the constraints have the following form: ()+⋯+() _1x^(1)+·s+E_Dx^(D) =0 =b_0 (1) ∀i∈[D] ∀ i∈[D] () _ix^(i) =i =b_i (2) ∀i∈[D] ∀ i∈[D] ℓi≤() _i ^(i) ≤i _i (3) where ∈ℤr×tiE_i ^r× t_i, ∈ℤsi×tiA_i ^s_i× t_i, 0∈ℤrb_0 ^r, i∈ℤsib_i ^s_i, and ℓi,i∈ℤti _i,u_i ^t_i for each i∈[D]i∈[D]. We call constraints of type (1) global and constraints of type (2) local. 3 Bounded Vertex Integrity We begin by showing the fixed-parameter tractability of q-Majority Illusion with respect to the vertex integrity of the social network. This parameter is indeed relevant for social networks, as there are examples where we have a set of “influencers” and the remaining agents can be partitioned into small and disjoint communities. Also note that this parameter has been used in several similar works (Dvořák et al. 2017; Bodlaender et al. 2020; Fioravantes, Gahlawat, and Melissinos 2025; Knop, Schierreich, and Suchý 2026). The algorithm is based on an N-fold ILP formulation of the q-Majority Illusion problem. Theorem 1. q-Majority Illusion is in FPT when parameterized by the vertex integrity vi(G)vi(G) of the social network G. Proof. Let ℐ=(N,G,q)I=(N,G,q) be an instance of q-Majority Illusion and M be a vi-set for G of size vi(G)=kvi(G)=k. Our algorithm can be divided into two parts. First, we guess how a hypothetical solution labeling f labels the agents of M, and which agents of M are under illusion in f (the latter can be skipped if q=1q=1, as then μf(N)=|N| _f(N)=|N|). Then, for each such possibility, we create an N-fold ILP that verifies whether we can extend the guessed partial labeling of M so that the correct number of agents actually experience majority illusion. We now formally describe the verification phase of the algorithm. Let fMf_M be some labeling of the vertices of M and M′⊆M M be a set of agents of M under majority illusion in a hypothetical solution f (in an actual solution, more agents of M can be under majority illusion, but the program we construct checks this only for agents of M′M ). Let ℋH be the set of connected components of G−MG-M. By definition, each component is of size at most k; therefore, there are at most 2k2^k different labelingsfor every component H∈ℋH . We call each such labeling a configuration of H, and we use HC_H to denote the set of all possible configurations for a component H. Additionally, we denote by μH,C _H,C the number of agents in component H who are under majority illusion if H is in (i.e., labeled by) configuration C∈HC _H, assuming that we use labeling fMf_M for agents in M (recall that fMf_M is known and fixed at this time). Furthermore, we use #H,C\# b_H,C to denote the number of blue agents and #H,C\# r_H,C to denote the number of red agents, respectively, in H when it is in configuration C. Finally, we extend the previous notion and use #H,C(H(v))\# b_H,C(N_H(v)) (#H,C(H(v))\# r_H,C(N_H(v))) to denote the number of blue (red, respectively) neighbors of some agent v∈Mv∈ M in H when H is in configuration C. Then, our N-fold ILP contains a binary variable xH,Cx_H,C for every H∈ℋH and every C∈HC _H. If this variable is set to 11 for some H and C, then, in the corresponding solution, the component H is in configuration C. The program contains four types of constraints. First, we have a single global constraint that ensures that blue is indeed the majority color: ∑H∈ℋ∑C∈HxH,C⋅#H,C>|N|2−#fM(M). _H _C _Hx_H,C·\# b_H,C> |N|2-\# b_f_M(M)\,. (4) Second, we have |M′||M |-many constraints, one for each agent of M′M , which ensure that all agents of M′M are indeed under majority illusion. ∀v∈M′:∑H∈ℋ∑C∈HxH,C⋅#H,C(H(v))>degG(v)2−#fM(M(v)),∀ v∈ M _H _C _Hx_H,C·\# r_H,C(N_H(v))\\ > _G(v)2-\# r_f_M(N_M(v))\,, (5) and for agents of M∖M′M M , we (for technical reasons) require that none of them is under majority illusion. ∀v∈M∖M′:∑H∈ℋ∑C∈HxH,C⋅#H,C(H(v))≤degG(v)2−#fM(M(v)),∀ v∈ M M _H _C _Hx_H,C·\# r_H,C(N_H(v))\\ ≤ _G(v)2-\# r_f_M(N_M(v))\,, (6) Next, we add a single global constraint that ensures that enough agents are under majority illusion. ∑H∈ℋ∑C∈HxH,C⋅μH,C≥⌈q⋅|N|⌉−|M′|. _H _C _Hx_H,C· _H,C≥ q·|N| -|M |\,. (7) Notice that if we remove the previous constraint and instead maximize the left side of the inequality in the objective function, we can easily find an extension of fMf_M with the largest number of agents under majority illusion. However, since we formulate ℐI as a decision problem, we keep the constraint as is and use a constant objective function. Finally, we need to ensure that each component H∈ℋH is in exactly one configuration. This can be secured by adding a single local constraint for each H∈ℋH of the following form. ∀H∈ℋ:∑C∈HxH,C=1.∀ H _C _Hx_H,C=1\,. (8) Now, we prove that it is possible to extend the given labeling fMf_M to a solution f for ℐI such that agents of M′M are under majority illusion if and only if the above N-fold IP is feasible. We start with the left-to-right implication. Claim 1. Let f be an extension of fMf_M so that at least q⋅|N|q·|N| agents, including agents of M′M and excluding agents of M∖M′M M , are under majority illusion. Then, the constructed N-fold ILP admits a feasible solution x. Proof. Without loss of generality, we assume that blue is the predominant color. If not, we can simply swap the color of each agent and obtain another solution. Now, for every component H∈ℋH , we set xH,C=1x_H,C=1 if and only if H is in configuration C according to f. Clearly, for every H, there exists exactly one C such that xH,C=1x_H,C=1, so constraints of type (8) are easily satisfied. Let #f\# b_f denote the number of blue agents according to f. By our assumption, #f>|N|/2\# b_f>|N|/2. Moreover, since f is an extension of fMf_M, it holds that #f−#fM>|N|/2−#fM\# b_f-\# b_f_M>|N|/2-\# b_f_M. Observe that the left part of the inequality corresponds to the number of blue agents in components H1,…,HℓH_1,…,H_ , so we can write it as ∑H∈ℋ#H,f _H \# b_H,f, where #H,f\# b_H,f is the number of agents in H colored blue in f. This is exactly ∑H∈ℋxH,C⋅#H,C=∑H∈ℋ∑C∈HxH,X⋅#H,C, _H x_H,C·\# b_H,C= _H _C _Hx_H,X·\# b_H,C, since exactly one variable xH,Cx_H,C for some fixed component H—the one corresponding to the configuration of H in f—is set to 11. That is, constraint (4) is satisfied. Let v∈M′v∈ M be an agent. By our assumptions, v must be under majority illusion in f. That is, the number of red agents in its neighborhood is greater than degG(v)/2 _G(v)/2. Since f is an extension of fMf_M, the number of red neighbors of v in the components H1,…,HℓH_1,…,H_ is greater than degG(v)/2−#fMv _G(v)/2-\# r^v_f_M. Using an argument similar to that in the previous paragraph, we obtain that constraint (5) is satisfied for v. Since we picked v arbitrarily, all these constraints are necessarily satisfied. Similarly, constraint (6) is satisfied for all v∈M∖M′v∈ M M . Finally, since f is an extension of fMf_M with at least q⋅|N|q·|N| agents under majority illusion, including the agents of M′M and excluding agents of M∖M′M M , there are at least q⋅|N|−|M′|q·|N|-|M | agents within the components H1,…,HℓH_1,…,H_ under illusion. The number of such agents is ∑H∈ℋ∑C∈HxH,C⋅μH,C _H _C _Hx_H,C· _H,C which is an integer at least q⋅|N|−|M′|q·|N|-|M |; therefore constraint (7) is satisfied as well. ◀ Now, we show that each feasible solution x for the N-fold ILP corresponds to a solution extension f of fMf_M. Claim 2. Let x be a feasible solution for the N-fold ILP. Then, there is an extension of f such that at least q⋅|N|q·|N| agents, including agents of M′M and excluding agents of M∖M′M M , are under majority illusion. Proof. Given a feasible solution x, we construct the extension f of fMf_M as follows. For every component H∈ℋH and every vertex v∈V(H)v∈ V(H), we set f(v)=C(v)f(v)=C(v), where C∈HC _H is the unique configuration of H such that xH,C=1x_H,C=1. By constraint (8), this labeling f is well defined, since for each H∈ℋH there is exactly one variable xH,Cx_H,C set to 11. Now, the total number of agents colored blue is #f \# b_f =#fM+∑H∈ℋ#H,f =\# b_f_M+ _H \# b_H,f =#fM+∑H∈ℋ∑c∈HxH,C⋅#H,C>|N|/2 =\# b_f_M+ _H _c _Hx_H,C·\# b_H,C>|N|/2 where #H,f\# b_H,f is again the number of agents in H colored blue in f, and the inequality follows from constraint (4). That is, the blue color is indeed the majority color. What remains to verify is that the correct number of agents, including all agents of M′M , is experiencing a majority illusion. Let v∈M′v∈ M be an agent. If ∑H∈ℋ#H,fv+#fMv≤degG(v)/2 _H \# r^v_H,f+\# r_f_M^v≤ _G(v)/2, then constraint (5) is violated for v, which contradicts that x is a feasible solution. That is, all agents in M′M are indeed under the illusion in f. By the same argument, no agent of M∖M′M M is under majority illusion, as otherwise, constraint (6) is violated. Finally, the number of agents in components of ℋH under illusion can be expressed as ∑H∈ℋμH,f _H _H,f, which is equal to ∑H∈ℋ∑C∈HxH,C⋅μH,C _H _C _Hx_H,C· _H,C. By constraint (7), this is at least q⋅|N|−|M′|q·|N|-|M |. Additionally, all agents of M′M are under the illusion and, therefore, at least q⋅|N|−|M′|+|M′|q·|N|-|M |+|M | are under majority illusion, which finishes the proof. ◀ Let us prove the correctness of the algorithm using Claims˜1 and 2. Our algorithm tries all possible labelings fMf_M over M and, for each, all possible sets M′M ; thus, if there is a solution f for I, then the algorithm checks its restriction to M and, by Claim˜1, returns the correct answer. If there is no solution for I, the N-fold ILP is not feasible for any combination of fMf_M and M′M , so it correctly returns no. For running time, the N-fold ILP contains k+2k+2 global constraints and one constraint that is local for every brick. The largest coefficient in the constraints is also k, so we can solve the previous ILP in time 2(k2logk)⋅n(1)2^O (k^2 k )· n^O (1 ) time, using the algorithm of Eisenbrand et al. (2025). For the guessing part, there are 2(k)2^O (k ) different functions fMf_M and, for each such function, 2(k)2^O (k ) different sets M′M . As we construct the previous N-fold ILP for every pair of possible fMf_M and M′M , we obtain an algorithm running in 2(k)⋅2(k)⋅2(k2logk)⋅n(1)∈2(k2logk)⋅n(1)2^O (k )· 2^O (k )· 2^O (k^2 k )· n^O (1 )∈ 2^O (k^2 k )· n^O (1 ), which is indeed in FPT. Therefore, the theorem follows. ∎ Using the previous algorithm, we also significantly improve the running time for parameterization by the vertex cover number. The best known algorithm so far, due to Grandi et al. (2025), runs in 22(vc(G))|N|(1)2^2^O (vc(G) )|N|^O (1 ) time, i.e., is doubly exponential in the parameter. As vi(G)≤vc(G)+1vi(G) (G)+1, by employing the previous algorithm, we directly obtain the following. Corollary 1. The q-Majority Illusion problem can be solved in 2(vc(G)2logvc(G))⋅n(1)2^O (vc(G)^2 (G) )· n^O (1 ) time. 4 Bounded Feedback Edge Set Recall that the feedback edge set (FES) is a set of edges whose removal turns the social network into a tree. This parameter is particularly appealing because, unlike other parameters we study in this work, it can be computed in polynomial time. FES found use in the design of practical algorithms in various AI applications (Grüttemeier and Komusiewicz 2020; Ganian and Korchemna 2021; Guo et al. 2022). Our FPT algorithm for FES relies on a polynomial-time algorithm for the following auxiliary problem. Definition 1. The input of the Max List Majority Illusion problem is a triple (N,G,L)(N,G,L) where N is a set of agents, G is a social network over N, and L is a function L:N→,,,L N→\\ blue\,\ red\,\ blue, red\\ that satisfies |v∈N:∈L(v)|>|N|/2|\v∈ N: blue∈ L(v)\|>|N|/2. The task is to compute the maximum number of agents under majority illusion over all possible labelings f where • f(v)∈L(v)f(v)∈ L(v) for every v∈Nv∈ N, and • #f(N)>#f(N)\# b_f(N)>\# r_f(N), i.e., blue is the majority color. Observe that due to our condition on L, each instance admits at least one labeling f satisfying the above conditions. We show that if G is a tree, then we can compute the solution for it in polynomial time. Lemma 1. If the social network G is a tree, Max List Majority Illusion is solvable in polynomial time. Proof. We use dynamic programming over the tree G. Let N be the set of agents in G. Consider G as a rooted tree with an arbitrarily chosen agent ρ as its root. For each agent v∈Nv∈ N, let NvN^v denote the set of agents in the subtree of G rooted at v. Moreover, if v≠ρv≠ρ, then we write parent(v)parent(v) for the parent of v, and let children(v)=u∈N:parent(u)=vchildren(v)=\u∈ N:parent(u)=v\. For each agent v∈N∖ρv∈ N \ρ\, we compute a table DPvDP_v containing values DPv[c,cp,B]DP_v[c,c_p,B] where • c∈,c∈\ red, blue\ is the color of agent v, • cp∈,c_p∈\ red, blue\ is the color of p=parent(v)p=parent(v), and • B∈[|N|]B∈[|N|] is the number of agents in NvN^v colored blue. We call triplets of the form (c,cp,B)(c,c_p,B) a signature, and for each signature, the table stores the maximum number of agents in NvN^v that are under majority illusion assuming that v is of color c, p is of color cpc_p, there are exactly B blue agents in the subtree rooted at v, and the color of each agent u∈Nvu∈ N^v is in its corresponding set L(u)L(u). If no such labeling exists, the table stores −∞-∞. If DPv[c,cp,B]≠−∞DP_v[c,c_p,B] =-∞, we say that the signature (c,cp,B)(c,c_p,B) is valid for v. Once the dynamic programming table is correctly computed for all agents, we can compute the solution to our instance as follows. Let u1,…,uγu_1,…,u_γ be an arbitrary but fixed ordering of the children of the root ρ. We return maxcρ∈L(ρ)maxB∈[⌈|N|/2+1⌉,|N|]max∈[B]γ∈,γ∑i=1γBi=B−⟦cρ=⟧ι()+∑i=1γDPui[ci,cρ,Bi] _c_ρ∈ L(ρ) _B∈[ |N|/2+1 ,|N|] x _ subarraycB∈[B]^γ\\ c∈\ red, blue\^γ\\ _i=1^γB_i=B- c_ρ= blue subarray (c)+ _i=1^γDP_u_i[c_i,c_ρ,B_i] (9) where ι is a function that evaluates to 11 if the strict majority of elements of the vector c have the value red, and to 0 otherwise. Moreover, we use ⟦⋅⟧ · as the Iverson bracket; i.e., an expression that evaluates to 11 if the condition inside the brackets is satisfied and to 0 otherwise. Computation. Now, we formally show how to compute the dynamic programming table for each agent v and for every signature (c,cp,B)(c,c_p,B). We distinguish two cases according to the type of agent v under consideration. Leaf Agent. Let v be a leaf agent. Every valid signature must satisfy that the color c is allowed for v, i.e., c∈L(v)c∈ L(v). Moreover, the number B of blue vertices in the subtree is one if and only if the color of c is blue. Otherwise, it must hold that B=0B=0. Once we get rid of all clearly invalid signatures, we have that agent v is under majority illusion if and only if its parent is red. Formally, the computation is as follows: DPv[c,cp,B]=−∞if c∉L(v) or B>1,−∞if c= and B=1,−∞if c= and B=0,1if cp=, and0otherwise.DP_v[c,c_p,B]= cases-∞&if c ∈ L(v) or B>1,\\ -∞&if c= red and B=1,\\ -∞&if c= blue and B=0,\\ 1&if c_p= red, and\\ 0&otherwise. cases (10) Internal Agent. If DPv[c,cp,B]DP_v[c,c_p,B] is such that c∉L(v)c ∈ L(v), we set DPv[c,cp,B]=−∞DP_v[c,c_p,B]=-∞. Otherwise, we find an optimal way how to label the children of v and how to split the remaining blue agents between their respective subtrees. Let children(v)=u1,…,uγchildren(v)=\u_1,…,u_γ\. The computation is as follows. DPv[c,cp,B]=max∈[B]γ∈,γ∑i=1γBi=B−⟦c=⟧ι(cp,)+∑i=1γDPui[ci,c,Bi].DP_v[c,c_p,B]= _ subarraycB∈[B]^γ\\ c∈\ blue, red\^γ\\ _i=1^γB_i=B- c= blue subarray (c_p,c)+Σ _i=1^γDP_u_i[c_i,c,B_i]\,. (11) Correctness. We show that, indeed, each dynamic programming table is computed correctly. Claim 3. Whenever DPv[c,cp,B]=wDP_v[c,c_p,B]=w and w≠−∞w =-∞, there exists a labeling f:Nv→,f N^v→\ blue, red\ such that f(v)=cf(v)=c, #f(Nv)=B\# b_f(N^v)=B, f(u)∈L(u)f(u)∈ L(u) for every u∈Nvu∈ N^v, and, assuming the color of parent(v)parent(v) is cpc_p, the number of agents under majority illusion in NvN^v is exactly w. Proof. We prove the claim by bottom-up induction over the agents in the tree. Let v be a leaf agent that admits a valid signature, so that DPv[c,cp,B]=w≠−∞DP_v[c,c_p,B]=w≠-∞. By our computation in (10), w∈0,1w∈\0,1\. We define f by setting f(v)=cf(v)=c and f(vp)=cpf(v_p)=c_p. Clearly, c∈L(v)c∈ L(v), as otherwise we would have w=−∞w=-∞ by the first condition in (10). If c=c= red, then B=0=#f(Nv)B=0=\# b_f(N^v), and if c=c= blue, then B=1=#f(Nv)B=1=\# b_f(N^v). Finally, the number of agents in NvN^v under the illusion with majority-red neighborhood, by f(vp)=cpf(v_p)=c_p is 11 if and only if cp=c_p= red. Thus, f has the desired properties. Assume now that v is an internal agent and the claim holds for all its children; let u1,…,uγu_1,…,u_γ denote them. Let c and B be the vectors where the right-hand side of (11) takes its maximum. Since DPv(c,cp,B)≠−∞DP_v(c,c_p,B)≠-∞, we know that for each i∈[γ]i∈[γ], the signature (ci,c,Bi)(c_i,c,B_i) is valid for uiu_i. for each i∈[γ]i∈[γ], let fif_i be the labeling for Nui∪vN^u_i∪\v\ guaranteed by the inductive hypothesis. We define f by taking the union of f1,…,fγf_1,…,f_γ (note that fi(vp)=cpf_i(v_p)=c_p for each i∈[γ]i∈[γ], so f is well-defined. Using again the inductive hypothesis, the number of blue agents under f in NvN^v is exactly (∑i=1γBi)+⟦c=⟧( _i=1^γB_i)+ c= blue , and we also have f(u)∈L(u)f(u)∈ L(u) for all agents u∈Nvu∈ N^v, using also that c∈L(v)c∈ L(v) holds as otherwise we would have w=−∞w=-∞. Finally, the number of agents under majority illusion in NuiN^u_i is DPui(ci,c,Bi)DP_u_i(c_i,c,B_i) for each i∈[γ]i∈[γ] by induction; hence, by the definition of ι , the right-hand side of (11) correctly computes the number of agents with a majority-red neighborhood in NvN^v under f. ◀ Next, we show that the value stored for each signature is indeed the maximum possible number of agents under illusion. Claim 4. If a labeling f:Nv∪vp→,f N^v∪\v_p\→\ blue, red\ exist such that f(v)=cf(v)=c, f(vp)=cpf(v_p)=c_p, #f(Nv)=B\# b_f(N^v)=B, and f(u)∈L(u)f(u)∈ L(u) for every u∈Nvu∈ N^v, then DPv[c,cp,B]≥μ^f(Nv)DP_v[c,c_p,B]≥ μ_f(N^v). Proof. Again, we use bottom-up induction over the agents of the tree. First, let v be a leaf agent and f be a labeling corresponding to a signature (c,cp,B)(c,c_p,B). By the assumptions on f, it must hold that DPv[c,cp,B]∈0,1DP_v[c,c_p,B]∈\0,1\. Moreover, DPv[c,cp,B]=1DP_v[c,c_p,B]=1 if and only if cp=c_p= blue, showing that the claim is indeed satisfied for leaf agents. Now, let v be an internal agent and assume that the claim holds for all children u∈children(v)=u1,…,uγu (v)=\u_1,…,u_γ\. Let fif_i be a restriction of f to Nu∪vN^u∪\v\ for a child uiu_i of v. Clearly, fif_i corresponds to a signature (f(u),f(v),#f(Nu))(f(u),f(v),\# b_f(N^u)) in DPuDP_u and, by the induction hypothesis, DPu[f(u),f(v),#f(Nu)]≥μ^fu(Nu).DP_u[f(u),f(v),\# b_f(N^u)]≥ μ_f^u(N^u). By (11), the value stored in DPv[c,cp,B]DP_v[c,c_p,B] is at least ∑i=1γ _i=1^γ DPui[f(ui),f(v),#f(Nui)]+ι(cp,(f(ui))i∈[γ]) _u_i[f(u_i),f(v),\# b_f(N^u_i)]+ (c_p,(f(u_i))_i∈[γ]) ≥∑i=1γμ^fi(Nui)+ι(cp,(f(ui))i∈[γ])≥μ^f(Nv), ≥ _i=1^γ μ_f_i(N^u_i)+ (c_p,(f(u_i))_i∈[γ])≥ μ_f(N^v), as desired. ◀ Next, we show that the computation of the final output as formulated in (9) is also correct, which leads to the correctness of our approach. According to Claims˜3 and 4, the dynamic programming table is correctly computed for all children u∈children(ρ)u (ρ). Recall also that there is at least one labeling for G as required and thus an optimal such labeling f always exists. Note that (9) checks the combination of c=f(ρ)c=f(ρ), B=#f(Nρ)B=\# b_f(N^ρ), =(#f(Nu))u∈children(ρ)B=(\# b_f(N^u))_u (ρ), =(f(u))u∈children(ρ)c=(f(u))_u (ρ), and, as the dynamic tables are computed correctly, the algorithm returns value of at least μ^f(N) μ_f(N) which, as the majority color by B=#f(N)>|N|/2B=\# r_f(N)>|N|/2 is blue, equals μf(N) _f(N). Running Time. The computation in a leaf agent can be done in constant time by simply checking all conditions. To compute a cell’s value for an internal agent (as well as the final result in (9)), we use simple dynamic programming, which runs in (|N|3)O (|N|^3 ) time. In particular, the dynamic programming table used within an internal agent v is T[i,ρ,β] T[i,ρ,β], where i is the currently processed child of v, ρ is the number of children in ui,…,uγ\u_i,…,u_γ\ colored red, and β is the number of agents of Tui,…,TuγT_u_i,…,T_u_γ we need to color blue. The stored value is the maximum number of agents under majority illusion in subtrees Tui,…,TuγT_u_i,…,T_u_γ, assuming that v is of color c, exactly ρ roots of these subtrees are colored red, and there are exactly β blue agents in these subtrees. The size of the table is at most n⋅γ⋅n·γ· n, and each cell can be computed in time (|Tui|)O (|T_u_i| ) by a) trying to color uiu_i in color ci∈L(ui)c_i∈ L(u_i), b) guessing the number of blue agents BiB_i in the respective subtree TuiT_u_i, and c) looking up the optimal solution for i+1i+1 with the parameters ρ and β appropriately modified (this is already stored in T[i+1,⋅,⋅] T[i+1,·,·]). Moreover, for each pair of cic_i and BiB_i, we already have the partial solution computed in table DPuiDP_u_i. Observe that overall, the computation can be done in (|N|2⋅γ⋅|N|)O (|N|^2·γ·|N| ) time. However, as γ∈(|N|)γ∈O (|N| ), the overall running time of the above approach is (|N|4)O (|N|^4 ). With a more careful analysis based on the fact that ∑i∈[γ]|Ti|=(|N|) _i∈[γ]|T_i|=O (|N| ), we can implement the DP in (|N|3)O (|N|^3 ) time. We have (|N|)O (|N| ) tables with (|N|)O (|N| ) signatures for each table, giving us the overall running time of (|N|5)O (|N|^5 ). ∎ Finally, we are ready to give our algorithm for q-Majority Illusion. Given a feedback edge set M, the high-level idea is to guess the labeling of agents adjacent to edges of M, then perform local replacement of these edges with small gadgets that turn the social network into a prelabeled tree, and find an optimal extension of such a labeling using the algorithm from Lemma˜1. Theorem 2. q-Majority Illusion is in FPT when parameterized by the feedback edge set number fes(G)fes(G) of the social network G. Proof. Let (N,G,q)(N,G,q) be our input instance. We assume w.l.o.g. that G is connected. Let M be a feedback edge set of G of size fes(G)fes(G). Let P denote the set of agents that are adjacent to some edge in M; then |P|≤2|M||P|≤ 2|M|. Let f be a labeling of G with blue as the majority color that maximizes the number μf(N) _f(N) of agents under illusion in G. First, for each v∈Pv∈ P, we guess its label in f. Second, we construct a new social network T that will be a tree by deleting all edges of M in G, and then adding for each v∈Pv∈ P exactly |v,u∈M:f(u)=||\\v,u\∈ M:f(u)= blue\| blue and exactly |v,u∈M:f(u)=||\\v,u\∈ M:f(u)= red\| red pendant leaves. Then, to each of these 2|M|2|M| newly added agents, we add a pendant leaf having the opposite color. This way, we have added exactly 2|M|2|M| red and exactly 2|M|2|M| blue agents to N; let A denote the set of these 4|M|4|M| auxiliary agents. We set L(v)=f(v)L(v)=\f(v)\ for each v∈Pv∈ P, set L(a)=cL(a)=\c\ for each a∈Aa∈ A having color c, and set L(v)=,L(v)=\ red, blue\ for all agents v∈N∖Pv∈ N P. Notice that for any labeling f′f of G that coincides with f on P, each agent v∈Pv∈ P is under majority illusion in G if and only if it is under majority illusion in the corresponding labeling fT′f _T of T that coincides with f′f on N and satisfies fT′(a)∈L(a)f _T(a)∈ L(a) for each a∈Aa∈ A. Moreover, such a labeling f′f has blue as its majority color if and only if fT′f _T has blue as the majority color. Next, we solve the Max List Majority Illusion problem on (N∪A,T,L)(N∪ A,T,L) using the algorithm from Lemma˜1. Let μT _T be the returned solution value. Finally, we compute the answer to our instance as follows. Let μA _A denote the number of agents in A under majority illusion under our labeling of P∪AP∪ A. By our previous arguments and the correctness of Lemma˜1, the maximum number of agents under majority illusion under any labeling with majority color blue that coincides with f on P is exactly μT−μA _T- _A. Hence, we return yes if μT−μA≥q|N| _T- _A≥ q|N| and no otherwise. The algorithm runs in 2(fes(G))⋅|N|(1)2^O (fes(G) )·|N|^O (1 ) time. ∎ 5 Bounded Distance to Disjoint Stars Let us now show that q-Majority Illusion is intractable even if the social network G is close to being a collection of disjoint stars. To show the W[1]-hardness of 11-Majority Illusion when parameterized by dds(G)dds(G), we provide a reduction from the following variant of Multidimensional Subset Sum: given an integer d and a set S of n vectors in ℕdN^d, the task is to decide if there exists a subset ′⊆S with ∑∈′=∑∈∖′ _s s= _s s and |′|=||/2|S |=|S|/2. We call this the Multidimensional Halfset Sum problem. Lemma 2. Multidimensional Halfset Sum encoded in unary is W[1]-hard with respect to the dimension. Proof. We give a reduction from Multidimensional Subset Sum; let I=(d,,)I=(d,S,t) of with =1,…,nS=\s_1,…,s_n\ be our input instance. We first append the value i to each vector is_i (increasing the dimension by one) and add n new vectors 1′,…,n′s _1,…,s _n where i′=(0,…,0,i)∈d+1s _i=(0,…,0,i) ^d+1 for each i∈[n]i∈[n]. We further add the two vectors (,n2)(t,n^2) and (Σ−,n2)(s_ -t,n^2) where Σ=∑∈s_ = _s . Note that the total sum of the vectors in the constructed instance (d+1,′)(d+1,S ) of Multidimensional Halfset Sum adds up to (2Σ,2n2+2(n2))(2s_ ,2n^2+2 n2). It is straightforward to check that a solution X for I implies that there are n+1n+1 vectors in ′S that sum up to (Σ,n2+(n2))(s_ ,n^2+ n2) can be extended to a solution in the constructed instance by adding those vectors i′s _i for which i∉Xs_i∉ X together with the vector (Σ−,n2)(s_ -t,n^2). Conversely, any solution to the constructed instance partitions the vectors in ′S into two sets of size n+1n+1 with one of them, say X′X , containing the vector (Σ−,n2)(s_ -t,n^2). Then the remaining n vectors in X′X must add up to (,(n2))(t, n2) which yields that i:(i,i)∈X′\s_i:(s_i,i)∈ X \ is a solution for I. ∎ Now, we are ready to prove the main result of this section. Theorem 3. q-Majority Illusion is W[1]-hard when parameterized by the distance to disjoint stars dds(G)dds(G) of the social network G. Proof. We give a reduction from Multidimensional Halfset Sum, which is W[1]-hard as shown in Lemma˜2, using similar ideas as in the reduction proving Theorem˜9. Let I=(d,)I=(d,S) be our input with =1,…,nS=\s_1,…,s_n\; we will use the notation Σ=∑i∈[n]s_ = _i∈[n]S. We may clearly assume that n≥2n≥ 2, and also that d≥2d≥ 2, as otherwise we can just append an additional coordinate with value 11 to each vector in S. We may further assume that Σ[j]≥3s_ [j]≥ 3 for each j∈[d]j∈[d], as otherwise we can multiply all vectors by three; this ensures the required condition unless Σ[j]=0s_ [j]=0 in which case we can ignore the jthj^th coordinates. We create an instance J=(N,G,q)J=(N,G,q) of q-Majority Illusion as follows. Construction. Let =Σ/2t=s_ /2 denote our target vector. We define β=maxj∈[d]Σ[j]β= _j∈[d]s_ [j] and α=n2(dβ+1)−n−d−1α= n2(dβ+1)-n-d-1. First, for each i∈[α]i∈[α], we create a pair (ai,ai′)(a_i,a _i) of agents connected by an edge in G; let A=a1,…,ad,a1′,…,aα′A=\a_1,…,a_d,a _1,…,a _α\. Next, for each i∈[n]i∈[n] we create a star with center agent cic_i and a set LiL_i of 2dβ+12dβ+1 leaves with Li=Li′∪⋃j∈[d](Lij∪L¯ij)∪ℓi0L_i=L _i∪ _j∈[d](L_i^j∪ L_i^j)∪\ _i^0\ where |Li′|=dβ|L _i|=dβ, and |Lij|=i[j]|L_i^j|=s_i[j] and |L¯ij|=β−i[j]| L_i^j|=β-s_i[j] for each j∈[d]j∈[d]. Let C denote the set of all central agents. Additionally, we create a set M=m1,…,md,m¯1,…,m¯dM=\m_1,…,m_d, m_1,…, m_d\ of modulator agents. For each j∈[d]j∈[d] we connect agent mjm_j to all agents in ⋃i∈[n]Lij _i∈[n]L_i^j as well as to aja_j, and we connect m¯j m_j to all agents in ⋃i∈[n]L¯ij _i∈[n] L_i^j as well as to aj′a _j. This finishes our definition of the social network G over agent set N; note that the number of agents is |N|=2α+n(2dβ+2)+2d|N|=2α+n(2dβ+2)+2d. We set the value of q such that qN=|N|−n/2qN=|N|-n/2. Removing all modulator agents from G leaves a collection of disjoint stars; hence, dds(G)≤|M|=2ddds(G)≤|M|=2d, so the presented reduction is a parameterized one. We now show that I is a yes-instance of Multidimensional Halfset Sum if and only if J is a yes-instance of q-Majority Illusion. Correctness. Let us first assume that there exists a red—blue labeling f for G with majority color blue where at least q|N|q|N| agents are under majority illusion; let us choose f such that it maximizes the number of agents under majority illusion and, subject to that, maximizes the number or red agents in A. We can assume that #f(N)=|N|2−1=α+n(dβ+1)+d−1=2α+n2(dβ+1)+n+2d, split\# r_f(N)&= |N|2-1=α+n(dβ+1)+d-1\\ &=2α+ n2(dβ+1)+n+2d, split (12) as otherwise we can simply re-label some blue vertices as red as long as we keep blue the majority color. First note that each center vertex is red under f. Indeed, since all agents except for center and modulator agents have at most two neighbors in G, by #f(N)>n+d\# r_f(N)>n+d we know that if some center agent cic_i is not red, then we can modify f by re-labeling cic_i as red and, if necessary, setting some agent in N∖(C∪M)N (C∪ M) as blue; this way, the number of agents under majority illusion in LiL_i increases by at least |Li′∪ℓi0|=dβ+1≥3|L _i∪\ _i^0\|=dβ+1≥ 3 while at most two agents may cease being under illusion; a contradiction to our choice of f. We can apply an analogous reasoning for modulator agents: since all center agents are red, re-labeling some modulator agent mjm_j, j∈[d]j∈[d] as red increases the number of agents under majority illusion by ∑i∈[n]|Lij|=Σ[j] _i∈[n]|L_i^j|=s_ [j]; similarly, re-labeling agent m¯j m_j as red increases this number by ∑i∈[n]|L¯ij|=nβ−Σ[j] _i∈[n]| L_i^j|=nβ-s_ [j], both of which values are at least 33 by our initial assumptions; hence, the above arguments show that all modulator agents are red. We next show that each agent in A is red. On the one hand, re-labeling a blue agent in A as red increases the number of agents under majority illusion in A by exactly one (recall that all modulator agents are red). On the other hand, some center agent cic_i must be under majority illusion by q|N|>|N|−|C|q|N|>|N|-|C|; it follows that cic_i must have a red neighbor ℓ in LiL_i not adjacent to any modulator agent. Hence, we can re-label ℓ as blue (destroying the illusion only for cic_i) to compensate for re-labeling some agent in A as red, without decreasing the number of agents under majority illusion. This contradicts our choice of f, proving that all agents in A are red. Notice now that since all agents in M∪C∪AM∪ C∪ A are red, from (12) we get #f(L)=n2(dβ+1).\# r_f(L)= n2(dβ+1). (13) Since each center agent needs at least dβ+1dβ+1 red agents in LiL_i to be under majority illusion, and at least n2 n2 center agents must be under majority illusion by q|N|=|N|−n2q|N|=|N|- n2, it follows that there must be exactly n2 n2 center agents under majority illusion, each of them having exactly dβ+1dβ+1 red neighbors. Moreover, using again q|N|=|N|−n2q|N|=|N|- n2, we obtain that all modulator agents must be under majority illusion as well. Define ′=i:i∈[n],ciS =\s_i:i∈[n],c_i is under majority illusion\; then we know |′|=||/2|S |=|S|/2. Since each modulator agent mjm_j for some j∈[d]j∈[d] has one red neighbor in A, it needs at least [j]t[j] red neighbors from ⋃i∈[n]Lij _i∈[n]L_i^j as otherwise it would not be under majority illusion by #f(NG(mj))≤[j]=Σ[j]−[j]<#f(NG(mj)).\# r_f(N_G(m_j)) [j]=s_ [j]-t[j]<\# b_f(N_G(m_j)). This yields ∑∈′[j]≥[j]for each j∈[d]. _s s[j] [j] each $j∈[d]$. (14) Similarly, since each modulator agent m¯j m_j for some j∈[d]j∈[d] has one red neighbor in A, it needs at least n2β−[j] n2β-t[j] red neighbors from ⋃i∈[n]L¯ij _i∈[n] L_i^j as otherwise it would not be under majority illusion by #f(NG(m¯j)) \# r_f(N_G( m_j)) <n2β−[j] < n2β-t[j] =n2β−(Σ[j]−[j])≤#f(NG(m¯j)). = n2β-(s_ [j]-t[j])≤\# b_f(N_G( m_j)). This yields ∑∈′[j]≤[j]for each j∈[d]. _s s[j] [j] each j∈[d]. which, together with (14) yields that ∑∈′= _s s=t, proving that ′S is a solution for I. For the other direction, assume now that I admits a solution ′S . We create a red–blue labeling f for G as follows. We create all agents in C∪M∪AC∪ M∪ A red, as well as the agents in Li∖Li′L_i L _i for each i∈[n]i∈[n] where i∈′s_i . The number of red agents thus satisfies (12), so the majority color in f is blue. It is clear that all agents in A∪L∪ci:i∈′A∪ L∪\c_i:s_i \ are under majority illusion. We show that all modular agents are under majority illusion as well. First, each agent mjm_j for some j∈[d]j∈[d] has exactly 1+∑∈′[j]=1+[j]1+ _s s[j]=1+t[j] red neighbors and exactly ∑∈∖′[j]=[j] _s s[j]=t[j] blue neighbors. Second, each agent m¯j m_j for some j∈[d]j∈[d] has exactly 1+n2β−∑∈′[j]=1+n2β−[j]1+ n2β- _s s[j]=1+ n2β-t[j] red neighbors and exactly n2β−∑∈∖′[j]=n2β−[j] n2β- _s s[j]= n2β-t[j] blue neighbors. Thus, all modulator agents are under majority illusion, implying that all agents except for the n2 n2 center agents in ci:i∈∖′\c_i:s_i \ are under majority illusion. This proves that J is a yes-instance of q-Majority Illusion. ∎ The strength of this intractability result is demonstrated by its consequences on other prominent graph parameters: Corollary 2. q-Majority Illusion is W[1]-hard when parameterized by the combination of the following parametersof the social network G: • the feedback vertex set number fvs(G)fvs(G), • the 44-path vertex cover number 4pvc(G)4pvc(G), and • the treedepth td(G)td(G). A reduction from the Capacitated Vertex Cover problem, proved by Dom et al. (2008) to be W[1]-hard when parameterized by treedepth, shows that even the case q=1q=1 remains intractable when parameterized by treedepth: Theorem 4. 11-Majority Illusion is W[1]-hard parameterized by the treedepth td(G)td(G) of the social network G. Proof. We present a parameterized reduction from Capacitated Vertex Cover which is W[1]-hard when parameterized by the treedepth of the input graph (Dom et al. 2008). Let (H,c,k)(H,c,k) be our input instance; we assume w.l.o.g. that |V|≥2k+2|V|≥ 2k+2. We are going to construct an instance (N,G,1)(N,G,1) of q-Majority Illusion. Construction. We are going to create a vertex gadget for each v∈Vv∈ V, an edge gadget for each e∈Ee∈ E, and a single counting gadget. Our social network will consist of the disjoint union of these gadgets, with some additional inter-gadget edges running between them. We start by introducing a general structure called an (v,ℓr,ℓb)(v, _r, _b)-cap that will be used in all vertex gadgets as well as in the counting gadget. Here, v is an agent, and ℓr _r and ℓb _b are non-negative integers. An (v,ℓr,ℓb)(v, _r, _b)-cap Q is defined over an agent set v∪AQ\v\∪ A_Q where AQ A_Q =(⋃i∈[ℓr]AQ,i)∪(⋃i∈[ℓb]∪BQ,i) = ( _i∈[ _r]A_Q,i )∪ ( _i∈[ _b]∪ B_Q,i ) AQ,i A_Q,i =ai,j,ai,j′:j∈[4] =\a_i,j,a _i,j:j∈[4]\ BQ,i B_Q,i =bi,j,bi,j′:j∈[4] =\b_i,j,b _i,j:j∈[4]\ Figure 3: Illustration of a (v,ℓr,ℓb)(v, _r, _b)-cap. The social networks formed by the agents in AQ,iA_Q,i are the same for each i∈[ℓr]i∈[ _r], and similarly for the social networks formed by the agents in BQ,iB_Q,i for all i∈[ℓb]i∈[ _b]; see Figure˜3 for an illustration. Formally, for each i∈[ℓr]i∈[ _r], agents ai,ja_i,j for j∈[4]j∈[4] form a clique, and ai,j′a _i,j is connected to ai,ja_i,j for each j∈[4]j∈[4]. Similarly, for each i∈[ℓb]i∈[ _b], agents bi,jb_i,j for j∈[4]j∈[4] form a clique, and bi,j′b _i,j is connected to bi,jb_i,j for each j∈[4]j∈[4]. We further connect agent bi,1′b _i,1 to bi,2b_i,2, and agent bi,2′b _i,2 to bi,1b_i,1 for each i∈[ℓr]i∈[ _r]. Finally, we connect agent a to ai,1a_i,1 for each i∈[ℓr]i∈[ _r] and and to bi,1′b _i,1 for each i∈[ℓb]i∈[ _b]. The key property of a (v,ℓ,ℓ′)(v, , )-cap is stated in the next claim. Claim 5. Let Q be an (v,ℓr,ℓb)(v, _r, _b)-cap with a red–blue labeling f. If all agents in Q other than v have more red than blue neighbors, then #f(A(Q)∖v) \# r_f(A(Q) \v\) ≥#f(A(Q)∖v) ≥\# b_f(A(Q) \v\) (15) #f(NQ(v)) \# r_f(N_Q(v)) ≥ℓr; ≥ _r; (16) #f(NQ(v)) \# b_f(N_Q(v)) ≤ℓb. ≤ _b. (17) Equality for (15) implies equality in (16) and (17). Moreover, B admits red–blue labelings f and f′f with f(v)=f(v)= blue but f′(v)=f (v)= red that both satisfy (15)–(17) with equalities. Proof. Consider some index i. Since each agent ai,j′a _i,j for j∈2,3,4j∈\2,3,4\ and each agent bi′b _i for j∈[4]j∈[4] has at most two neighbors in Q, those neighbors must be red. Thus, all agents in ai,j,bi,j:j∈[4]\a_i,j,b_i,j:j∈[4]\ are red under f. As the number of such agents is 4(ℓr+ℓb)4( _r+ _b), and the total number of agents in Q not counting v is 8(ℓr+ℓb)8( _r+ _b), statements (15)–(17) follow. Assuming that the number of red and blue agents is equal, we get that all remaining agents must be blue. In particular, v has ℓr _r red neighbors (namely, a1,1,…,aℓr,1a_1,1,…,a_ _r,1) and ℓb _b blue ones (namely, b1,1′,…,bℓb,1′b _1,1,…,b _ _b,1). Finally, observe that such a labeling indeed ensures that all agents have more red than blue neighbors, irrespective of the labeling of v, implying the last statement of the claim. ◀ Now, the vertex gadget GvG_v for some vertex v∈Vv∈ V, which is simply a (v,c(v)+2,degH(v)−c(v))(v,c(v)+2, _H(v)-c(v))-cap over a set AvA_v of agents where degH(v) _H(v) is the degree of v in H. The edge gadget GeG_e for some edge e=u,v∈Ee=\u,v\∈ E is defined over agent set Ae=Ze∪WeA_e=Z_e∪ W_e where Ze Z_e =zix,e,ziv,e:i∈[4],x∈u,v and =\z_i^x,e,z_i^v,e:i∈[4],x∈\u,v\\ and We W_e =w4x,e,w2,3x,e,w3,4x,e:x∈u,v. =\w^x,e_4,w^x,e_2,3,w^x,e_3,4:x∈\u,v\\. Figure 4: Illustration of an edge-gadget GeG_e for e=u,ve=\u,v\. Inter-gadget connections are shown with dashed lines. Agents in ZeZ_e, WeW_e, and those outside GeG_e are shown as black, white, and gray circles, respectively. The social gadget underlying GeG_e is depicted in Figure˜4; the construction is symmetric for the two endpoint of e. Formally, we define the connections within GeG_e by connecting z2v,ez_2^v,e to agents z1v,ez_1^v,e, z1u,ez_1^u,e, w2,3v,ew^v,e_2,3, z2u,ez_2^u,e, and z3u,ez_3^u,e, connecting z3v,ez_3^v,e to agents z1v,ez_1^v,e, z4v,ez_4^v,e, w2,3v,ew^v,e_2,3, w3,4v,ew^v,e_3,4, z2u,ez_2^u,e, and z4u,ez_4^u,e, and additionally connecting z4v,ez_4^v,e to agents w4v,ew^v,e_4, w3,4v,ew^v,e_3,4 and z4u,ez_4^u,e. Finally, we make the construction symmetric by adding the analogous edges after switching the roles of u and v. Next, we define the counting gadget Ga⋆G_a that is based on an (a⋆,|V|−k+1,k)(a ,|V|-k+1,k)-cap for a newly introduced agent a⋆a over agent set Qa⋆Q_a , and additionally contains a set Ka⋆K_a of |V|−2k|V|-2k agents whose underlying social network is a collection of cliques of size 22 and 33. We finish the construction by defining all inter-gadget edges as follows: for each vertex v∈Vv∈ V, we connect agent v with agents z1v,ez_1^v,e ,z3v,ez_3^v,e, and w3,4v,ew^v,e_3,4 for all edges e∈Ee∈ E incident to v in H. Furthermore, we connect agent a⋆a in the counting gadget to each agent v for v∈Vv∈ V. Note that G can be computed in polynomial time. The next claim shows that the presented reduction is in fact a parameterized one in the sense that td(G)td(G) is a function of td(H)td(H). Claim 6. The constructed social network G has treedepth at most 9td2(H))9td^2(H)). Proof. We show how to construct a treedepth decomposition for G of the claimed depth, using a treedepth decomposition HT_H of depth td(H)td(H) for H. First, it is straightforward to check that for each v∈Vv∈ V, deleting agent v from the vertex gadget GvG_v leaves us with a social network with treedepth at most 55. Hence, GvG_v admits a treedepth decomposition of depth at most 66 with v as its root. Similarly, the counting gadget also admits a treedepth decomposition cT_c of depth 66 with a⋆a as its root. It is also easy to verify that for each edge e∈Ee∈ E connecting vertices u and v in H, the social network induced by the edge-gadget GeG_e and the two agents u and v admits a treedepth decomposition eT_e of depth 1010 whose root is u with v as its only child. We now show how to compute a treedepth decomposition for G based on HT_H. We start by setting :=HT:=T_H, and proceed as follows. • We add cT_c to T by setting a⋆a as the new root and adding the root of T as a child of a⋆a (besides all its children in cT_c). • For each v∈Vv∈ V, we add vT_v to T by identifying the root of vT_v with the node v in T. • We iteratively apply the following operation for each e∈Ee∈ E. Let u and v be the endpoints of e such that v is a descendant of u. We delete u from eT_e so that v is the root of the obtained tree e−uT_e-u, and then add e−uT_e-u by identifying the vertex v within T with the root of e−uT_e-u, and re-position each child of v within T as the child of some (arbitrarily chosen) leaf of e−uT_e-u. Note that u becomes an ascendant of all vertices of GeG_e within T, and moreover, all vertices that were descendants (ascendents) of v before the operation remain descendants (ascendents, respectively) of v afterwards. It is easy to see that the above procedure yields a treedepth decomposition for H. To see that it has the claimed depth of 9td2(H)9td^2(H), first observe that the operations involving the counting gadget and the vertex gadgets increase the depth of T by at most 55. Second, note that the number of times when the agents within some edge-gadget need to be added right under some vertex v is not more than the number of its ascendants in H, i.e., at most td(H)td(H). Since each such operation adds 88 to the depth of T, the incurred total increase in depth is at most 8td(H)8td(H) for these additions at v. Summing such increases up for each vertex and recalling the depth td(H)td(H) of HT_H, we obtain that the obtained treedepth decomposition indeed has depth not more than 9td2(H)9td^2(H). ◀ Correctness. It remains to show that (H,c,k)(H,c,k) is a yes-instance of Capacitated Vertex Cover if and only if (N,G,1)(N,G,1) is a yes-instance of q-Majority Illusion. Suppose first that G admits a red–blue labeling f which ensures that all agents are under majority illusion. We use the following claim about edge gadgets. Claim 7. Let u,v=e∈E\u,v\=e∈ E. If all agents in GeG_e have more red than blue neighbors under f, then #f(Ae)≥#f(Ae)\# r_f(A_e)≥\# b_f(A_e) (18) and equality may only happen if (i) exactly one of z1v,ez_1^v,e and z1u,ez_1^u,e is blue and (i) f(z1v,e)=f(z_1^v,e)= blue implies f(v)=f(v)= red whereas f(z1u,e)=f(z_1^u,e)= blue implies f(u)=f(u)= red; (i) both u and v have one red and one blue neighbor within GeG_e that is not in z1v,e,z1u,e\z_1^v,e,z_1^u,e\. Conversely, if we fix at least one of u and v as red, then agents in GeG_e can be labeled such that (18) and (i)–(i) hold, and each agent in GeG_e has more red than blue neighbors. Proof. First note that all four agents in We∖w3,4u,e,w3,4v,eW_e \w^u,e_3,4,w^v,e_3,4\ have at most two neighbors in G; hence, all their neighbors must be red. This means that agents Ze∖z1u,e,z1v,eZ_e \z_1^u,e,z_1^v,e\ are red. It is not possible that all remaining eight agents of GeG_e are blue, as that would yield more blue than red neighbors for z2v,ez_2^v,e and z2u,ez_2^u,e. Hence, there are at least 77 red agents, implying (18). If (18) holds with equality, then there must be exactly one additional red agent in GeG_e, which means that exactly one common neighbor of z2v,ez_2^v,e and z2u,ez_2^u,e must be red: either z1v,3z_1^v,3 or z1u,ez_1^u,e. Hence, (i) and (i) hold. If z1v,3z_1^v,3 is red, then z1u,ez_1^u,e is blue, and thus inspecting the neighborhood of z3u,ez_3^u,e we obtain that u must be red. Similarly, if z1v,ez_1^v,e is blue, then v must be red. This proves (i). Finally, assume w.l.o.g. that we label v red. Then it is easy to verify that setting all six agents in WeW_e as well as z1v,ez_1^v,e blue and all other agents red yields a labeling with the required properties. ◀ Let S=v∈V:f(v)=S=\v∈ V:f(v)= red\; we are going to prove that S is a capacitated vertex cover of H. First, we show the following. Claim 8. We have |S|=#f(V)≤k|S|=\# r_f(V)≤ k. Moreover, #f(Av∖v)=#f(Av∖v) \# r_f(A_v \v\)=\# b_f(A_v \v\) (19) for each v∈Vv∈ V, and (18) holds with equality for each e∈Ee∈ E. Proof. First note that all agents in Ka⋆K_a must be red, as each of them has at most two neighbors, and thus all these neighbors must be red. Second, consider the set of neighbors of a⋆a within the counting gadget Ga⋆G_a ; note that these are all agents in Qa⋆Q_a . Applying the first statement of Claim˜5 for the (a⋆,|V|−k+1,k)(a ,|V|-k+1,k)-cap over Qa⋆Q_a , we obtain that a⋆a has at least |V|−k+1|V|-k+1 red and at most k blue neighbors within Qa⋆Q_a . Hence, we can define a non-negative Δ∈ℕ for which #f(NG(a⋆))∩Qa⋆=|V|−k+1+Δ and#f(NG(a⋆))∩Qa⋆=k−Δ. split\# r_f(N_G(a ))∩ Q_a &=|V|-k+1+ and\\ \# b_f(N_G(a ))∩ Q_a &=k- . split (20) By the arguments in the proof of Claim˜5, we also get #f(Qa⋆∖a⋆)≥|Qa⋆|−1)/2+Δand#f(Qa⋆∖a⋆)≤(|Qa⋆|−1)/2−Δ split\# r_f(Q_a \a \)&≥|Q_a |-1)/2+ and\\ \# b_f(Q_a \a \)&≤(|Q_a |-1)/2- split (21) Recall now that the set of neighbors of a⋆a outside the counting gadget is V, and the red agents among these are those in S. Thus, from (20) we obtain #f(NG(a⋆))=|V|−k+1+Δ+|S| and#f(NG(a⋆))=k−Δ+|V|−|S|. split\# r_f(N_G(a ))&=|V|-k+1+ +|S| and\\ \# b_f(N_G(a ))&=k- +|V|-|S|. split (22) Since a⋆a is under majority illusion, we get #f(NG(a⋆)) \# r_f(N_G(a )) >#f(NG(a⋆)) >\# b_f(N_G(a )) |V|−k+1+Δ+|S| |V|-k+1+ +|S| >k−Δ+|V|−|S| >k- +|V|-|S| 2|S|+2Δ+1 2|S|+2 +1 >2k >2k |S|+|Δ| |S|+| | ≥k. ≥ k. (23) Let N′N denote the set of agents contained in some vertex- or edge-gadget. Claim˜5 implies that #f(Av∖v)≥#f(Av∖v)\# r_f(A_v \v\)≥\# b_f(A_v \v\) holds for each v∈Vv∈ V. Summing up the above inequalities for each v∈Vv∈ V and (18) for each e∈Ee∈ E, we get that N′N contains at least as many red as blue agents, i.e., #f(N′)≥#f(N′).\# r_f(N )≥\# b_f(N ). (24) Counting now the number of red agents in Ka⋆K_a , Qa⋆Q_a , N′N , and V and using (21) and (24), we get that #f(N)≥(|V|−2k)+|Qa⋆|−12+Δ+|N′|2+|S|.\# r_f(N)≥(|V|-2k)+ |Q_a |-12+ + |N |2+|S|. (25) Similarly counting blue agents in Qa⋆Q_a , N′N , and V, we obtain #f(N)≤|Qa⋆|−12−Δ+1+|N′|2+(|V|−|S|).\# b_f(N)≤ |Q_a |-12- +1+ |N |2+(|V|-|S|). (26) Since blue is the majority opinion, i.e., #f(N)<#f(N)\# r_f(N)<\# b_f(N), it follows that −2k+Δ+|S| -2k+ +|S| <−Δ+1−|S| <- +1-|S| 2|S|+2Δ 2|S|+2 <2k+1 <2k+1 |S|+Δ |S|+ ≤k ≤ k Taking into account (23), we obtain that |S|+Δ=k|S|+ =k must hold. Hence, the first statement of the claim follows. Observe that |S|+Δ=k|S|+ =k implies also that (24) must hold with equality, as otherwise #f(N′)≥|N′|/2+1\# r_f(N )≥|N |/2+1, which would imply #f(N) \# r_f(N) ≥(|V|−2k)+|Qa⋆|−12+Δ+|N′|2+1+|S| ≥(|V|-2k)+ |Q_a |-12+ + |N |2+1+|S| =(|V|−k)+|Qa⋆|−12+|N′|2+1 =(|V|-k)+ |Q_a |-12+ |N |2+1 ≥#f(N) ≥\# b_f(N) contradicting our assumption that blue is the majority winner. In particular, this means that (19) for each v∈Vv∈ V and (18) for each e∈Ee∈ E hold with equality. ◀ Claim˜8 immediately yields that (i) and (i) in Claim˜7 holds for each e∈Ee∈ E, and thus S is a vertex cover for H. We next show that it is a capacitated vertex cover for H. Let us define a mapping g:E→Sg:E→ S such that g maps e∈Ee∈ E to its endpoint v if and only if f(z1v,e)=f(z_1^v,e)= blue. By Claim˜8 we know that (i) in Claim˜7 holds for each e∈Ee∈ E, and thus g is well-defined. To show that S is a capacitated vertex cover for H with capacity function c, it remains to show that f maps at most c(v)c(v) vertices to each v∈Sv∈ S. To see this, consider some v∈Sv∈ S. By (19) in Claim˜8 and using Claim˜5 we know that v has exactly c(v)+2c(v)+2 red neighbors and degH(v)−c(v) _H(v)-c(v) blue ones within GvG_v. By the definition of g, we further know that v has exactly |g−1(v)||g^-1(v)| blue neighbors within edge-gadgets, and thus exactly degH(v)−|g−1(v)| _H(v)-|g^-1(v)| red ones. Finally, taking into account a⋆a , we obtain that c( c( v)+2+degH(v)−|g−1(v)|=#f(NG(v)) v)+2+ _H(v)-|g^-1(v)|=\# r_f(N_G(v)) (27) >#f(NG(v))=degH(v)−c(v)+|g−1(v)|+1 >\# b_f(N_G(v))= _H(v)-c(v)+|g^-1(v)|+1 which implies 2c(v)+1 2c(v)+1 >2|g−1(v)| >2|g^-1(v)| c(v) c(v) ≥|g−1(v)| ≥|g^-1(v)| as required. Hence, S is a capacitated vertex cover for H of size at most k, and thus (H,c,k)(H,c,k) is a yes-instance. For the other direction, suppose that S is a capacitated vertex cover for H of size k with mapping g:E→Sg E→ S. We define a red–blue labeling f as follows. Using Claim˜5, we label the agents in each vertex gadget GvG_v, v∈Vv∈ V, so that • f(v)=f(v)= red if and only if v∈Sv∈ S, • v has c(v)+2c(v)+2 red and degH(v)−c(v) _H(v)-c(v) blue neighbors within the gadget GvG_v, • (19) holds for v∈Vv∈ V, and • each agent in GvG_v other than v has more red than blue neighbors. Using Claim˜7, we then label the agents in GeG_e for each e∈Ee∈ E so that • for each endpoint v of e, we have f(z1v)=f(z_1^v)= blue if and only if g(e)=vg(e)=v, • properties (i)–(i) in Claim˜7 hold, • (18) holds, and • each agent in GeG_e other than v has more red than blue neighbors. Finally, using Claim˜5 again, we label the agents in the counting gadget Ga⋆G_a so that • f(a)=f(a)= red for each agent a∈Ka⋆a∈ K_a , • f(a⋆)=f(a )= blue, • a⋆a has |V|−k+1|V|-k+1 red and k blue neighbors within Ga⋆G_a , • the number of red and blue agents in Qa⋆∖a⋆Q_a \a \ is equal, and • each agent in Ga⋆G_a other than a⋆a has more red than blue neighbors. Note further that for each v∈Vv∈ V, by |g−1(v)|≤c(v)|g^-1(v)|≤ c(v) we get that (27) holds. Moreover, (22) holds with Δ=0 =0, and hence, |S|=k|S|=k yields #f(NG(a⋆))=|V|+1>|V|=#f(NG(a⋆)).\# r_f(N_G(a ))=|V|+1>|V|=\# b_f(N_G(a )). This proves that each agent has more red than blue neighbors in G under f. In order to show that all agents are under majority illusion, it now suffices to show that blue is the majority winner. To see this, note that (25) and (26) both hold with Δ=0 =0 and |S|=k|S|=k, implying #f(N)<#f(N)\# r_f(N)<\# b_f(N). Therefore, (N,G,1)(N,G,1) is a yes-instance of q-Majority Illusion. This proves the correctness of our reduction. ∎ 6 Bounded Distance to Disjoint Paths Note that the XP algorithm for treewidth by Grandi et al. (2025), as well as our simpler (and faster) dynamic programming for Max List Majority Illusion, presented in Lemma˜1 and running in (|N|5)O (|N|^5 ) time, implies that q-Majority Illusion can be solved in polynomial time on trees. If the social network is a path P, then the problem gets even easier: simply labeling every other agent on P as red maximizes the number of agents under majority illusion. Theorem 5. If the social network G is a path, q-Majority Illusion can be solved in linear time. In fact, the maximum number of agents under majority illusion in G, denoted by μ(G)μ(G), depends only on the number |N||N| of agents: μ(G)=0if |N|≤2,⌈|N|/2⌉if |N| is odd,|N|/2−1if |N| is even.μ(G)= cases0&if |N|≤ 2,\\ |N|/2 &if |N| is odd,\\ |N|/2-1&if |N| is even. cases Proof. If |N|≤2|N|≤ 2, then all agents have to be labeled with the majority color. Thus, no agent is under the illusion. For |N|≥3|N|≥ 3, let f∗f^* be a labeling of G for which μG=μf⋆(G) _G= _f (G). For a path P, let μ^opt|x(P) μ_ opt|x(P) denote the maximum number of agents with a majority-red neighborhood under any labeling f of P that satisfies #f(P)=x\# r_f(P)=x. The following claims establish the value of μ^opt|x(P) μ_ opt|x(P) depending on the parity of |P||P|. For a path P=(a1,…,aℓ)P=(a_1,…,a_ ), we define the agent sets P1=ai:i∈[ℓ],i oddP_1=\a_i:i∈[ ],i odd\ and P2=ai:i∈[ℓ],i evenP_2=\a_i:i∈[ ],i even\. Claim 9. For a path P=(a1,…,aℓ)P=(a_1,…,a_ ) with ℓ even, we have μ^opt|x(P)=x μ_ opt|x(P)=x for each x∈[ℓ]x∈[ ]. Proof. Let AiA_i be the agents with a majority-red neighborhood in PiP_i for each i∈[2]i∈[2]. Note that all neighbors of any agent in A1∪A2A_1∪ A_2 must be red. At most one agent (an endpoint of P) has only one neighbor in each AiA_i, i∈[2]i∈[2], with every other agent having two neighbors, all of them red and in P3−iP_3-i. Thus, summing up the neighborhood sizes of all agents in AiA_i yields at least 2|Ai|−12|A_i|-1. As each red agent in P3−iP_3-i can contribute to the neighborhood of at most two agents in AiA_i, there must be at least |Ai||A_i| red agents in P3−iP_3-i. Hence, labeling x agents red in P yields at most x agents with a majority-red neighborhood. Moreover, such a labeling exists for each x∈[ℓ]x∈[ ]: it can be verified easily that it suffices to label the first x the agents according to the order a2,a4,…,aℓ,aℓ−1,aℓ−3,…,a1a_2,a_4,…,a_ ,a_ -1,a_ -3,…,a_1 as red. ◀ Now, we show the analogous result for the case when the length of P is odd. Claim 10. For a path P=(a1,…,aℓ)P=(a_1,…,a_ ) with ℓ odd, we have μ^opt|x(P)=x+1 if x=ℓ−12;x if x∈[ℓ],x≠ℓ−12. μ_ opt|x(P)= casesx+1& if x= -12;\\ x& if x∈[ ],x≠ -12. cases (28) Proof. Let AiA_i be the agents with a majority-red neighborhood in PiP_i for each i∈[2]i∈[2]. Again, all neighbors of any agent in A1∪A2A_1∪ A_2 must be red. Note that at most two agents in A1A_1 (the endpoints of P) have only one neighbor, with every other agent in A1∪A2A_1∪ A_2 having two neighbors, all of them red. Consider first A1A_1. Summing up the neighborhood sizes of all agents in A1A_1 yields at least 2|A1|−22|A_1|-2. Since each red agent in P2P_2 can contribute to the neighborhood of at most two agents in A1A_1, there must be at least |A1|−1|A_1|-1 red agents in P2P_2; moreover, equality is only possible if A1=P1A_1=P_1 (as otherwise there is at least one red agent in P2P_2 with only one neighbor in A1A_1). Hence, labeling x agents red in P2P_2 yields at most x agents with a majority-red neighborhood, unless x=|P2|x=|P_2| in which case all x+1x+1 agents in A1A_1 have majority-red neighborhood. Consider now A2A_2. Summing up the neighborhood sizes of all agents in A2A_2 yields at least 2|A2|2|A_2|. Since each red agent in P1P_1 can contribute to the neighborhood of at most two agents in A1A_1, but the ones with the smallest and the largest index can contribute to the neighborhood of at most one agent in A2A_2, we get that there must be at least |A2|+1|A_2|+1 red agents in P1P_1. Hence, labeling x agents red in P1P_1 yields at most x−1x-1 agents with a majority-red neighborhood in P2P_2. Altogether, it follows that the value of μ^opt|x μ_ opt|x is at most the right-hand side of (28). Moreover, a suitable labeling reaching the claimed value exists for each x∈[ℓ]x∈[ ]: as in Claim˜9, it suffices to label the first x the agents according to the order a2,a4,…,aℓ,aℓ−1,aℓ−3,…,a1a_2,a_4,…,a_ ,a_ -1,a_ -3,…,a_1 as red. ◀ As the majority color must be blue, the maximum number of red agents is |N|/2−1|N|/2-1 if |N||N| is even, and ⌊|N|/2|⌋ |N|/2| otherwise. I.e., Claims˜9 and 10 imply the statement. ∎ The observations in the proof of Theorem˜5 can be used to solve the case when the social network consists of several disjoint paths, leading to a linear-time algorithm. Theorem 6. If the social network is the union of disjoint paths, q-Majority Illusion is solvable in linear time. Proof. We show that there is a simple, linear-time method to create an optimal labeling f of the set N of agents in G optimally, i.e., one that maximizes the number of agents under illusion. Then comparing μf(N) _f(N) with q⋅|N|q·|N| suffices to decide whether our instance is a yes-instance. Our method relies on Claims˜9 and 10. Let P_ even and P_ odd denote the set of disjoint paths in G with an even and odd number of agents, respectively, and let =∪P=P_ even _ odd. Furthermore, let us adopt the notation P1P_1 and P2P_2 as defined in the proof of Theorem˜5 for each path P in G. Let f be a labeling of G that maximizes μf(G) _f(G). We can clearly assume that #f(N)=⌊|(N|−1)/2⌋\# r_f(N)= |(N|-1)/2 . Let us call a path |P||P| in G f-superb if it is odd and has ⌊|P|/2⌋ |P|/2 red agents; then μf(P)=⌈|P|/2⌉ _f(P)= |P|/2 . Note that for the set fS_f of f-superb paths, it must hold that ⌊|N|−12⌋=#f(N)≤∑P∈f⌊|P|2⌋+∑P∈∖f|P|. |N|-12 =\# r_f(N)≤ _P _f |P|2 + _P _f|P|. (29) Note also that μf(N) _f(N) =μf(⋃P∈fP)+μf(⋃P∈∖fP) = _f ( _P _fP )+ _f ( _P _fP ) ≤∑P∈f⌈|P|2⌉+∑P∈∖f#f(P) ≤ _P _f |P|2 + _P _f\# r_f(P) =∑P∈f(#f(P)+1)+∑P∈∖f#f(P) = _P _f(\# r_f(P)+1)+ _P _f\# r_f(P) =#f(N)+|f| =\# r_f(N)+|S_f| where the inequality is implies by Claims˜9 and 10. We use the following algorithm: 1. We create add to a path family Π paths which will be f′f -superb for the labeling f′f we construct. Initially, Π=∅ = , and we add paths from P_ odd to Π one by one, in increasing order of their length, as long as the condition ⌊|N|−12⌋≤∑P∈Π⌊|P|2⌋+∑P∈∖Π|P| |N|-12 ≤ _P∈ |P|2 + _P |P| (30) holds. Note that due to the ordering of the odd paths in which we add them to Π , we know that |Π|≥|f|| |≥|S_f|, because fS_f satisfies (29). 2. We label each agent in P2:P∈Π\P_2:P∈ \ as red; let R be number of these agents. 3. We label ⌊(|N|−1)/2⌋−R (|N|-1)/2 -R agents on paths in ∖ΠP as red in a way that yields ⌊(|N|−1)/2⌋−R (|N|-1)/2 -R agents with a majority-red neighborhood in these paths; this can be achieved as shown in Claims˜9 and 10. Notice that this way, we can label exactly ⌊(|N|−1)/2⌋ (|N|-1)/2 agents red, due to (30); in particular, the majority color will be blue. Moreover, Claims˜9 and 10 guarantee that the number of agents under majority illusion in the obtained labeling f′f is exactly #f′(N)+|Π|≥#f(N)+|f|=μf(G)\# r_f (N)+| |≥\# r_f(N)+|S_f|= _f(G). Hence, the labeling f′f is optimal. To decide whether our instance is a yes-instance, it suffices to compare μf′(N) _f (N) with q⋅|N|q·|N|. Clearly, the running time of our algorithm is (|N|)O (|N| ). ∎ Our final result shows that the method we apply to solve q-Majority Illusion on disjoint paths is not robust with respect to the addition of agents: the presence of only a few additional agents leads to intractability, since the problem is W[1]-hard when parameterized by the distance to disjoint paths of the social network. Theorem 7. q-Majority Illusion is W[1]-hard when parameterized by the distance to disjoint paths ddp(G)ddp(G) of the social network G. Proof. We are going to present a parameterized reduction from Multidimensional Halfset Sum when parameterized by the dimension d. Let (d,)(d,S) be our input instance with =1,…,nS=\s_1,…,s_n\. We may assume without that |i|=s⋆|s_i|=s for some integer s⋆∈ℕs , as otherwise we can create an equivalent instance by appending to each vector i∈s_i a new coordinate with value s⋆−|i|s -|s_i| for some large enough integer s⋆s , say s⋆=maxi∈[n],j∈[d]i[j]s = _i∈[n],j∈[d]s_i[j]. Observe that this transformation indeed yields an equivalent instance, since if a set ′S of n2 n2 vectors sum up to Σ2 s_ 2 where Σ=∑i∈[n]is_ = _i∈[n]s_i, then the newly appended last coordinates of the vectors in ′S , as well as in ∖′S , automatically sum up to n2s⋆−|Σ| n2s -|s_ |. We may further assume that n>d+2n>d+2 and that Σ[j]>4ds_ [j]>4d for each j∈[d]j∈[d]. Moreover, by multiplying all vectors in S by 44, we ensure that each coordinate of every vector in S (and, hence, s⋆s ) is divisible by 44. Construction. Let us now define an instance I=(N,G,q)I=(N,G,q) of q-Majority Illusion as follows. We define the integer α=n−d−2α=n-d-2. To define the social network G of our instance I, we create a short path for each i∈[α]i∈[α] which is a path Xi=(ai1,bi1,ai2,bi2,ai3)X_i=(a_i^1,b_i^1,a_i^2,b_i^2,a_i^3), and a long path for each i∈[n]i∈[n] defined as a path Yi=(pi1,qi1,pi2,qi2,…,pis⋆,qis⋆,pis⋆+1)Y_i=(p_i^1,q_i^1,p_i^2,q_i^2,…,p_i^s ,q_i^s ,p_i^s +1). We will use the agent sets Ai=aij:j∈[3],Pi=pij:j∈[s⋆+1],Bi=bij:j∈[2],Qi=qij:j∈[s⋆]. array[]r@ 2ptl@ 12ptr@ 2ptlA_i 2.0&=\a_i^j:j∈[3]\, 12.0&P_i 2.0&=\p_i^j:j∈[s +1]\,\\[3.0pt] B_i 2.0&=\b_i^j:j∈[2]\, 12.0&Q_i 2.0&=\q_i^j:j∈[s ]\.\\[3.0pt] array We further let A=⋃i∈[α]AiA= _i∈[α]A_i, and we define the sets B, P, and Q analogously. Additionally, we create a set M=m0,m1,…,mdM=\m_0,m_1,…,m_d\ of modulator agents. We connect m0m_0 with all agents in B as well as with every other modulator agent. Moreover, we connect m1m_1 to the first i[1]s_i[1] agents of QiQ_i on YiY_i (i.e., qi1,…,qii[1]q_i^1,…,q_i^s_i[1]) for each i∈[n]i∈[n], then connect m2m_2 to the next i[2]s_i[2] agents of QiQ_i on YiY_i, and so on, with each modulator mjm_j, j∈[d]j∈[d], connected to exactly [j]s[j] agents from QiQ_i (placed “consecutively” along YiY_i). This way, every agent in QiQ_i is connected to exactly one modulator agent, by |Qi|=s⋆|Q_i|=s . This defines the social network G over agent set N=N∪N∪MN=N_ odd∪ N_ even∪ M. Note that the number of agents is |N|=5α+n(2s⋆+1)+d+1|N|=5α+n(2s +1)+d+1. Finally, we set q such that q|N|=|N|−n2(s⋆+1)q|N|=|N|- n2(s +1). Correctness. Assume first that there is a red–blue labeling f of G with majority color blue that leaves q|N|q|N| agents under majority illusion; let us choose f so as to maximize the number of agents under majority illusion. We may assume that #f(N)=|N|−12=3α+ns⋆+d+1\# r_f(N)= |N|-12=3α+ns +d+1 (31) due to our choice of α. Notice that the number of agents under majority illusion in AiA_i (or in PiP_i) solely depends on the labeling of agents in BiB_i (or in QiQ_i, respectively). labeling one agent in bi1,bi2\b_i^1,b_i^2\ red for some i∈[α]i∈[α] yields exactly one agent in AiA_i under majority illusion, while labeling both of them achieves this for all three agents in AiA_i. Setting #f(B)=2α−kB,\# r_f(B)=2α-k_B, (32) we know that the number of agents under majority illusion in A is at most 3#f(B)2≤3α−3kB2. 3\# r_f(B)2≤ 3α- 3k_B2. (33) Similarly, if there are ℓ red agents in QiQ_i, then the maximum number of agents under illusion in PiP_i is ℓ if ℓ<s⋆ <s and ℓ+1=s⋆+1 +1=s +1 if ℓ=s⋆ =s . Hence, the number of agents under majority illusion in P is at most s⋆+1s⋆#f(Q). s +1s \# r_f(Q). (34) Similarly, the number of agents under majority illusion in BiB_i (or in QiQ_i) solely depends on the labeling of agents in Ai∪m0A_i∪\m_0\ (or in Pi∪M∖m0P_i∪ M \m_0\, respectively). In order to ensure that all agents in ⋃i∈αBi _i∈αB_i are under majority illusion, it is sufficient to label every agent in ai2:i∈[α]∪m0\a_i^2:i∈[α]\∪\m_0\ red. Similarly, to ensure that all agents in ⋃i∈[n]Qi _i∈[n]Q_i are under majority illusion, it is sufficient to label all agents in M∖m0∪pi2j:j∈[s⋆/2]M \m_0\∪\p_i^2j:j∈[s /2]\ as red. Thus, we need not more than α+ns⋆2+d+1α+ ns 2+d+1 red agents in A∪P∪MA∪ P∪ M to ensure that all agents in B∪QB∪ Q are under majority illusion. In particular, by (31), there are at least 2α+ns⋆22α+ ns 2 red agents in B∪QB∪ Q, implying #f(Q)≥ns⋆2\# r_f(Q)≥ ns 2. Claim 11. All modulator agents are red under f. Proof. Clearly, we if m0m_0 is not red but #f(A)>0\# r_f(A)>0, then either we can re-label any red agent in A as blue and set m0m_0 as red without decreasing the number of agents under majority illusion. If #f(A)=0\# r_f(A)=0, then we can take the first d+4d+4 red agents from Q in the order where qijq_i^j precedes qi′j′q_i ^j if i<i′i<i or i=i′i=i and j<j′j<j (recall that #f(Q)≥ns⋆2>d+4\# r_f(Q)≥ ns 2>d+4), re-label them as blue and label m0m_0 as well as d+3d+3 agents of the form ai2a_i^2 as red: this way, at most d+4d+4 agents in P and possibly d modulators cease to be under illusion, while at least 2(d+3)2(d+3) agents in B will get (newly) under illusion. By our choice of f, this proves that m0m_0 is red. To see that each mj∈M∖m0m_j∈ M \m_0\ is red too, suppose the contrary. Let P^j P_j agents of the form pi2hp_i^2h with two neighbors in NG(mj)N_G(m_j). If some agent in P^j P_j is red, then we can re-label it as blue and set mjm_j as blue instead, without decreasing the number of agents under majority illusion. Otherwise, let x+1x+1 be the odd integer in d+4,d+5\d+4,d+5\. Let us re-label as blue the first x+1x+1 red agents from Q as in the previous paragraph, causing at most x+2+dx+2+d agents from P∪MP∪ M to lose their majority illusion, and re-label mjm_j as well as x agents of the form P^j P_j as red, increasing the number of agents under majority illusion in Q by 2x2x. Due to x+2+d<2x+2+d<2x, this increases the number of agents under majority illusion, contradicting our choice of f and proving f(mj)=f(m_j)= red. ◀ By Claim˜11, we know that all modulators are red. In addition, there are at most α+ns⋆2α+ ns 2 red agents in A∪PA∪ P (as that many red agents suffice to make all agents in B∪QB∪ Q to be under majority illusion). Hence, there exists a non-negative integer kA∪Pk_A∪ P such that #f(A∪P)=α+ns⋆2−kA∪P.\# r_f(A∪ P)=α+ ns 2-k_A∪ P. (35) It is clear that every agent in B∪QB∪ Q needs at least one red neighbor in A∪PA∪ P, and each agent in A∪PA∪ P is connected to at most two agents in B∪QB∪ Q. Thus, the number of agents under majority illusion in B∪QB∪ Q is at most 2#f(A∪P)≤2α+ns⋆−2kA∪P.2\# r_f(A∪ P)≤ 2α+ns -2k_A∪ P. (36) Note that by Claim˜11 and (31), we know #f(Q)=#f(N)−|M|−#f(A∪P)−#f(B)=3α+ns⋆−(α+ns⋆2−kA∪P)−(2α−kB)=ns⋆2+kA∪P+kB split\# r_f(Q)&=\# r_f(N)-|M|-\# r_f(A∪ P)-\# r_f(B)\\ &=3α+ns -(α+ ns 2-k_A∪ P)-(2α-k_B)\\ &= ns 2+k_A∪ P+k_B split (37) where we used the definitions of kA∪Pk_A∪ P and of kBk_B as given in (32) and (35). Summing up (33), (34), and (36) while taking into account the modulator agents and using (37), the total number of agents under majority illusion is at most 3α 3α −3kB2+s⋆+1s⋆#f(Q)+2α+ns⋆−2kA∪P+|M| - 3k_B2+ s +1s \# r_f(Q)+2α+ns -2k_A∪ P+|M| =5α+ns⋆+s⋆+1s⋆(ns⋆2+kA∪P+kB)−3kB2 =5α+ns + s +1s ( ns 2+k_A∪ P+k_B )- 3k_B2 −2kA∪P+d+1 =5α-2k_A∪ P+d+1 ≤5α+3ns⋆2−kA∪B−kB2+n2+d+1 ≤ 5α+ 3ns 2-k_A∪ B- k_B2+ n2+d+1 =q|N|−kA∪B−kB2≤q|N|. =q|N|-k_A∪ B- k_B2≤ q|N|. (38) Since there are at least q|N|q|N| agents under illusion in f, the following must hold: (a) (38) holds with equality, which implies kB=kA∪P=0k_B=k_A∪ P=0 and, hence #f(Q)=ns⋆2\# r_f(Q)= ns 2; (b) the number of agents under majority illusion in P must be exactly s⋆+1s⋆#f(Q)=n2(s⋆+1) s +1s \# r_f(Q)= n2(s +1); (c) all modulators must be under majority illusion. Observe that (a) and (b) together imply that the set of red agents in Q must be of the form ⋃i∈SQi _i∈ SQ_i for some I⋆⊆[n]I [n] with |I⋆|=n2|I |= n2. Hence, for each j∈[d]j∈[d], the modulator agent mjm_j has exactly ∑i∈I⋆i[j] _i∈ I s_i[j] red neighbors. Therefore, (c) requires that ∑i∈I⋆i[j]≥∑i∈[n]∖I⋆i[j], _i∈ I s_i[j]≥ _i∈[n] I s_i[j], (39) since mjm_j has only one red neighbor not in Q (namely, m0m_0). Summing this up for j∈[d]j∈[d], we get n2s⋆=∑j∈[d]∑i∈I⋆i[j]≥∑j∈[d]∑i∈[n]∖I⋆i[j]=n2s⋆ n2s = _j∈[d] _i∈ I s_i[j]≥ _j∈[d] _i∈[n] I s_i[j]= n2s by ||=s⋆|s|=s for each ∈s . Hence, equality must hold for (39) for each j∈[d]j∈[d], implying that i:i∈I⋆\s_i:i∈ I \ is a solution for our instance IIof Multidimensional Halfset Sum. For the other direction, suppose I is yes-instance, i.e., there exists a subset ′S of S of size n2 n2 for which ∑∈′=Σ2 _s s= s_ 2. Let I⋆=i:i∈[n],∈′I =\i:i∈[n],s_i \. We define a red–blue labelling f for J under which exactly q|N|q|N| agents are under majority illusion. First, let us color all modulator agents, all agents in M∪ai2,bi1,bi2:i∈[α]∪pi2j:i∈[n],j∈[s⋆/2]M∪\a_i^2,b_i^1,b_i^2:i∈[α]\∪\p_i^2j:i∈[n],j∈[s /2]\ red, as well as all agents in ⋃i∈I⋆Qi _i∈ I Q_i. By our previous arguments, this means that all agents in A∪B∪QA∪ B∪ Q, as well as all agents in ⋃i∈I⋆Pi _i∈ I P_i are under majority illusion. Moreover, since ′S is a solution, we know that (39) holds for each j∈[d]j∈[d] with equality; since m0m_0 is red and is the only neighbor of mjm_j not in Q, we get that mjm_j is also under majority illusion. This clearly holds for m0m_0 as well, who has only red neighbors. Hence, the set of agents under majority illusion is exactly N∖⋃i∈[n]∖I⋆PiN _i∈[n] I P_i, a set of size exactly q|N|q|N|. This shows the correctness of our reduction. ∎ 7 Bounded Distance to Cluster Graph Finally, let us turn to the parameterization by the distance of the social network to cluster graphs; that is, we assume that removing a few agents results in a collection of cliques; however, these cliques can have unbounded size. Again, we are not the first considering this parameter in the context of social networks; see, e.g., (Eiben, Ganian, and Ordyniak 2018; Fioravantes et al. 2025a, 2026). Theorem 8. q-Majority Illusion is in XP when parameterized by dcg(G)dcg(G), the distance to cluster graphs of the social network G. Proof. Let M be a set of agents of size k=dcg(G)k=dcg(G) such that G−MG-M is a disjoint union of cliques K1,…,KℓK_1,…,K_ . This time, our algorithm first guesses the labeling fMf_M of M and then extends fMf_M using a dynamic-programming approach over the cliques K1,…,KℓK_1,…,K_ . Let Kj→ℓ=Kj∪⋯∪KℓK_j→ =K_j∪·s∪K_ . For every clique j∈[ℓ]j∈[ ], we have a dynamic programming table DPjDP_j containing values DPj[R,]DP_j[R,r], where • R∈[|N|/2]R∈[|N|/2] is the number of red agents in Kj→ℓK_j→ , and • =(ri)i∈Mr=(r_i)_i∈ M, where ri∈[|N|]0r_i∈[|N|]_0 is the number of red neighbors of agent i∈Mi∈ M in Kj→ℓK_j→ . The value DPj[R,]DP_j[R,r] stores the maximum number of agents in Kj→ℓK_j→ with a majority-red neighborhood over all possible extensions f of fMf_M such that #f(Kj→ℓ)=R\# r_f(K_j→ )=R and for every i∈Mi∈ M it holds that #f(Kj→ℓ(i))=ri\# r_f(N_K_j→ (i))=r_i. Before we formally define the computation, we show an auxiliary lemma proving that, for each clique KjK_j, the number of relevant labelings can be bounded in terms of our parameter. Specifically, we show that if we swap the labels of two twins, the number of agents with majority-red neighborhood remains the same. Claim 12. Let f be an extension of fMf_M and u,vu,v be a pair of agents in KjK_j for some j∈[ℓ]j∈[ ] such that f(u)=f(u)= red, f(v)=f(v)= blue, and u and v are twins, i.e., (u)∖v=(v)∖uN(u) \v\=N(v) \u\. Then, μ^f(N)=μ^f′(N) μ_f(N)= μ_f (N) where f′(w)=if w=v,if w=u, andf(w)otherwise.f (w)= cases red&if w=v,\\ blue&if w=u, and\\ f(w)&otherwise. cases Proof. Let Nuv=((u)∪(v))∖u,vN_uv=(N(u) (v)) \u,v\. Each agent that is not in NuvN_uv is not affected by the swap of labels. For each agent in NuvN_uv, the number of red neighbors also remains the same, since (u)∖v=(v)∖u=NuvN(u) \v\=N(v) \u\=N_uv. Finally, it may happen that v has a majority-red neighborhood in f, but not in f′f . In this case, #f(Nuv)=#f(Nuv)\# r_f(N_uv)=\# b_f(N_uv), and thus u does not have majority-red neighborhood in f, but it does so in f′f . This proves the claim. ◀ Let KjK_j, j∈[ℓ]j∈[ ], be a clique in G. Observe that the agents in KjK_j can be partitioned into (2k)O (2^k ) classes of twins called types. Moreover, by Claim˜12, swapping the labels of two twin agents does not change the number of agents with a majority-red neighborhood. Hence, we say that two labelings f and f′f are equivalent if they have the same number of red agents of each type. Consider the resulting equivalence classes of all labelings of KjK_j, and let ℱjF_j contain exactly one labeling from each such class. By the previous arguments, it holds that |ℱj|∈|N|(2k)|F_j|∈|N|^O (2^k ). Moreover, we use ℱjRF_j^R to denote the set of all labelings in ℱjF_j with exactly R red agents. The base case of the computation is when j=ℓj= . To compute DPℓ[R,]DP_ [R,r], we check if we can satisfy the requirement prescribed by the pair (R,)(R,r). Specifically, we iterate over all labelings of KjK_j in ℱjF_j that label exactly R agents red, and for each of them we check that they satisfy that each modulator agent i∈Mi∈ M has exactly rir_i red neighbors. For all such labelings, we compute the number of agents with majority-red neighborhoods, and store the maximum value in DPj[R,]DP_j[R,r]. Formally, the computation is as follows:111Here and elsewhere, we let the maximum of some value taken over an empty set be defined as −∞-∞. DPℓ[R,]=maxf:ℱℓR s.t. ∀i∈M:#f(Kℓ(i))=riμ^f∪fM(Kℓ)DP_ [R,r]= _ subarraycf _ ^R s.t. ∀ i∈ M \\ \# r_f(N_K_ (i))=r_i subarray\!\!\!\!\!\! μ_f∪ f_M(K_ ) For j∈[1,ℓ−1]j∈[1, -1], we compute DPj[R,]DP_j[R,r] as follows. We iterate over all possible values for the number R′R of red agents in KjK_j (from among all R red agents in Kj→ℓK_j→ ), and over all labelings of KjK_j in ℱjF_j that label exactly R′R agents in KjK_j red. For all values of R′R and for all labelings in f∈ℱjR′f ^R _j, we compute the maximum number of agents with a majority-red neighborhood in Kj→ℓK_j→ under some suitable labeling respecting our choices for R′R , f, and (R,)(R,r). This can be done by using previously computed values from table DPj+1DP_j+1. More precisely, we need to ensure that (i) there are R−R′R-R red agents in Kj+1→ℓK_j+1→ , and that (i) each modulator agent i∈Mi∈ M has exactly rir_i red neighbors in Kj→ℓK_j→ , that is, i has ri−#f(Kj(i))r_i-\# r_f(N_K_j(i)) red neighbors in Kj+1→ℓK_j+1→ . The maximum number of agents in Kj+1→ℓK_j+1→ with a majority-red neighborhood under such a labeling is stored in DPj[R−R′,′]DP_j[R-R ,r ] where ri′=ri−#f(Kj(i))r _i=r_i-\# r_f(N_K_j(i)) for i∈Mi∈ M. Formally, the computation is defined as follows. DPj[R,]=maxR′∈[min|Kj|,R]0maxf∈ℱjR′ _j[R,r]= _R ∈[ \|K_j|,R\]_0 _f _j^R μ^f∪fM(Kj)+DPj+1[R−R′,(ri−#f(Kj(i)))i∈M]. a μ_f∪ f_M(K_j)+DP_j+1[R-R ,(r_i-\# r_f(N_K_j(i)))_i∈ M]\,. Once the dynamic programming table for clique K1K_1 is correctly computed, we check whether there exists a pair (R,)(R,r) for some R∈[⌊|N|−12⌋−#fM(M)]0R∈[ |N|-12 -\# r_f_M(M)]_0 and ∈[|N|]0kr∈[|N|]_0^k so that DP1[R,]+|i∈M:ri+#fM(M(i))>deg(i)2|>q⋅|N|.DP_1[R,r]+|\i∈ M r_i+\# r_f_M(N_M(i))> (i)2\|\\ >q·|N|. If so, we return yes; otherwise, we return no. Note that our choice for R ensures that blue is the majority color, while our second condition guarantees that the number of agents under majority illusion is at least q|N|q|N|. Thus, the correctness of our algorithm is implied by the following claim for j=1j=1. Claim 13. For all values of j∈[ℓ]j∈[ ], R∈[⌊|N|/2⌋]0R∈[ |N|/2 ]_0, and =(ri)i∈Mr=(r_i)_i∈ M with ri∈[|N|]0r_i∈[|N|]_0, we have DPj[R,]=wDP_j[R,r]=w (where w∈ℕw ) if and only if there exists a labeling f of G that extends fMf_M and satisfies the following conditions: (a) #f(Kj→ℓ)=R\# r_f(K_j→ )=R, (b) #f(Kj→ℓ(i))=ri\# r_f(N_K_j→ (i))=r_i\, for each i∈Mi∈ M, and (c) μ^f(Kj→ℓ)=w μ_f(K_j→ )=w. Proof. We prove the statement by induction on j, for decreasing values of j from ℓ to 11. Consider the case for j=ℓj= , and recall that DPℓ[R,]=maxf:ℱℓR s.t. ∀i∈M:#f(Kℓ(i))=riμ^f∪fM(Kℓ),DP_ [R,r]= _ subarraycf _ ^R s.t. ∀ i∈ M \\ \# r_f(N_K_ (i))=r_i subarray\!\!\!\!\!\! μ_f∪ f_M(K_ ), (40) First, assume that f is a labeling of G satisfying conditions (a)–(c) of the claim for some R and r. By the definition of equivalent labelings and of ℱℓRF_ ^R, it is clear that there must be a labeling f′f in ℱℓRF^R_ that is equivalent to the restriction of f to KℓK_ and satisfies #f′(Kℓ(i))=ri\# r_f (N_K_ (i))=r_i for each modulator i∈Mi∈ M. Then in the expression (40) for computing DPℓ[R,]DP_ [R,r], the maximum is taken over a non-empty subset, and in particular, the value of DPℓ[R,]DP_ [R,r] will be set to at least the number of agents with a majority-red neighborhood in KℓK_ under f′f , that is, to μ^f′(Kℓ) μ_f (K_ ) which, in turn, equals μ^f(Kℓ) μ_f(K_ ) by the definition of equivalence of labelings. Suppose now that DPℓ[R,]=wDP_ [R,r]=w; we show that there exist a labeling f of G satisfying conditions (a)–(c) of the claim. Let f∈ℱℓRf ^R_ for which μ^f∪fM(Kℓ)=w μ_f∪ f_M(K_ )=w and also #f(Kℓ(i))=ri\# r_f(N_K_ (i))=r_i for each i∈Mi∈ M holds. Let f′f be an arbitrary extension of f∪fMf∪ f_M over N. Then conditions (a)–(c) clearly hold for f′f by our choice of f′f . Consider now the case j∈[ℓ−1]j∈[ -1], and recall that DPj[R,]=maxR′∈[min|Kj|,R]0maxf∈ℱjR′μ^f∪fM(Kj)+DPj+1[R−R′,(ri−#f(Kj(i)))i∈M]. split&DP_j[R,r]= _R ∈[ \|K_j|,R\]_0 _f _j^R \\ & a μ_f∪ f_M(K_j)+DP_j+1[R-R ,(r_i-\# r_f(N_K_j(i)))_i∈ M]\,. split (41) Assume first that f is a labeling of G satisfying conditions (a)–(c) for some R and r. We aim to show that DPj[R,]≥μ^f(Kj→ℓ)DP_j[R,r]≥ μ_f(K_j→ ). Let R′=#f(Kj)R =\# r_f(K_j); then we have R′≤min|Kj|,RR ≤ \|K_j|,R\. Moreover, let f′f be the restriction of f to KjK_j. Observe that by its definition, ℱjR′F_j^R must contain some labeling f f of KjK_j that is equivalent to f′f . Therefore, the maximum in the expression (41) for DPj[R,]DP_j[R,r] is taken over a non-empty set. To lower-bound the maximum value obtained in (41), first note that μ^f^∪fM(Kj)=μ^f(Kj) μ_ f∪ f_M(K_j)= μ_f(K_j). Second, note that • #f(Kj+1→ℓ)=R−R′\# r_f(K_j+1→ )=R-R and • #f(Kj+1→ℓ(i))=ri−#f(Kj(i))\# r_f(N_K_j+1→ (i))=r_i-\# r_f(N_K_j(i)) for each i∈Mi∈ M. Hence, if w′w denotes the number of agents with majority-red neighborhood in Kj+1→ℓK_j+1→ under f, then the induction hypothesis yields that DPj+1[R−R′,(ri−#f(Kj(i)))i∈M]DP_j+1[R-R ,(r_i-\# r_f(N_K_j(i)))_i∈ M] has value at least w′w . Thus, the right-hand side of (41) is at least μ^f(Kj)+w′=μ^f(Kj→ℓ)=w μ_f(K_j)+w = μ_f(K_j→ )=w, as desired. Suppose now that DPj[R,]=wDP_j[R,r]=w for some integer w. We are going to construct a labeling of G satisfying conditions (a)–(c). Let R′∈[min|Kj|,R]R ∈[ \|K_j|,R\] and f∈ℱjR′f _j^R be the values under which the right-hand side of (41) takes its maximum (namely, w) in the computation for DPj[R,]DP_j[R,r]. Let w′w denote the value of DPj+1[R−R′,(ri−#f(Kj(i)))i∈M]DP_j+1[R-R ,(r_i-\# r_f(N_K_j(i)))_i∈ M]; then we must have w=μ^f∪fM(Kj)+w′w= μ_f∪ f_M(K_j)+w , due to the computation in (41). By induction, we know that there exists a labeling f′f of G extending fMf_M for which (a’) #f′(Kj+1→ℓ)=R−R′\# r_f (K_j+1→ )=R-R , (b’) #f′(Kj+1→ℓ(i))=ri−#f(Kj(i))\# r_f (N_K_j+1→ (i))=r_i-\# r_f(N_K_j(i)) for all i∈Mi∈ M, and (c’) μ^f′(Kj+1→ℓ)=w′ μ_f (K_j+1→ )=w . Define f f as an arbitrary labeling of G that coincides with f over KjK_j, with f′f over Kj+1→ℓK_j+1→ , and with fMf_M over M. First, there are (R−R′)(R-R ) red agents in Kj+1→ℓK_j+1→ by (a’) and R′R red agents in KjK_j under f f (because f∈ℱjR′f _j^R ), so (a) holds for f f. Second, each modulator agent i∈Mi∈ M has exactly rir_i red neighbors in Kj→ℓK_j→ due to (b’). Third, the number of agents with majority-red neighborhood under f f is w′w in Kj+1→ℓK_j+1→ due to (c’), and thus μ^f^(Kj→ℓ)=w′+μ^f∪fM(Kj)=w μ_ f(K_j→ )=w + μ_f∪ f_M(K_j)=w. Hence, f f fulfills conditions (a)–(c), as required. This shows the claim for j∈[ℓ−1]j∈[ -1]. ◀ Running Time. Each cell in each table DPjDP_j can be computed in n(2k)n^O (2^k ) time where n=|N|n=|N|, as we exhaustively try all labelings in ℱjRF_j^R. There are n⋅nk∈n(k)n· n^k∈ n^O (k ) different cells for every table, and overall (n)O (n ) different tables. That is, the dynamic programming procedure runs in n(2k)n^O (2^k ) time, and requires n(k)n^O (k ) space, as it is enough to store tables only for two consecutive cliques KjK_j and Kj+1K_j+1. As we compute the table for each of the 2(k)2^O (k ) possible labelings fMf_M for M, the running time of the algorithm is 2(k)⋅n(2k)2^O (k )· n^O (2^k ). ∎ The next result shows that the running time of the algorithm in Theorem˜8 cannot be improved to obtain an FPT algorithm with parameter dcg(G)dcg(G), since the problem is W[1]-hard. Its proof relies on a reduction from the Multidimensional Subset Sum problem whose input consists of an integer d, a set =1,…,nS=\s_1,…,s_n\ of d-dimensional vectors from ℕdN^d, and a target vector ∈ℕdt ^d; the task is to decide whether there exists a subset ′⊆S for which ∑∈′= _s s=t. This problem is known to be W[1]-hard with parameter d even if its input is encoded in unary (Ganian, Klute, and Ordyniak 2021). Theorem 9. q-Majority Illusion is W[1]-hard when parameterized by the distance to cluster graph dcg(G)dcg(G) of the social network G. Proof. We present a parameterized reduction from the unary-encoded version of Multidimensional Subset Sum; let I=(d,,)I=(d,S,t) be our input instance with =1,…,nS=\s_1,…,s_n\. Observe first that we may assume w.l.o.g. that d is odd, as otherwise we can increase d by one, appending a coordinate with value 0 to each vector in ∪S∪\t\. Second, we may also assume that each coordinate of t is positive: this can be achieved by adding a sufficiently large vector ∈ℕdv ^d satisfying >∑∈v> _s s) to the set S and also to the target vector t, this way ensuring that any solution will contain v. Third, we can also assume that each coordinate of v is divisible by 2d+62d+6 (in particular, ||≥2d+6|v|≥ 2d+6) for each ∈∪tv ∪\t\, as otherwise we can simply multiply each vector in ∪S∪\t\ by 2d+62d+6. Fourth, we may additionally assume that not only ≤∑∈t≤ _s s but also 2<∑∈2t< _s s holds, as otherwise we can add a vector ′>t >t to S which can never be contained in a solution. We create an instance J=(N,G,q)J=(N,G,q) of q-Majority Illusion as follows. Construction. Let us introduce some notation. We will denote by Σ=∑i=1nis_ = _i=1^ns_i the sum of all input vectors, and we define integers α=2|Σ|+d+1α=2|s_ |+d+1 and nα=|Σ|−||−d+22n_α=|s_ |-|t|- d+22. For each i∈[nα]i∈[n_α], we define a clique AiA_i over exactly 2α2α agents. The agents in AiA_i will not be connected to any agent outside AiA_i except for i=1i=1. Next, for each i∈[n]i∈[n], we define a clique KiK_i of size 2|i|2|s_i| over agent set ⋃ ⋅ j=0dKij # $ $ -9.4445pt 2.0$ ·$ # $ $ -9.4445pt 2.0$ ·$ # $ $ -6.75699pt 2.0$ ·$ # $ $ -4.96532pt 2.0$ ·$ _j=0^dK_i^j, where |Ki0|=|i||K_i^0|=|s_i| and |Kij|=i[j]|K_i^j|=s_i[j] for each j∈[d]j∈[d]. Finally, we add a set M=m0,m1,…,mdM=\m_0,m_1,…,m_d\ of modulator agents. We connect m0m_0 to each agent in K:=⋃i∈[n],j∈[d]KijK:= _i∈[n],j∈[d]K_i^j. Next, for each j∈[d]j∈[d] we connect mjm_j to each agent in ⋃i∈[n]Kij _i∈[n]K_i^j, as well as to exactly Σ[j]−2[j]+1s_ [j]-2t[j]+1 agents from A1A_1 in a way that no two agents in A1A_1 are connected to more than one modulator agent. Note that this is possible, because ∑j∈[d](Σ[j]−2[d]+1)=|Σ|−2||+d>0 _j∈[d](s_ [j]-2t[d]+1)=|s_ |-2|t|+d>0. This finishes the definition of the social network G over the set N of agents; note that |N|=2α⋅nα+2|Σ|+d|N|=2α· n_α+2|s_ |+d. We set q such that q|N|=2α⋅nα+2||+dq|N|=2α· n_α+2|t|+d. Observe that the constructed social network has cluster deletion number at most d+1d+1, because deleting all modulator agents from G leaves a collection of disjoint cliques. Thus, the presented reduction is a parameterized one. Correctness. We are going to show that I is a yes-instance of Multidimensional Subset Sum if and only if J is a yes-instance of q-Majority Illusion. Assume first that there are at least q|N|q|N| agents under majority illusion for some red–blue labeling f (with blue being the majority color). We need the following observation, obtained by simple counting: Claim 14. Let C be a clique of even size whose each agent has at most one red neighbor outside C. If it contains fewer than |C|/2|C|/2 red agents, then no agent in C is under majority illusion; if C contains exactly |C|/2|C|/2 red agents, then no red agent is under majority illusion. By Claim˜14 applied to the cliques AiA_i, i∈[nα]i∈[n_α], we know that either each of AiA_i contains at least α+1α+1 red agents, or the number of agents under majority illusion is at most 2α⋅(nα−1)+α+2|Σ|+d=2α⋅nα−1<q|N|. 2α·(n_α-1)+α+2|s_ |+d=2α· n_α-1<q|N|. Thus, there must be at least α+1α+1 red agents in each clique AiA_i, ensuring that all agents in these cliques are under majority illusion. Next, we show that #f(K∪M)≤||+d+1\# r_f(K∪ M)≤|t|+d+1 (42) as otherwise #f(N) \# r_f(N) ≥(α+1)nα+||+d+2 ≥(α+1)n_α+|t|+d+2 =(α−1)nα+2|Σ|−||≥#f(N) =(α-1)n_α+2|s_ |-|t|≥\# b_f(N) where the equality follows from our choice of nαn_α, and the last inequality from |K∪M|=2|Σ|+d+1|K∪ M|=2|s_ |+d+1. Let us say that some clique KiK_i, i∈[n]i∈[n], is selected, half-selected, or rejected by f if #f(Ki)\# r_f(K_i) is at least |Ki|/2=|i||K_i|/2=|s_i|, exactly |i|−1|s_i|-1, or less, respectively. By an analog of Claim˜14 for cliques where some agents can have two neighbors outside the clique, we get that if KiK_i is rejected, then no agent in it is under majority illusion; if KiK_i is half-selected, then at most |i||s_i| agents in KiK_i can be under majority illusion, whereas this is possible for all agents in a selected clique. Claim 15. There are exactly 2||2|t| agents under majority illusion in K, all in selected cliques of total size 2||2|t|. Proof. We first show that no clique in K is half-selected by f. Suppose for the sake of contradiction that KiK_i is such a clique. Then #f(Ki)=|i|−1\# r_f(K_i)=|s_i|-1 and the number of agents in KiK_i under majority illusion is |i|≤2|i|−(2d−6)|s_i|≤ 2|s_i|-(2d-6) by our assumption on |i||s_i|. Let β denote the number of red vertices in K∖KiK K_i; recall that by (42) we have β+|i|−1≤||+d+1β+|s_i|-1≤|t|+d+1. Then there are at most 2β2β agents under majority illusion in K∖KiK K_i. Thus, the number of agents in K under majority illusion is at most 2β+|i| 2β+|s_i| ≤2β+2|i|−(2d+6) ≤ 2β+2|s_i|-(2d+6) ≤2(||+d+2)−2d−6=2||−2 ≤ 2(|t|+d+2)-2d-6=2|t|-2 which yields that the total number of agents under majority illusion is 2α⋅nα+2||−2+(d+1)<q|N|2α· n_α+2|t|-2+(d+1)<q|N|, a contradiction. Thus, all cliques in K are either selected or rejected. Hence, the set of agents under majority illusion in K is exactly the agent set of all selected cliques. Since there are at most ||+d+1|t|+d+1 agents in K and each |i||s_i|, i∈[n]i∈[n], as well as |||t| are divisible by 2d+62d+6, we know that the maximum total size of selected cliques is 2||2|t|. Note that if the the total size these cliques is less than 2||2|t| or not all agents in them are under majority illusion, then the number of such agents in K is at most 2−(2d+6)2t-(2d+6), and we again reach a contradiction because this yields less than q|N|q|N| such agents in total. This proves the claim. ◀ Let ′S denote the set of vectors i∈s_i for which KiK_i is selected by f. By Claim˜15, we know that ∑i∈|i|=||. _s_i |s_i|=|t|. (43) Observe that agent m0m_0 is not under majority illusion, as it has 2|Σ|2|s_ | neighbors but at most ||+d+1<2||<|Σ||t|+d+1<2|t|<|s_ | holds by our assumptions. Hence, all other modulator vertices must be under majority illusion, resulting in exactly 2α⋅nα+2||+d=q|N|2α· n_α+2|t|+d=q|N| such agents in total. This means that each modulator agent mjm_j, j∈[d]j∈[d] needs at least [j]t[j] red neighbors as otherwise mim_i has at most Σ[j]−2[j]+1+([j]−1)=Σ[j]−[j]s_ [j]-2t[j]+1+(t[j]-1)=s_ [j]-t[j] red neighbors but at least Σ−[j]+1s_ -t[j]+1 blue neighbors. Using that [j]t[j] as well as |Kij||K_i^j| for each i∈[n]i∈[n] is divisible by 2d+62d+6, we get that mjm_j must have at least [j]t[j] neighbors in selected cliques. This means that ∑i∈′i[j]≥[j] _s_i s_i[j] [j] (44) holds for each j∈[d]j∈[d]. Taking into account (43) we get that equality must hold for each j∈[d]j∈[d] in (44). Hence, we obtain ∑∈′= _s s=t, proving that ′S is a solution to our instance I of Multidimensional Subset Sum. For the other direction, let us now assume that ′⊆S is a solution for I. We create a red–blue labeling f with majority color blue as follows. We color exactly α+1α+1 agents red in each AiA_i, i∈[nα]i∈[n_α]; we take care to color red all agents in AiA_i connected to any modulator agent (it is easy to check that there are not more than |Ai|/2|A_i|/2 such agents). This yields 2α⋅nα2α· n_α agents under majority illusion in these cliques. Next, we color all modulator vertices as well as all agents in ⋃Kij:i∈′,j∈[d] \K_i^j:s_i ,j∈[d]\ red. This way, each modulator agent mjm_j, j∈[d]j∈[d], has exactly [j]t[j] red neighbors in K and is therefore under majority illusion. Finally, all agents in KiK_i with i∈′s_i are under majority illusion, because in each such clique exactly half of the agents are red, and moreover, each red agent has two red neighbors (namely, two modulator agents) outside the clique. This yields in total exactly 2α⋅nα+2||+d=q|N|2α· n_α+2|t|+d=q|N| agents under majority illusion. It remains to check that blue is indeed the majority color under f. Note that #f(N) \# r_f(N) =(α+1)nα+||+d+1 =(α+1)n_α+|t|+d+1 =(α−1)nα+2|Σ|−||−1=#f(N)−1 =(α-1)n_α+2|s_ |-|t|-1=\# b_f(N)-1 which proves the correctness of the reduction. ∎ We conclude with an FPT algorithm for the parameterization by the cluster edge deletion number, that is, the minimum number of edges we need to remove to obtain a disjoint union of cliques. Theorem 10. q-Majority Illusion is in FPT when parameterized by the cluster edge deletion number cdn(G)cdn(G) of the social network G. Proof. Let F be a set of k=cdn(G)k=cdn(G) edges such that G−FG-F is a disjoint union of cliques K1,…,KℓK_1,…,K_ , and let W be the set of all endpoints of the edges in F; note that |W|≤2k|W|≤ 2k. Since each KjK_j is a clique that contains no edge of F, every edge of F joins two distinct cliques. We record two immediate consequences: (i) every agent in N∖WN W has all of its neighbors inside its own clique; and (i) for every agent w∈Ww∈ W, each neighbor of w lying outside its own clique is an endpoint of an edge of F, and hence belongs to W. As in the proof of Theorem˜8, our algorithm first guesses the labeling fWf_W of W (there are at most 22k2^2k of them) and then extends fWf_W by dynamic programming over the cliques K1,…,KℓK_1,…,K_ . The decisive difference lies in property (i): once fWf_W is fixed, the number of red and blue neighbors that any agent w∈Ww∈ W has outside its own clique is a constant determined by fWf_W. Thus, the status of every agent—including those in W—is determined locally, within a single clique, and we no longer need the vector r recording the red neighbors of the modulator agents across cliques. A single counter for the total number of red agents suffices; this is exactly what turns the XP algorithm into an FPT one. Let Kj→ℓ=Kj∪⋯∪KℓK_j→ =K_j∪·s∪K_ . For every clique j∈[ℓ]j∈[ ] we maintain a table DPjDP_j which stores a value DPj[R]DP_j[R] for each R∈[⌊|N|/2⌋]0R∈[ |N|/2 ]_0, interpreted as the number of red agents in Kj→ℓK_j→ . The value DPj[R]DP_j[R] stores the maximum number of agents in Kj→ℓK_j→ with a majority-red neighborhood over all extensions f of fWf_W with #f(Kj→ℓ)=R\# r_f(K_j→ )=R. Relevant Labelings of a Clique. Fix a clique KjK_j. By property (i), all agents in Kj∖WK_j W are pairwise twins. By Claim˜12, swapping the labels of two such twins preserves the number of agents with a majority-red neighborhood; moreover, since the swap affects only agents in KjK_j, it preserves this number within KjK_j as well. Hence, the number of agents in KjK_j with a majority-red neighborhood depends only on fWf_W and on the number of red agents in KjK_j. Accordingly, for each feasible red count R′R we let ℱjR′F_j^R contain a single representative labeling of the agents Kj∖WK_j W obtained by coloring any R′−#fW(W∩Kj)R -\# r_f_W(W∩K_j) of them red; this set is empty (and the corresponding maximum is −∞-∞) unless #fW(W∩Kj)≤R′≤#fW(W∩Kj)+|Kj∖W|.\# r_f_W(W∩K_j)\;≤\;R \;≤\;\# r_f_W(W∩K_j)+|K_j W|. In particular |ℱjR′|≤1|F_j^R |≤ 1, so KjK_j has only (|Kj|)O (|K_j| ) relevant labelings in total—in contrast to the bound |N|(2k)|N|^O (2^k ) of Theorem˜8. Computation. The base case j=ℓj= is computed as DPℓ[R]=maxf∈ℱℓRμ^f∪fW(Kℓ),DP_ [R]= _f _ ^R μ_f∪ f_W(K_ ), where each μ^f∪fW(Kℓ) μ_f∪ f_W(K_ ) is evaluated directly: an agent a in Kℓ∖WK_ W sees only Kℓ∖aK_ \a\, and an agent w∈W∩Kℓw∈ W∩K_ sees, in addition, its red and blue neighbors outside KℓK_ , whose number is fixed by fWf_W thanks to property (i). For j∈[ℓ−1]j∈[ -1], we have DPj[R]=maxR′∈[min|Kj|,R]0maxf∈ℱjR′(μ^f∪fW(Kj)+DPj+1[R−R′]).DP_j[R]=\\ _R ∈[ \|K_j|,R\]_0\ _f _j^R ( μ_f∪ f_W(K_j)+DP_j+1[R-R ] ). (45) Once DP1DP_1 is computed, we return yes if and only if there is some R∈[⌊|N|−12⌋]0R∈ [ |N|-12 ]_0 with DP1[R]>q⋅|N|.DP_1[R]\;>\;q·|N|. Our choice of R guarantees that blue is the (strict) majority color, so an agent is under majority illusion exactly when it has a majority-red neighborhood; since K1→ℓ=NK_1→ =N, the value DP1[R]DP_1[R] then equals the number of agents under majority illusion. Correctness thus follows from the next claim for j=1j=1. Claim 16. For all j∈[ℓ]j∈[ ] and R∈[⌊|N|/2⌋]0R∈[ |N|/2 ]_0, we have DPj[R]=wDP_j[R]=w (with w∈ℕw ) if and only if there exists a labeling f of G extending fWf_W such that (a) #f(Kj→ℓ)=R\# r_f(K_j→ )=R, and (b) μ^f(Kj→ℓ)=w μ_f(K_j→ )=w. Proof. The proof is by induction on decreasing j and is identical in structure to that of Claim˜13, with two simplifications: there is no condition on the vector r, and—by property (i)—the contribution μ^f∪fW(Kj) μ_f∪ f_W(K_j) of a single clique is fully determined by fWf_W and by #f(Kj)\# r_f(K_j), the status of every agent of W∩KjW∩K_j included. For j=ℓj= , given a labeling f satisfying (a)–(b), the definition of ℱℓRF_ ^R provides a representative whose restriction to the agents in Kℓ∖WK_ W has the same number of reds as f; by Claim˜12, it also yields the same number of agents with a majority-red neighborhood. This implies DPℓ[R]≥wDP_ [R]≥ w, and the converse direction is immediate by extending any maximizing representative arbitrarily over N. For j∈[ℓ−1]j∈[ -1], suppose that f satisfies (a)–(b), and let R′=#f(Kj)R =\# r_f(K_j). The restriction of f to KjK_j is equivalent to some f′∈ℱjR′f _j^R with μ^f′∪fW(Kj)=μ^f(Kj) μ_f ∪ f_W(K_j)= μ_f(K_j), and #f(Kj+1→ℓ)=R−R′\# r_f(K_j+1→ )=R-R ; by the induction hypothesis DPj+1[R−R′]≥μ^f(Kj+1→ℓ)DP_j+1[R-R ]≥ μ_f(K_j+1→ ), so the right-hand side of (45) is at least μ^f(Kj)+μ^f(Kj+1→ℓ)=w μ_f(K_j)+ μ_f(K_j+1→ )=w. Conversely, if R′R and f∈ℱjR′f _j^R attain the maximum w in the recurrence, the induction hypothesis supplies a labeling f′f of G witnessing DPj+1[R−R′]DP_j+1[R-R ]; combining f′f on Kj+1→ℓK_j+1→ , f on the agents of Kj∖WK_j W, and fWf_W on W gives a labeling of G satisfying (a)–(b), because every clique’s contribution is computed independently of the others’ once fWf_W is fixed. ◀ Running Time. For a fixed fWf_W and clique KjK_j, the value μ^f∪fW(Kj) μ_f∪ f_W(K_j) of each of the (|Kj|)O (|K_j| ) relevant labelings is computed in (|N|)O (|N| ) time, so all per-clique contributions are tabulated in (|N|2)O (|N|^2 ) time overall. Each of the (|N|)O (|N| ) tables has (|N|)O (|N| ) cells, and each cell is evaluated by taking a maximum over (|N|)O (|N| ) values of R′R ; thus the dynamic program runs in (|N|3)O (|N|^3 ) time per choice of fWf_W and uses (|N|)O (|N| ) space, as only two consecutive tables need to be stored. As there are at most 22k2^2k labelings fWf_W of W, the total running time is 2(k)⋅|N|(1)2^O (k )·|N|^O (1 ). ∎ 8 Conclusions We investigated how the complexity of q-Majority Illusion changes with various parameters of the underlying social network G; our results outline the limits of tractability in terms of such graph parameters, providing us with efficient algorithms and, in many cases, matching lower bounds. Our results show that to render the problem tractable, one of three conditions must be satisfied: a) G is within bounded edge-distance from some graph class where the problem is polynomial-time solvable (as in feedback-edge set or cluster edge deletion number), b) G is within a bounded vertex-distance from components of bounded size (as in vertex integrity), or c) G consists of a bounded number of well-structured blocks (as in neighborhood diversity). We left open the complexity of q-Majority Illusion when parameterized by the twin-cover number of G: by Theorem˜8, the problem is in XP when parameterized by the number of agents whose removal yields a cluster graph, and by Theorem˜10, the problem is in FPT when parameterized by the number of edges whose removal yields a cluster graph. As the twin-cover number is between these two parameterizations, it would be interesting to see if this additional twin structure of the cliques allows for an FPT algorithm. More generally, what kind of other structural properties allow for FPT algorithms for our problem? Acknowledgments This project was co-funded by the European Union under the project Robotics and Advanced Industrial Production (reg. no. CZ.02.01.01/00/22_008/0004590). The second author is supported by the Hungarian Academy of Sciences under its Momentum Programme (LP2021-2) and its János Bolyai Research Scholarship. Most of this work was done while the first author was at AGH University of Krakow. References Asch (1951) Asch, S. 1951. Effects of Group Pressure Upon the Modification and Distortion of Judgments. In Groups, leadership and men; research in human relations, 177–190. Auletta, Ferraioli, and Greco (2020) Auletta, V.; Ferraioli, D.; and Greco, G. 2020. On the Complexity of Reasoning About Opinion Diffusion Under Majority Dynamics. Artificial Intelligence, 284: 103288. Banerjee (1992) Banerjee, A. V. 1992. A Simple Model of Herd Behavior. The Quarterly Journal of Economics, 107(3): 797–817. Bodlaender et al. (2020) Bodlaender, H. L.; Hanaka, T.; Jaffke, L.; Ono, H.; Otachi, Y.; and van der Zanden, T. C. 2020. Hedonic Seat Arrangement Problems. In Seghrouchni, A. E. F.; Sukthankar, G.; An, B.; and Yorke-Smith, N., eds., Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’20, 1777–1779. IFAAMAS. Bredereck, Chen, and Woeginger (2013) Bredereck, R.; Chen, J.; and Woeginger, G. J. 2013. Are There Any Nicely Structured Preference Profiles Nearby? In Rossi, F., ed., Proceedings of the 23rd International Joint Conference on Artificial Intelligence, IJCAI ’13, 62–68. IJCAI/AAAI. Bredereck and Elkind (2017) Bredereck, R.; and Elkind, E. 2017. Manipulating Opinion Diffusion in Social Networks. In Sierra, C., ed., Proceedings of the 20th International Joint Conference on Artificial Intelligence, IJCAI ’17, 894–900. ijcai.org. Bredereck, Jacobs, and Kellerhals (2020) Bredereck, R.; Jacobs, L.; and Kellerhals, L. 2020. Maximizing the Spread of an Opinion in Few Steps: Opinion Diffusion in Non-Binary Networks. In Bessiere, C., ed., Proceedings of the 29th International Joint Conference on Artificial Intelligence, IJCAI ’20, 1622–1628. ijcai.org. Castiglioni et al. (2021) Castiglioni, M.; Ferraioli, D.; Gatti, N.; and Landriani, G. 2021. Election Manipulation on Social Networks: Seeding, Edge Removal, Edge Addition. Journal of Artificial Intelligence Research, 71: 1049–1090. Cialdini and Goldstein (2004) Cialdini, R. B.; and Goldstein, N. J. 2004. Social Influence: Compliance and Conformity. Annual Review of Psychology, 55: 591–621. Cinelli et al. (2021) Cinelli, M.; Morales, G. D. F.; Galeazzi, A.; Quattrociocchi, W.; and Starnini, M. 2021. The Echo Chamber Effect on Social Media. Proceedings of the National Academy of Sciences of the USA, 118(9): e2023301118. Cygan et al. (2015) Cygan, M.; Fomin, F. V.; Kowalik, Ł.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; and Saurabh, S. 2015. Parameterized Algorithms. Springer. Dippel et al. (2025) Dippel, J.; la Tour, M. D.; Niu, A.; Roy, S.; and Vetta, A. 2025. Eliminating Majority Illusion Is Easy. In Walsh, T.; Shah, J.; and Kolter, Z., eds., Proceedings of the 39th AAAI Conference on Artificial Intelligenc AAAI ’25, 13763–13770. AAAI Press. Dom et al. (2008) Dom, M.; Lokshtanov, D.; Saurabh, S.; and Villanger, Y. 2008. Capacitated Domination and Covering: A Parameterized Perspective. In Grohe, M.; and Niedermeier, R., eds., Proceedings of the 3rd International Workshop on Parameterized and Exact Computation, IWPEC ’08, volume 5018 of Lecture Notes in Computer Science, 78–90. Berlin, Heidelberg: Springer. Doucette et al. (2019) Doucette, J. A.; Tsang, A.; Hosseini, H.; Larson, K.; and Cohen, R. 2019. Inferring True Voting Outcomes in Homophilic Social Networks. Autonomous Agents and Multiagent Systems, 33(3): 298–329. Dvořák et al. (2017) Dvořák, P.; Eiben, E.; Ganian, R.; Knop, D.; and Ordyniak, S. 2017. Solving Integer Linear Programs With a Small Number of Global Variables and Constraints. In Sierra, C., ed., Proceedings of the 26th International Joint Conference on Artificial Intelligence, IJCAI ’17, 607–613. ijcai.org. Eiben, Ganian, and Ordyniak (2018) Eiben, E.; Ganian, R.; and Ordyniak, S. 2018. A Structural Approach to Activity Selection. In Lang, J., ed., Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI ’18, 203–209. ijcai.org. Eisenbrand et al. (2025) Eisenbrand, F.; Hunkenschröder, C.; Klein, K.; Koutecký, M.; Levin, A.; and Onn, S. 2025. Sparse Integer Programming Is Fixed-Parameter Tractable. Mathematics of Operations Research, 50(3): 2141–2156. Faliszewski et al. (2018) Faliszewski, P.; Gonen, R.; Koutecký, M.; and Talmon, N. 2018. Opinion Diffusion and Campaigning on Society Graphs. In Lang, J., ed., Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI ’18, 219–225. ijcai.org. Ferrara et al. (2016) Ferrara, E.; Varol, O.; Davis, C. A.; Menczer, F.; and Flammini, A. 2016. The Rise of Social Bots. Communications of the ACM, 59(7): 96–104. Fioravantes, Gahlawat, and Melissinos (2025) Fioravantes, F.; Gahlawat, H.; and Melissinos, N. 2025. Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size. In Walsh, T.; Shah, J.; and Kolter, Z., eds., Proceedings of the 39th AAAI Conference on Artificial Intelligence, AAAI ’25’, 13847–13855. AAAI Press. Fioravantes et al. (2026) Fioravantes, F.; Gahlawat, H.; Melissinos, N.; and Schierreich, Š. 2026. Individual Rationality in Constrained Hedonic Games: Additively Separable and Fractional Preferences. In Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’26, 2848–2857. Richland, SC: IFAAMAS. Fioravantes et al. (2025a) Fioravantes, F.; Knop, D.; Křišťan, J. M.; Melissinos, N.; Opler, M.; and Vu, T. A. 2025a. Solving Multiagent Path Finding on Highly Centralized Networks. In Walsh, T.; Shah, J.; and Kolter, Z., eds., Proceedings of the 39th AAAI Conference on Artificial Intelligence, AAAI ’25’, 23186–23193. AAAI Press. Fioravantes et al. (2025b) Fioravantes, F.; Lahiri, A.; Lauerbach, A.; Sabater, L.; Sieper, M. D.; and Wolf, S. 2025b. Eliminating Majority Illusion. In Das, S.; Nowé, A.; and Vorobeychik, Y., eds., Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’25, 749–757. IFAAMAS. Ganian, Klute, and Ordyniak (2021) Ganian, R.; Klute, F.; and Ordyniak, S. 2021. On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem. Algorithmica, 83: 297–336. Ganian and Korchemna (2021) Ganian, R.; and Korchemna, V. 2021. The Complexity of Bayesian Network Learning: Revisiting the Superstructure. In Ranzato, M.; Beygelzimer, A.; Dauphin, Y. N.; Liang, P.; and Vaughan, J. W., eds., Proceedings of the 34th Annual Conference on Neural Information Processing Systems 2021, NeurIPS ’21, 430–442. Garimella et al. (2018) Garimella, K.; Morales, G. D. F.; Gionis, A.; and Mathioudakis, M. 2018. Political Discourse on Social Media: Echo Chambers, Gatekeepers, and the Price of Bipartisanship. In Champin, P.; Gandon, F.; Lalmas, M.; and Ipeirotis, P. G., eds., Proceedings of the 2018 World Wide Web Conference, W ’18, 913–922. ACM. Grandi (2017) Grandi, U. 2017. Social Choice and Social Networks. In Endriss, U., ed., Trends in Computational Social Choice, 169–184. AI Access. Grandi et al. (2025) Grandi, U.; Kanesh, L.; Lisowski, G.; Ramanujan, M. S.; and Turrini, P. 2025. A Complexity-Theoretic Analysis of Majority Illusion in Social Networks. Journal of Artificial Intelligence Research, 83: 26. Grüttemeier and Komusiewicz (2020) Grüttemeier, N.; and Komusiewicz, C. 2020. Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis. In Bessiere, C., ed., Proceedings of the 29th International Joint Conference on Artificial Intelligence, IJCAI ’20, 4245–4251. ijcai.org. Guo et al. (2022) Guo, M.; Li, J.; Neumann, A.; Neumann, F.; and Nguyen, H. 2022. Practical Fixed-Parameter Algorithms for Defending Active Directory Style Attack Graphs. In Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI ’22, 9360–9367. AAAI Press. Jana and Roy (2026) Jana, S.; and Roy, S. 2026. Eliminating Illusion in Directed Networks. arXiv:2604.02395. Kempe, Kleinberg, and Tardos (2015) Kempe, D.; Kleinberg, J. M.; and Tardos, É. 2015. Maximizing the Spread of Influence Through a Social Network. Theory of Computing, 11: 105–147. Knop, Schierreich, and Suchý (2026) Knop, D.; Schierreich, Š.; and Suchý, O. 2026. Balancing the Spread of Two Opinions in Sparse Social Networks. Artificial Intelligence, 357: 104563. Lerman, Yan, and Wu (2016) Lerman, K.; Yan, X.; and Wu, X.-Z. 2016. The "Majority Illusion" in Social Networks. PLoS ONE, 11(2): 1–13. Musco, Musco, and Tsourakakis (2018) Musco, C.; Musco, C.; and Tsourakakis, C. E. 2018. Minimizing Polarization and Disagreement in Social Networks. In Champin, P.; Gandon, F.; Lalmas, M.; and Ipeirotis, P. G., eds., Proceedings of the 2018 World Wide Web Conference, W ’18, 369–378. ACM. Schierreich (2023) Schierreich, Š. 2023. Maximizing Influence Spread Through a Dynamic Social Network (Student Abstract). In Williams, B.; Chen, Y.; and Neville, J., eds., Proceedings of the 37th AAAI Conference on Artificial Intelligence, AAAI ’23, 16316–16317. AAAI Press. UNESCO (2023) UNESCO. 2023. Survey on the Impact of Online Disinformation and Hate Speech. Technical report, United Nations Educational, Scientific and Cultural Organization. Venema-Los, Christoff, and Grossi (2025) Venema-Los, M.; Christoff, Z.; and Grossi, D. 2025. On the Graph Theory of Majority Illusions: Theoretical Results and Computational Experiments. Autonomous Agents and Multi-Agent Systems, 39(2): 39. Vosoughi, Roy, and Aral (2018) Vosoughi, S.; Roy, D.; and Aral, S. 2018. The Spread of True and False News Online. Science, 359(6380): 1146–1151. Wilder and Vorobeychik (2018) Wilder, B.; and Vorobeychik, Y. 2018. Controlling Elections Through Social Influence. In André, E.; Koenig, S.; Dastani, M.; and Sukthankar, G., eds., Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’18, 265–273. IFAAMAS. Woolley and Howard (2018) Woolley, S. C.; and Howard, P. N. 2018. Computational Propaganda: Political Parties, Politicians, and Political Manipulation on Social Media. Oxford University Press. ISBN 9780190931407. Yang et al. (2020) Yang, K.; Varol, O.; Hui, P.; and Menczer, F. 2020. Scalable and Generalizable Social Bot Detection Through Data Selection. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, AAAI ’20, 1096–1103. AAAI Press.