problem  Input: Question:

# Eliminating Majority Illusion is Easy

Jack Dippel McGill University<EMAIL_ADDRESS>Max Dupré la Tour
McGill University<EMAIL_ADDRESS>April Niu McGill University:
<EMAIL_ADDRESS>Sanjukta Roy University of Leeds<EMAIL_ADDRESS>Adrian Vetta McGill University<EMAIL_ADDRESS>
###### Abstract

Majority Illusion is a phenomenon in social networks wherein the decision by
the majority of the network is not the same as one’s personal social circle’s
majority, leading to an incorrect perception of the majority in a large
network. In this paper, we present polynomial-time algorithms which can
eliminate majority illusion in a network by altering as few connections as
possible. Additionally, we prove that the more general problem of ensuring all
neighbourhoods in the network are at least a $p$-fraction of the majority is
NP-hard for most values of $p$.

##  1 Introduction

Perceptions are liable to become distorted on a social network. An exemplar of
this is the friendship paradox [10]: on average, a person has fewer friends
than their friends do.111This is a simple consequence of the fact that a
higher degree node appears in more neighbourhoods than a lower degree node.
Similarly, on average, a researcher is less productive than their co-authors
[8, 3]. This network characteristic, whereby local observations can lead to
erroneous conclusions regarding a global state, was dubbed majority illusion
by Lerman et al. [16]. This nomenclature relates to situations where a
minority viewpoint is perceived to be the majority viewpoint [23].

One of the simplest manifestation of majority illusion concerns election.
Let’s model a two-party election by a graph $G=(V,E)$ where each node
represents a voter and each edge connects two voters that are neighbours (or
friends). Furthermore, imagine party preference is given by a colouring
function $f:V\rightarrow\\{B,R\\}$. If there are more blue nodes than red
nodes then we say blue is the majority. A node $v\in V$ is then under
(majority) illusion if it has strictly more red neighbours than blue
neighbours. It is easy to construct instances where some nodes are under
majority illusion; see Figure 1(a). Much more surprising is the existence of
instances where every node is under illusion; see Figure 1(b).

$(a)$$v_{8}$$v_{4}$$v_{2}$$v_{1}$$v_{5}$$v_{6}$$v_{3}$$v_{7}$

$(b)$$v_{9}$$v_{5}$$v_{3}$$v_{1}$$v_{2}$$v_{6}$$v_{7}$$v_{4}$$v_{8}$

Figure 1: In network (a) there are two nodes, $v_{1}$ and $v_{2}$, under
majority illusion; in network (b) every node suffers illusion!

Network topology can have a big impact on misinformation. Indeed, electoral
networks are very susceptible to majority illusion because their underlying
network topology has a social determinant. For example, homophily, the
tendency for humans to connect with similar people, contributes to the
creation of information bubbles and polarization [19].

Another topical example of majority illusion concerns vaccinations [14]. Here
node colours may indicate vaccinated or unvaccinated. If a personal decision
to vaccinate oneself is influenced by the actions of people in your local
social network then misinformation here may have significant consequences.
Moreover, a smaller number of influential high degree nodes may suffice to
cause major distortions. An illusion can occur even when there are more than
two alternatives and each node selects one alternative. Then, a node under
illusion has strictly less blue neighbors (i.e., the neighbors select the
winning alternative) compared to red neighbors (denotes the set of all non-
winning alternatives). Indeed, this observation indicates the relevance of
majority illusion to advertising, campaigning, and influence maximization [2,
26]. Moreover, the effects of illusion have been studied in many disparate
areas, including voting theory [1, 4, 6, 24], participatory budgeting and the
allocation of public goods [15, 25].

These applications highlighting the importance of creating social networks
that give everyone fair and unbiased information [14]. That is the focus of
this paper. Specifically, to determine whether or not majority illusion can be
eliminated in a network? If so, can we do this optimally in polynomial time?

###  1.1 The Illusion Elimination Problem

To answer these questions we first study a class of majority illusion
elimination problems. We are given a social network $G=(V,E)$, a non-negative
integer $k$, and a voting function $f:V\rightarrow\\{B,R\\}$, where blue is
the strict _majority_. Can we eliminate (majority) illusion, for every node,
by altering (adding and/or deleting) at most $k$ edges? That is, after the
alteration, no node can have a strict majority of red nodes in its
neighbourhood.

Observe that, since we may remove edges of $G$ or add non-edges of $G$, there
are three variants of the majority illusion elimination problems where we can
only add edges, only remove edges, or both add and remove edges. Formally,
this gives the following three decision problems, respectively:

It may be helpful to illustrate these three problems using the two examples we
encountered in Figure 1. Figure 2 considers the example from Figure 1(a) where
only two nodes, $v_{1}$ and $v_{2}$, are under majority illusion. It presents
optimal solutions that require the minimum number of edge alterations for the
three problems (that is, solutions to optimization versions of the above
decision problems). Similarly, Figure 3 considers the example Figure 1(b)
where every node is under illusion and gives the three corresponding optimal
solutions to eliminate illusion.

$(a)$$v_{8}$$v_{4}$$v_{2}$$v_{1}$$v_{5}$$v_{6}$$v_{3}$$v_{7}$

$(b)$$v_{8}$$v_{4}$$v_{2}$$v_{1}$$v_{5}$$v_{6}$$v_{3}$$v_{7}$

$(c)$$v_{8}$$v_{4}$$v_{2}$$v_{1}$$v_{5}$$v_{6}$$v_{3}$$v_{7}$

$(d)$$v_{8}$$v_{4}$$v_{2}$$v_{1}$$v_{5}$$v_{6}$$v_{3}$$v_{7}$

Figure 2: In (a) only $v_{1}$ and $v_{2}$ are under majority illusion. An
optimal solution to the MIAE problem, adding just $2$ edges, is shown in (b);
an optimal solution to the MIRE problem, removing $5$ edges, is shown in (c);
an optimal solution to the MIE problem, adding $1$ edge and removing $1$ edge,
is shown in (d).

$(a)$$v_{9}$$v_{5}$$v_{3}$$v_{1}$$v_{2}$$v_{6}$$v_{7}$$v_{4}$$v_{8}$

$(b)$$v_{9}$$v_{5}$$v_{3}$$v_{1}$$v_{2}$$v_{6}$$v_{7}$$v_{4}$$v_{8}$

$(c)$$v_{9}$$v_{5}$$v_{3}$$v_{1}$$v_{2}$$v_{6}$$v_{7}$$v_{4}$$v_{8}$

$(d)$$v_{9}$$v_{5}$$v_{3}$$v_{1}$$v_{2}$$v_{6}$$v_{7}$$v_{4}$$v_{8}$

Figure 3: In (a) every node is under majority illusion. An optimal solution to
the MIAE problem, adding $11$ edges, is shown in (b); an optimal solution to
the MIRE problem, requiring the removal of all $12$ edges, is shown in (c); an
optimal solution to the MIE problem, adding $3$ edges and removing $3$ edges,
is shown in (d).

We remark that the assumption that blue party is strict majority is not
necessary. However the assumption of strictness ensures that, for all three
problems, it is always feasible to alter the graph to eliminate majority
illusion.

Grandi et al. [12] left unresolved the computational complexity of these
problems. Instead, rather than completely eliminating illusion at every node,
they showed it was NP-complete to partially eliminate illusion for a fraction
of the nodes. In particular, they studied the following $q$-partial (majority)
illusion elimination problem: can at most a $q$-fraction of the nodes be left
under illusion after altering (adding and/or deleting) at most $k$ edges in
$G$.

They proved this problem is NP-complete for $q\in(0,1)$. Observe that the
MIAE, MIRE, and MIE problems correspond to the case $q=0$, that is, where no
nodes are allowed to be left under illusion. Therefore, the computational
complexity of the main problems of interest remained open and motivated this
work.

###  1.2 Our Contributions.

We make two contributions regarding illusion elimination in social networks.
First, we prove that the majority illusion elimination problem is solvable in
polynomial time for all three variants (MIAE, MIRE and MIE). Thus completely
eliminating majority illusion in a social network is easy. The result is very
surprising given, as described above, that the problem of partially
eliminating illusion is hard [12].

In our second contribution, we generalize the problem of eliminating majority
illusion and consider the problem of $p$-illusion. The majority illusion
elimination problems assume the blue party has at least $\frac{1}{2}$ the
votes. Suppose, instead, we do not assume the votes for the blue party and ask
if it is possible to ensure that every voter believes that the blue party has
at least a $p$-fraction of the ballots, where $p\in[0,1]$ is a rational
number. Thus, we define the _$p$ -Illusion problem_: Given a graph $G=(V,E)$,
a colouring function $f:V\rightarrow\\{B,R\\}$, and a rational number
$p\in[0,1]$, can we modify at most $k$ edges such that every node has at least
$p$-fraction of blue nodes in its neighbourhood? This question induces three
problems for $p$-Illusion (analogous to majority illusion elimination),
namely, $p$-IA, $p$-IR, and $p$-I,222We emphasize the distinction between the
$p$-I problem and the $q$-partial MIE problem or the $q$-majority illusion
problem of [12]. In $p$-I (and $p$-IA/$p$-IR) every node must have at least a
$p$-fraction of blue neighbors. In contrast, $q$-partial MIE eliminates the
illusion of any $(1-q)$-fraction of the nodes; and in the $q$-majority
illusion problem asks if at least $q$ fraction of the nodes be under illusion.
which as we prove are all polynomial time solvable for $p=\frac{1}{2}$.
However, the majority case $p=\frac{1}{2}$ is very special. We prove that
$p$-IA, $p$-IR, and $p$-I are all NP-complete for any rational $p\in[0,1]$
except for $p\in\\{0,\frac{1}{3},\frac{1}{2},\frac{2}{3},1\\}$.

An overview of the rest of the paper is as follows. In Section 1.3 we discuss
related works. In Section 2, we present preliminary results and observations
concerning illusion elimination. Our three polynomial time algorithms for
MIAE, MIRE, and MIE are then given in Sections 3, 4, and 5, respectively.
Finally, in Section 6 we prove the NP-completeness of the $p$-IA, $p$-IR and
$p$-I problems, for $p\notin\\{0,\frac{1}{3},\frac{1}{2},\frac{2}{3},1\\}$.

###  1.3 Related Work.

Several studies have delved into the dynamics of decision-making within social
networks and the manipulation of these networks, offering insights into
various related phenomena. The article by Grandi et al. [12] is the most
relevant, as it directly addresses the phenomenon of majority illusion in
social networks, where individuals perceive a majority opinion that does not
reflect the actual distribution of opinions. Through analysis and
experimentation, the authors propose methods for identifying and mitigating
majority illusion, offering valuable insights into the dynamics of opinion
formation and social influence in networked environments. The results in this
paper are based upon their model.

Liu et al. [18] explore the concept of “information gerrymandering” in
elections, where the strategic distribution of individuals within social
networks can influence voting outcomes. They introduces a metric called
influence assortment to quantify this phenomenon and demonstrates its
effectiveness in predicting voting outcomes in various network structures.

The effect of adding and/or deleting edges in a social network has been
investigated in several settings. For example, Castiglioni et al. [4] study
election control in social networks through the addition or removal of
connections between individuals. Their study proposes methods for
strategically manipulating network connections to influence election outcomes,
highlighting the potential for network topology to shape democratic processes.

By analyzing the impact of link additions on information diffusion and
exposure diversity, Becker et al. [2] propose methods to mitigate bias and
improve the accessibility of diverse viewpoints. Through empirical analysis
and simulations, their study provides insights into the potential of
structural interventions to promote fairness and inclusivity in online
information dissemination.

Kempe et al. [15] explore methods for inducing equilibria in networked public
goods games by modifying the structure of the network. Through mathematical
modeling and simulations, their research investigates strategies for promoting
cooperation and achieving desirable outcomes in public goods dilemmas. Their
work also proffers insights into the role of network topology in shaping
collective behavior.

Wilder and Vorobeychik [24] investigate opinion diffusion and campaigning
strategies on society graphs. Their research studies how opinions spread
through networks and the effectiveness of various campaigning approaches. They
focus on the dynamics of opinion formation and diffusion in social networks,
with the aim of understanding influence dynamics and designing effective
communication strategies.

Faliszewski et al. [9] examine techniques for controlling elections through
social influence. By manipulating the spread of information and opinions
within social networks, they consider strategies for influencing voter
behavior and election outcomes and provides insights into the potential for
social influence to shape electoral processes, highlighting the need for
understanding and addressing such dynamics in democratic systems.

In a recent work Fioravantes et al. [11] study the problem of eliminating
majority illusion by altering the color of at most $k$ vertices and show that,
unlike our edge editing problem, it is NP-hard and W[2]-hard with respect to
$k$. They present FPT algorithm parameterized by treewidth of the input graph
and PTAS for planar graphs.

##  2 Preliminaries

We begin by defining the following notations. Given a graph $G=(V,E)$, let $B$
be the set of blue nodes and $R$ the set of red nodes. For any node $v\in V$,
let $\Gamma(v)$ denote the neighbourhood of $v$, $r(v)=|\\{u\in
R:u\in\Gamma(v)\\}|$ be the number of red nodes in the neighbourhood of $v$,
and $b(v)=|\\{u\in B:u\in\Gamma(v)\\}|$ be the number of blue nodes in its
neighbourhood.

######  Definition (Illusion).

Let $G=(V,E)$ be a graph such that $\frac{|B|}{|V|}>p$. Then, a node $v\in V$
is under illusion if it has strictly less than $p$-fraction of blue neighbors,
i.e., $\frac{b(v)}{|\Gamma(v)|}<p$. When $p=1/2$, it is known as majority
illusion.

Equivalently, if $\frac{|B|}{|V|}<p$, then a node $v\in V$ is under illusion
if it has at least $p$-fraction of blue neighbors, i.e.,
$\frac{b(v)}{|\Gamma(v)|}\geq p$.

Next, we describe basic properties that optimal solutions to our three
majority illusion elimination problems must possess. For a node $v\in V$, if
$r(v)>b(v)$ then we say $v$ is in deficit; if $r(v)<b(v)$ then we say $v$ is
in surplus. So the task is to add/remove as few edges as possible so that no
node is in deficit.

We begin with the trivial observation that it is never of benefit to add an
edge between two red nodes.

######  Observation 1.

In an optimal solution $E^{\prime}$ to an instance $(V,E,f,k)$ of MIE or MIAE,
there are no edges of $E^{\prime}\setminus E$ between two red nodes.

###### Proof.

Assume there exist two red nodes $u,v$ with $uv\in E^{\prime}\setminus E$.
Then $E^{\prime}\setminus uv$ is also be a solution to the instance
$(V,E,f,k)$, because removing $uv$ can only decrease the ratio of red nodes to
blue nodes in both affected neighbourhoods. Thus $uv$ cannot be added in an
optimal solution. ∎

Analogously, it is never of benefit to remove an edge between two blue nodes.

######  Observation 2.

In an optimal solution $E^{\prime}$ to an instance $(V,E,f,k)$ of MIE or MIRE,
there are no edges of $E\setminus E^{\prime}$ between two blue nodes.

###### Proof.

Assume there exist two blue nodes $u,v$ with $uv\in E\setminus E^{\prime}$.
Then $E^{\prime}\cup uv$ is also a solution to the instance $(V,E,f,k)$,
because adding $uv$ can only decrease the ratio of red nodes to blue nodes in
both affected neighbourhoods. Thus $uv$ cannot be removed in an optimal
solution. ∎

We conclude this section with three more observations, one for each of our
three problems. The first, for the addition variant, essentially states that
for any red node, it is never beneficial to connect it to more new blue
neighbours than is absolutely necessary.

######  Lemma 1.

In an optimal solution $E^{\prime}$ to $(V,E,f,k)$ of MIAE, there are exactly
$\max(r(v)-b(v),0)$ edges of $E^{\prime}\setminus E$ incident to each red node
$v$.

###### Proof.

Suppose there are fewer than $\max(r(v)-b(v),0)$ edges of $E^{\prime}\setminus
E$ incident to some red node $v$. Then $N_{E^{\prime}}[v]$ is majority red,
contradicting the feasibility of $E^{\prime}$.

On the other hand, suppose there are more than $\max(r(v)-b(v),0)$ edges of
$E^{\prime}\setminus E$ incident to some red node $v$. Then, by Lemma 1, there
are more than $\max(r(v)-b(v),0)$ edges between $v$ and the set of blue nodes.
For any blue node $u$ with $uv\in E^{\prime}\setminus E$, observe that
$E^{\prime}\setminus uv$ must also be a solution to the instance $(V,E,f,k)$.
This is because removing $uv$ does not cause there to be more red nodes than
blue nodes in the neighbourhood of $v$, and it decreases the ratio of red
nodes to blue nodes in the neighbourhood of $u$. Thus $uv$ cannot be added in
an optimal solution, a contradiction. ∎

Similarly, for the removal variant, for any blue node, it is never beneficial
to disconnect it from more red neighbours than is absolutely necessary.

######  Lemma 2.

In an optimal solution $E^{\prime}$ to $(V,E,f,k)$ of MIRE, there are exactly
$\max(r(v)-b(v),0)$ edges of $E\setminus E^{\prime}$ incident to each blue
node $v$.

###### Proof.

Suppose there are fewer than $\max(r(v)-b(v),0)$ edges of $E\setminus
E^{\prime}$ incident to some blue node $v$. Then $N_{E^{\prime}}[v]$ is
majority red, contradicting the feasibility of $E^{\prime}$.

On the other hand, suppose there are more than $\max(r(v)-b(v),0)$ edges of
$E\setminus E^{\prime}$ incident to some blue node $v$. Then, by Lemma 2,
there are more than $\max(r(v)-b(v),0)$ edges between $v$ and the set of red
nodes. For some red node $u$ with $uv\in E\setminus E^{\prime}$, observe
$E^{\prime}\cup uv$ must also be a solution to the instance $(V,E,f,k)$. This
is because adding $uv$ does not cause there to be more red nodes than blue
nodes in the neighbourhood of $v$, and it decreases the ratio of red nodes to
blue nodes in the neighbourhood of $u$. Thus $uv$ cannot be removed in an
optimal solution. ∎

Finally, for the general majority illusion elimination problem, we have the
following more substantial observation.

######  Lemma 3.

There exists an optimal solution $E^{\prime}$ to an instance $(V,E,f,k)$ of
MIE with no edges of $E^{\prime}\setminus E$ incident to any red node, and no
edges of $E\setminus E^{\prime}$ incident to any blue node.

###### Proof.

We provide a method of transforming any optimal solution $E^{\prime}$ to an
instance $(V,E,f,k)$ of MIE into an optimal solution of the desired form.

Suppose there is an edge of $E^{\prime}\setminus E$ incident to some red node
$v$. By 1, this edge connects $v$ to some node $u\in B$. $E^{\prime}$ is an
optimal solution, meaning $N_{E^{\prime}}(v)$ contains at least as many blue
nodes as red nodes. Removing $uv$ from $E^{\prime}$ would reduce the size of
$|E\setminus E^{\prime}|+|E^{\prime}\setminus E|$, and result in one fewer
blue node in $N_{E^{\prime}}(v)$ and one fewer red node in
$N_{E^{\prime}}(u)$, while leaving all other neighbourhoods unchanged. By the
optimality of $E^{\prime}$, $E^{\prime}\setminus\\{uv\\}$ is not a solution,
therefore it must be true that removing a blue node from $N_{E^{\prime}}(v)$
creates a majority red neighbourhood, meaning there are exactly as many red
nodes in $N_{E^{\prime}}(v)$ as blue nodes. Therefore, we will alter
$E^{\prime}$ by removing all edges of $E^{\prime}\setminus E$ incident to $v$,
and removing an equal number of edges of $E^{\prime}$ between $v$ and red
nodes. This operation, maintains the size of $|E\setminus
E^{\prime}|+|E^{\prime}\setminus E|$, decreases the number of edges of
$E^{\prime}\setminus E$ incident to a red node, and increases the number of
edges between red nodes in $E\setminus E^{\prime}$ by the same amount.

Now, suppose there is an edge of $E\setminus E^{\prime}$ incident to a blue
node $u$. Then, by 2, this edge connects $u$ to some node $v\in R$.
$E^{\prime}$ is an optimal solution, meaning $N_{E^{\prime}}(v)$ contains at
least as many blue nodes as red nodes. Adding $uv$ from $E^{\prime}$ would
reduce the size of $|E\setminus E^{\prime}|+|E^{\prime}\setminus E|$, and
result in one more blue node in $N_{E^{\prime}}(v)$ and one more red node in
$N_{E^{\prime}}(u)$, while leaving all other neighbourhoods unchanged. By the
optimality of $E^{\prime}$, $E^{\prime}\cup\\{uv\\}$ is not a solution,
therefore it must be true that adding a red node to $N_{E^{\prime}}(u)$
creates a majority red neighbourhood, meaning there are exactly as many red
nodes in $N_{E^{\prime}}(u)$ as blue nodes. Therefore, we will alter
$E^{\prime}$ by adding all edges of $E\setminus E^{\prime}$ incident to $u$,
and adding an equal number of edges of $E$ between $u$ and blue nodes. This
operation, maintains the size of $|E\setminus E^{\prime}|+|E^{\prime}\setminus
E|$, decreases the number of edges of $E\setminus E^{\prime}$ incident to a
blue node, and increases the number of edges between blue nodes in
$E^{\prime}\setminus E$ by the same amount.

Repeated application of these two operations returns an optimal solution
$E^{\prime}$ with no edges of $E^{\prime}\setminus E$ incident to any red
node, and no edges of $E\setminus E^{\prime}$ incident to any blue node. ∎

##  3 Majority Illusion Addition Elimination (MIAE)

The Majority Illusion Addition Elimination (MIAE) Problem is the Majority
Illusion Elimination Problem (MIE) restricted to adding edges.

###  3.1 A First Attempt

Given $G=(B\cup R,E)$ we define an auxiliary graph $G^{*}=(B\cup R,E^{*})$,
called the availability graph. Motivated by Lemma 1, its edges are the edges
in the complement of $G$ excluding those between two red nodes. That is,
$E^{*}$ = $\overline{E}(R,B)\cup\overline{E}(G[B])$. Now let

$b^{*}(v)=\begin{cases}\max(r(v)-b(v),0)&\mathrm{if}\ v\in R\\\
b(v)-r(v)&\mathrm{if}\ v\in B\end{cases}$

Now consider the following integer program.

$\displaystyle{\mathrm{(}{\tt IP-1a})}\qquad\qquad\max\quad\sum\limits_{e\in
E^{*}(G^{*})}-y_{e}$ (1) $\displaystyle\text{s.t.}\ \hskip 85.35826pt\
\displaystyle\sum\limits_{u:u\in N_{E^{*}}(v)\cap B}y_{uv}$
$\displaystyle=b^{*}(v)\qquad v\in R(G^{*})$ (2)
$\displaystyle\displaystyle\sum\limits_{u:u\in N_{E^{*}}(v)\cap
B}-y_{uv}+\displaystyle\sum\limits_{u:u\in N_{E^{*}}(v)\cap R}y_{uv}$
$\displaystyle\leq b^{*}(v)\qquad v\in B(G^{*})$ (3) $\displaystyle y_{e}$
$\displaystyle\in\\{0,1\\}\qquad e\in E^{*}(G^{*})$ (4)

######  Theorem 4.

The integer program (IP-1a) is the MIAE problem.

###### Proof.

Observe, by (4), that an optimal solution ${\bf y}$ to the integer program
(IP-1a) corresponds to a set of edges $Y$. We will demonstrate that $Y$ is an
optimal solution to the MIAE problem.

First, by 1, an optimal solution to the MIAE problem is a subset of $E^{*}$.
Thus constraint (4) is valid.

Second, by 1, an optimal solution to the MIAE problem has the property that
there are exactly $\max(r(v)-b(v),0)$ edges of incident to each red node $v$.
Thus the equality constraints (2) are valid.

Third, any feasible solution to the MIAE problem must satisfy the property
that the number of red nodes does not exceed the number of blue nodes in the
neighbourhood of any blue node. That is,

$\displaystyle r(v)+\displaystyle\sum\limits_{u:u\in N_{E^{*}}(v)\cap
R}y_{uv}$ $\displaystyle\leq b(v)+\displaystyle\sum\limits_{u:u\in
N_{E^{*}}(v)\cap B}y_{uv}\qquad v\in B(G^{*})$ (5)

But, for any blue node $v$, by definition $b^{*}(v)=b(v)-r(v)$. Thus
rearranging (5) we obtain (3).

Finally, an optimal solution to the MIAE problem contains as few edges of
$E^{*}$ as possible. However, minimizing $\sum_{e\in E^{*}(G^{*})}y_{e}$ is
equivalent to maximizing the objective function (1).

It follows that an optimal solution ${\bf y}$ to integer program (IP-1a) is an
optimal solution to the MIAE problem, as desired. ∎

Therefore to solve the MIAE problem, we can simply solve the integer program
(IP-1a). But running an integer programming solver is not polynomial time in
the worst case, so we need a more efficient method. Observe that the (IP-1a)
has size polynomial in the cardinality of the graph. Thus, its linear program
relaxation can be solved in polynomial time. So, if the optimal solution to
the LP relaxation is always integral then, by Theorem 4, we would have an
efficient algorithm for the MIAE problem. Unfortunately, this property is not
guaranteed. The LP relaxation is not integral.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$\frac{1}{2}$$\frac{1}{2}$$\frac{1}{2}$

Figure 4: A non-integral optimal solution to the linear program relaxation of
(IP-1a).

To see this, consider the graph shown in the LHS of Figure 4. Each of the
three blue nodes suffers from majority illusion as it has only a red node in
its neighbour. So they need an additional blue neighbour. To rectify this the
optimal solution (IP-1a) requires the addition of two edges. However, the
linear program relaxation has optimal value $\frac{3}{2}$. This is illustrated
in the RHS of Figure 4; simply add a cycle on the three blue nodes, shown in
bold, and assign these new edges weight $\frac{1}{2}$.

###  3.2 A Second Attempt

So we desire an integer program that (i) exactly models the MIAE problem, (ii)
has an integral LP relaxation, and (iii) the LP relaxation is solvable in
polynomial time.

Towards this goal we make two alterations to the integer program (IP-1a). The
first is we alter the constraint (3) for each blue node $v$ by adding
$|N_{E^{*}}(v)\cap B|$ to both sides. This transformation is evidently
innocuous. The new altered constraints are then

$\displaystyle\displaystyle\sum\limits_{u:u\in N_{E^{*}}(v)\cap
B}(1-y_{uv})+\displaystyle\sum\limits_{u:u\in N_{E^{*}}(v)\cap R}y_{uv}$
$\displaystyle\leq b^{*}(v)+|N_{E^{*}}(v)\cap B|\qquad v\in B(G^{*})$ (6)

For ease of exposition, we define a new function $b^{\prime}(v)$ to account
for this modification. Namely, let

$b^{\prime}(v)=\begin{cases}\ \max(r(v)-b(v),0)&\mathrm{if}\ v\in R\\\ \
|N_{E^{*}}(v)\cap B|+b(v)-r(v)&\mathrm{if}\ v\in B\end{cases}$

Critically, we also add the following new set of constraints to the integer
program.

$\sum\limits_{\begin{subarray}{c}e:e\in E^{*}(G^{*}[B])\\\ e\in
E^{*}(G^{*}[X])\cup
F\end{subarray}}(1-y_{e})+\displaystyle\sum\limits_{\begin{subarray}{c}e:e\in
E^{*}(R,B)\\\ e\in E^{*}(G^{*}[X])\cup F\end{subarray}}y_{e}\ \leq\
\Bigl{\lfloor}\frac{1}{2}\Bigl{(}\sum\limits_{v:v\in
X}b^{\prime}(v)+|F|\Bigr{)}\Bigr{\rfloor}\ \begin{array}[]{cc}&\forall
X\subseteq B\cup R\\\ &\forall F\subseteq\delta_{E^{*}}(X)\end{array}$ (7)

We will show in Theorem 5 that the constraints are satisMIEd by any feasible
solution to the MIAE problem. For the motivation underlying these constraints
consider again the example in Figure 4.

Consider the case of $X=B$ and $F=\emptyset$. This gives a violated constraint
for the non-integral solution ${\bf y}$ illustrated in Figure 5.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$\frac{1}{2}$$\frac{1}{2}$$\frac{1}{2}$ Figure 5:
A violated constraint:
$1-y_{v_{3}v_{4}}+1-y_{v_{3}v_{2}}+1-y_{v_{2}v_{4}}\leq\lfloor\frac{3}{2}\rfloor$

Observe, for this example, that (7) becomes

$\sum\limits_{e:e\in E^{*}(G^{*}[B])}(1-y_{e})\ \leq\
\Bigl{\lfloor}\frac{1}{2}\Bigl{(}\sum\limits_{v:v\in
B}b^{\prime}(v)\Bigr{)}\Bigr{\rfloor}$ (8)

Now

$\displaystyle\sum_{e:e\in E^{*}(G^{*}[B])}(1-y_{e})$
$\displaystyle=(1-y_{v_{2}v_{3}})+(1-y_{v_{2}v_{4}})+(1-y_{v_{3}v_{4}})$
$\displaystyle=3-(y_{v_{2}v_{3}}+y_{v_{2}v_{4}}+y_{v_{3}v_{4}})$
$\displaystyle=3-3\cdot\frac{1}{2}$ $\displaystyle=\frac{3}{2}$

On the other hand

$\displaystyle\Bigl{\lfloor}\frac{1}{2}\Bigl{(}\sum\limits_{v:v\in
B}b^{\prime}(v)\Bigr{)}\Bigr{\rfloor}$
$\displaystyle=\Bigl{\lfloor}\frac{1}{2}\Bigl{(}\sum\limits_{v:v\in
B}\left(|N_{E^{*}}(v)\cap B|+b(v)-r(v)\right)\Bigr{)}\Bigr{\rfloor}$
$\displaystyle=\Bigl{\lfloor}\frac{1}{2}\Bigl{(}\sum\limits_{v:v\in
B}\left(2+0-1\right)\Bigr{)}\Bigr{\rfloor}$
$\displaystyle=\Bigl{\lfloor}\frac{1}{2}\sum\limits_{v:v\in B}1\Bigr{\rfloor}$
$\displaystyle=\Bigl{\lfloor}\frac{3}{2}\Bigr{\rfloor}$ $\displaystyle=1$

Ergo, the constraint (8) is violated for the non-integral solution ${\bf y}$.
In fact, we will prove adding this set of new constraints will eliminate all
non-integral solutions.

Putting all this together our new integer program is

$\displaystyle{\mathrm{(}{\tt IP-1b})}\qquad\max\quad\sum\limits_{e\in
E^{*}(G^{*})}-y_{e}$ $\displaystyle\text{s.t.}\ \hskip 56.9055pt\
\displaystyle\sum\limits_{u:u\in N_{E^{*}}(v)\cap B}y_{uv}$
$\displaystyle=b^{\prime}(v)\qquad v\in R(G^{*})$
$\displaystyle\displaystyle\sum\limits_{u:u\in N_{E^{*}}(v)\cap
B}(1-y_{uv})+\displaystyle\sum\limits_{u:u\in N_{E^{*}}(v)\cap R}y_{uv}$
$\displaystyle\leq b^{\prime}(v)\qquad v\in B(G^{*})$
$\displaystyle\sum\limits_{\begin{subarray}{c}e:e\in E^{*}(G^{*}[B])\\\ e\in
E^{*}(G^{*}[X])\cup
F\end{subarray}}(1-y_{e})+\displaystyle\sum\limits_{\begin{subarray}{c}e:e\in
E^{*}(R,B)\\\ e\in E^{*}(G^{*}[X])\cup F\end{subarray}}y_{e}$
$\displaystyle\leq\Bigl{\lfloor}\frac{1}{2}\Bigl{(}\sum\limits_{v:v\in
X}b^{\prime}(v)+|F|\Bigr{)}\Bigr{\rfloor}\ \begin{array}[]{cc}&\forall
X\subseteq B\cup R\\\ &\forall F\subseteq\delta_{E^{*}}(X)\end{array}$ (11)
$\displaystyle y_{e}$ $\displaystyle\in\\{0,1\\}\qquad e\in E^{*}(G^{*})$

Our first step then is to verify that (i) still holds; that is, (IP-1b) solves
the MIAE problem.

######  Theorem 5.

The integer program (IP-1b) is the MIAE problem.

###### Proof.

By Theorem 4, it suffices to prove that the integer program (IP-1b) is the
integer program (IP-1a). As mentioned, the alterations to the previous
inequality constraints are trivial. What remains is to show the newly added
constraints (7) do not eliminate any solutions. So take any solution $\bf{y}$
to the integer program (IP-1a), any collection $X\subseteq B\cup R$ and any
subset of edges $F\subseteq\delta_{E^{*}}(X)$ leaving $X$ in $E^{*}(G^{*})$.
For each node $v\in B$, the constraint on $v$ gives

$\sum\limits_{\begin{subarray}{c}e:v\in e\\\ e\in E^{*}(G^{*}[B])\\\ e\in
E^{*}(G^{*}[X])\end{subarray}}(1-y_{e})+\displaystyle\sum\limits_{\begin{subarray}{c}e:v\in
e\\\ e\in E^{*}(R,B)\\\ e\in
E^{*}(G^{*}[X])\end{subarray}}y_{e}+\displaystyle\sum\limits_{\begin{subarray}{c}e:v\in
e\\\ e\in E^{*}(G^{*}[B])\\\ e\in
F\end{subarray}}(1-y_{e})+\displaystyle\sum\limits_{\begin{subarray}{c}e:v\in
e\\\ e\in E^{*}(R,B)\\\ e\in F\end{subarray}}y_{e}\ \leq\ b^{\prime}(v)$ (12)

Also, for each node $v\in R$, the constraint on $v$ gives

$\displaystyle\sum\limits_{\begin{subarray}{c}e:v\in e\\\ e\in E^{*}(R,B)\\\
e\in
E^{*}(G^{*}[X])\end{subarray}}y_{e}+\displaystyle\sum\limits_{\begin{subarray}{c}e:v\in
e\\\ e\in E^{*}(R,B)\\\ e\in F\end{subarray}}y_{e}\ \leq\ b^{\prime}(v)$ (13)

Therefore, when we sum these constraints for every node in $X$, we get

$2\cdot\sum\limits_{\begin{subarray}{c}e:e\in E^{*}(G^{*}[B])\\\ e\in
E^{*}(G^{*}[X])\end{subarray}}(1-y_{e})+2\cdot\displaystyle\sum\limits_{\begin{subarray}{c}e:e\in
E^{*}(R,B)\\\ e\in
E^{*}(G^{*}[X])\end{subarray}}y_{e}+\displaystyle\sum\limits_{\begin{subarray}{c}e:e\in
E^{*}(G^{*}[B])\\\ e\in
F\end{subarray}}(1-y_{e})+\displaystyle\sum\limits_{\begin{subarray}{c}e:e\in
E^{*}(R,B)\\\ e\in F\end{subarray}}y_{e}\ \leq\
\displaystyle\sum\limits_{v:v\in X}b^{\prime}(v)$ (14)

Also, trivially, we have

$\displaystyle|F|$ $\displaystyle=\sum\limits_{e:e\in E^{*}(G^{*}[B])\cap
F}1+\sum\limits_{e:e\in E^{*}(R,B)\cap F}1$
$\displaystyle\geq\sum\limits_{e:e\in E^{*}(G^{*}[B])\cap
F}(1-y_{e})+\sum\limits_{e:e\in E^{*}(R,B)\cap F}y_{e}$ (15)

Summing (14) and (3.2), we obtain

$2\cdot\sum\limits_{\begin{subarray}{c}e:e\in E^{*}(G^{*}[B])\\\ e\in
E^{*}(G^{*}[X])\cup
F\end{subarray}}(1-y_{e})+2\cdot\sum\limits_{\begin{subarray}{c}e:e\in
E^{*}(R,B)\\\ e\in E^{*}(G^{*}[X])\cup F\end{subarray}}y_{e}\ \leq\
\sum\limits_{v:v\in X}b^{\prime}(v)+|F|$

Finally divide both sides by two and take their floors. By the integrality of
${\bf y}$, we have

$\sum\limits_{\begin{subarray}{c}e:e\in E^{*}(G^{*}[B])\\\ e\in
E^{*}(G^{*}[X])\cup
F\end{subarray}}(1-y_{e})+\sum\limits_{\begin{subarray}{c}e:e\in E^{*}(R,B)\\\
e\in E^{*}(G^{*}[X])\cup F\end{subarray}}y_{e}\ \leq\
\Bigl{\lfloor}\frac{1}{2}\Bigl{(}\sum\limits_{v:v\in
X}b^{\prime}(v)+|F|\Bigr{)}\Bigr{\rfloor}$

Thus ${\bf y}$ is also a solution to the integer program (IP-1b). ∎

Again, Theorem 5 implies that we can solve the MIAE problem by solving the
integer program (IP-1b). We will do this efficiently by solving its linear
program relaxation. To achieve this successfully, we must show that the LP
relaxation is integral and also that it can be solved in polynomial time
despite the fact that there are an exponential number of constraints of type
(7).

###  3.3 A TDI System

The LP relaxation of (IP-1b) is

$\displaystyle{\mathrm{(}{\tt IP-1b})}\qquad\max\quad\sum\limits_{e\in
E^{*}(G^{*})}-y_{e}$ (16) $\displaystyle\text{s.t.}\ \hskip 56.9055pt\
\displaystyle\sum\limits_{u:u\in N_{E^{*}}(v)\cap B}y_{uv}$
$\displaystyle=b^{\prime}(v)\qquad v\in R(G^{*})$ (17)
$\displaystyle\displaystyle\sum\limits_{u:u\in N_{E^{*}}(v)\cap
B}(1-y_{uv})+\displaystyle\sum\limits_{u:u\in N_{E^{*}}(v)\cap R}y_{uv}$
$\displaystyle\leq b^{\prime}(v)\qquad v\in B(G^{*})$ (18)
$\displaystyle\sum\limits_{\begin{subarray}{c}e:e\in E^{*}(G^{*}[B])\\\ e\in
E^{*}(G^{*}[X])\cup
F\end{subarray}}(1-y_{e})+\displaystyle\sum\limits_{\begin{subarray}{c}e:e\in
E^{*}(R,B)\\\ e\in E^{*}(G^{*}[X])\cup F\end{subarray}}y_{e}$
$\displaystyle\leq\Bigl{\lfloor}\frac{1}{2}\Bigl{(}\sum\limits_{v:v\in
X}b^{\prime}(v)+|F|\Bigr{)}\Bigr{\rfloor}\ \begin{array}[]{cc}&\forall
X\subseteq B\cup R\\\ &\forall F\subseteq\delta_{E^{*}}(X)\end{array}$ (21)
$\displaystyle 0\ \leq\ y_{e}$ $\displaystyle\leq 1\qquad e\in E^{*}(G^{*})$
(22)

It will now be cleaner to impose a change of variables. Specifically, let

$x_{e}=\begin{cases}y_{e}&\mathrm{if}\ e\in E^{*}(R,B)\\\ 1-y_{e}&\mathrm{if}\
e\in E^{*}(G^{*}[B])\end{cases}$

The LP relaxation then simplifies to

$\displaystyle{\mathrm{(}{\tt LP-1c})}\qquad\max\quad\sum\limits_{e\in
E^{*}(G[B])}x_{e}$ $\displaystyle-\sum\limits_{e\in
E^{*}(R,B)}x_{e}-|E^{*}(G[B])|$ (23) $\displaystyle\text{s.t.}\ \hskip
56.9055pt\ \sum\limits_{e:e\in\delta(v)}x_{e}$
$\displaystyle=b^{\prime}(v)\qquad v\in R$ (24)
$\displaystyle\sum\limits_{e:e\in\delta(v)}x_{e}$ $\displaystyle\leq
b^{\prime}(v)\qquad v\in B$ (25) $\displaystyle\sum\limits_{e:e\in
E^{*}(G^{*}[X])}x_{e}+\sum\limits_{e:e\in F}x_{e}$
$\displaystyle\leq\Bigl{\lfloor}\frac{1}{2}\Bigl{(}\sum\limits_{v:v\in
X}b^{\prime}(v)+|F|\Bigr{)}\Bigr{\rfloor}\qquad\begin{array}[]{l}\forall
X\subseteq B\cup R\\\ \forall F\subseteq\delta_{E^{*}}(X)\end{array}$ (28)
$\displaystyle 0\ \leq\ x_{e}$ $\displaystyle\leq 1\qquad e\in E^{*}(G^{*})$
(29)

One method to prove that a polytope has integer nodes involves the concept of
total dual integrality (TDI).

######  Definition.

A polytope $\textbf{Ax}\leq\textbf{b}$ is Total Dual Integral (TDI) if A,b
have rational entries, and if for any $\textbf{c}\in\mathcal{Z}^{n}$ such that
$\max~{}\textbf{cx}$ s.t $\textbf{Ax}\leq\textbf{b}$ has an optimal solution,
then there is an integer optimal dual solution.

A proof that a linear program is TDI allows us to use the following result to
show that it is integral.

######  Theorem 6.

[7] If a linear system $\\{\textbf{Ax}\leq\textbf{b}\\}$ is TDI, and b is
integral, then $\\{\textbf{Ax}\leq\textbf{b}\\}$ is integral.

We will prove that (LP-1c) is total dual integral (TDI) to show its
integrality. To do this, we turn our attention to simple $b$-matchings.

######  Theorem 7.

[22] The following simple b’-matching polytope is TDI:

$\displaystyle({\tt\textbf{b'}-matching~{}LP})\qquad\sum\limits_{e:e\in\delta(v)}x_{e}$
$\displaystyle\leq b^{\prime}(v)\qquad v\in B\cup R$ (30)
$\displaystyle\sum\limits_{e:e\in E^{*}(G^{*}[X])}x_{e}+\sum\limits_{e:e\in
F}x_{e}$
$\displaystyle\leq\Bigl{\lfloor}\frac{1}{2}\Bigl{(}\sum\limits_{v:v\in
X}b^{\prime}(v)+|F|\Bigr{)}\Bigr{\rfloor}\qquad\begin{array}[]{l}\forall
X\subseteq B\cup R\\\ \forall F\subseteq\delta_{E^{*}}(X)\end{array}$ (33)
$\displaystyle 0\ \leq\ x_{e}$ $\displaystyle\leq 1\qquad e\in E^{*}(G^{*})$
(34)

This TDI system is very similar to our system. We merely require one more
result.

######  Theorem 8.

[5] Let $\textbf{Ax}\leq\textbf{b}$ be TDI and let
$\textbf{A'x}\leq\textbf{b'}$ arise from $\textbf{Ax}\leq\textbf{b}$ by adding
$-a^{T}x\leq-\beta$ for some inequality $a^{T}x\leq\beta$ in
$\textbf{Ax}\leq\textbf{b}$. Then also $\textbf{A'x}\leq\textbf{b'}$ is TDI.

######  Corollary 9.

The linear system of (LP-1b) is TDI.

###### Proof.

The b’-matching LP is total dual integral by 7. Therefore, the linear system
of (LP-1c) is total dual integral, as it is the result of applying 8 to the
constraints of the b’-matching LP. But, via the given change of variables,
this implies the linear system of (LP-1b) is total dual integral. ∎

######  Corollary 10.

The linear program (LP-1b) is integral.

###### Proof.

This follows immediately from Corollary 9 and Theorem 6. ∎

###  3.4 A Polynomial Time Algorithm

So (LP-1b) is integral. But because it has exponentially many constraints, we
need to show it can be solved in polynomial time. To do so, we apply a
separation oracle.

######  Definition.

Separation Problem: Given a convex set $P\subseteq\mathbb{R}^{n}$ and a vector
$y\in\mathbb{Q}^{n}$, either determine that $y\in P$ or find a vector
$d\in\mathbb{Q}^{n}$ such that $d^{T}x<d^{T}y$ for all $x\in P$.

######  Theorem 11.

[13] Let $n\in\mathbb{N}$ and $c\in\mathbb{Q}^{n}$. Let
$P\subseteq\mathbb{R}^{n}$ be a rational polytope, and let
$x_{0}\in\mathbb{Q}^{n}$ be a point in the interior of $P$. Let
$T\in\mathbb{N}$ such that $size(x_{0})\leq\log T$ and $size(x)\leq\log T$ for
all nodes $x$ of $P$. Given $n,c,x_{0},T$ and a polynomial-time oracle for the
Separation Problem for $P$, a node $x^{*}$ of $P$ attaining $max\\{c^{T}x:x\in
P\\}$ can be found in time polynomial in $n$, $\log T$ and $size(c)$.

######  Theorem 12.

[20, 17] For undirected graphs
$G,\textbf{u}:E(G)\rightarrow\mathbb{N}\cup\\{\infty\\}$ and
$\textbf{b}:V(G)\rightarrow\mathbb{N}$, the Separation Problem for the
b-matching polytope of $(G,\textbf{u})$ can be solved in $O(n^{4})$ time.

######  Theorem 13.

The Separation Problem for (LP-1b) can be solved in $O(n^{4})$ time.

###### Proof.

By Theorem 11 it suffices to have a polynomial-time algorithm for the
Separation Problem for the vector ${\bf y}$ and the feasible set in (LP-1b),
which we will refer to as $P$. Such an algorithm exists for the convex set in
(b’-matching LP), which we will refer to as $Q$, by Theorem 12. If we define
vector ${\bf x}\in\mathbb{R}^{E^{*}}$ by setting

$x_{e}=\begin{cases}y_{e}&\mathrm{if}\ e\in E^{*}(R,B)\\\ 1-y_{e}&\mathrm{if}\
e\in E^{*}(G^{*}[B])\end{cases}$

and then change variables from ${\bf y}$ to ${\bf x}$, we can transform $P$
into a subset of $Q$. This means if ${\bf x}\not\in Q$, then ${\bf y}\not\in
P$, and we can determine this in $O(n^{4})$ time. We can also determine if
${\bf x}\in Q$ in $O(n^{4})$ time, and if this is the case, we just need to
check $|R|$ equality constraints to determine if ${\bf y}\in P$, which we can
do in linear time. ∎

######  Corollary 14.

The $\frac{1}{2}$ -Illusion Addition Problem can be solved in polynomial time.

###### Proof.

LP-1c will solve the $\frac{1}{2}$-Illusion Addition problem just as it solves
MIAE. When a strict majority of the vertices are blue, the two problems are
equivalent. The removal of the strict majority requirement, which is the only
diffence between MIAE and $\frac{1}{2}$-IA, changes nothing except that it
allows input graphs where LP - 1c has no solution, for example in cases where
there is a blue vertex adjacent to more red vertices than there are blue
vertices. In these cases, there is no solution of size less than or equal to
$k$, meaning $\frac{1}{2}$-IA is a NO instance. ∎

##  4 Majority Illusion Removal Elimination (MIRE)

The Majority Illusion Removal Elimination (MIRE) Problem is the Majority
Illusion Elimination (MIE) Problem restricted to removing edges

Given $G=(B\cup R,E)$ we define an auxiliary graph $G^{*}=(B\cup R,E^{*})$,
called the removable graph. Its edges are the edges in $G$ excluding those
between two blue nodes. That is, $E^{*}=E(R,B)\cup E(G[R])$. Now let

$b^{*}(v)=\begin{cases}\max(r(v)-b(v),0)&\mathrm{if}\ v\in B\\\
b(v)-r(v)&\mathrm{if}\ v\in R\end{cases}$

Now consider the following integer program.

$\displaystyle{\mathrm{(}{\tt IP-2})}\qquad\max\quad\sum\limits_{e\in
E^{*}(G^{*})}-y_{e}$ (35) $\displaystyle\text{s.t.}\ \hskip 85.35826pt\
\displaystyle\sum\limits_{u:u\in N_{E^{*}}(v)\cap R}y_{uv}$
$\displaystyle=b^{*}(v)\qquad v\in B(G^{*})$ (36)
$\displaystyle\displaystyle\sum\limits_{u:u\in N_{E^{*}}(v)\cap
R}-y_{uv}+\displaystyle\sum\limits_{u:u\in N_{E^{*}}(v)\cap B}y_{uv}$
$\displaystyle\leq b^{*}(v)\qquad v\in R(G^{*})$ (37) $\displaystyle y_{e}$
$\displaystyle\in$ $\displaystyle\\{0,1\\}\qquad e\in E^{*}(G^{*})$ (38)

######  Theorem 15.

The integer program (IP-2) is the MIRE problem

###### Proof.

The proof is the same as for the MIAE case, as (IP-2) is symmetric to (IP-1)
with the roles of $B$ and $R$ swapped. ∎

As one might expect, our strategy for solving the MIRE problem will mirror the
approach for the MIAE problem. We will modify (IP-2) to create a linear
program (LP-2) which is symmetric to (LP-1b).

Just like for (LP-1b), we add a value to both sides of each inequality. In
this case, it is $|N_{E^{*}}(v)\cap R|$. Once again we define function
$b^{\prime}(v)$ to account for this change:

$b^{\prime}(v)=\begin{cases}\max(r(v)-b(v),0)&\mathrm{if}\ v\in B\\\
|N_{E^{*}}(v)\cap R|+b(v)-r(v)&\mathrm{if}\ v\in R\end{cases}$

Finally, we add an analogous set of new constraints to the integer program.

$\sum\limits_{\begin{subarray}{c}e:e\in E^{*}(G^{*}[R])\\\ e\in
E^{*}(G^{*}[X])\cup
F\end{subarray}}(1-y_{e})+\displaystyle\sum\limits_{\begin{subarray}{c}e:e\in
E^{*}(R,B)\\\ e\in E^{*}(G^{*}[X])\cup F\end{subarray}}y_{e}\ \leq\
\Bigl{\lfloor}\frac{1}{2}\Bigl{(}\sum\limits_{v:v\in
X}b^{\prime}(v)+|F|\Bigr{)}\Bigr{\rfloor}\ \begin{array}[]{cc}&\forall
X\subseteq B\cup R\\\ &\forall F\subseteq\delta_{E^{*}}(X)\end{array}$ (39)

The LP relaxation of (IP-2) is

$\displaystyle{\mathrm{(}{\tt LP-2})}\qquad\max\quad\sum\limits_{e\in
E^{*}(G^{*})}-y_{e}$ (40) $\displaystyle\text{s.t.}\ \hskip 56.9055pt\
\displaystyle\sum\limits_{u:u\in N_{E^{*}}(v)\cap R}y_{uv}$
$\displaystyle=b^{\prime}(v)\qquad v\in B(G^{*})$ (41)
$\displaystyle\displaystyle\sum\limits_{u:u\in N_{E^{*}}(v)\cap
R}(1-y_{uv})+\displaystyle\sum\limits_{u:u\in N_{E^{*}}(v)\cap B}y_{uv}$
$\displaystyle\leq b^{\prime}(v)\qquad v\in R(G^{*})$ (42)
$\displaystyle\sum\limits_{\begin{subarray}{c}e:e\in E^{*}(G^{*}[R])\\\ e\in
E^{*}(G^{*}[X])\cup
F\end{subarray}}(1-y_{e})+\displaystyle\sum\limits_{\begin{subarray}{c}e:e\in
E^{*}(R,B)\\\ e\in E^{*}(G^{*}[X])\cup F\end{subarray}}y_{e}$
$\displaystyle\leq\Bigl{\lfloor}\frac{1}{2}\Bigl{(}\sum\limits_{v:v\in
X}b^{\prime}(v)+|F|\Bigr{)}\Bigr{\rfloor}\ \begin{array}[]{cc}&\forall
X\subseteq B\cup R\\\ &\forall F\subseteq\delta_{E^{*}}(X)\end{array}$ (45)
$\displaystyle 0\ \leq\ y_{e}$ $\displaystyle\leq 1\qquad e\in E^{*}(G^{*})$
(46)

######  Corollary 16.

The linear program (LP-2) is integral.

###### Proof.

The proof is identical to the proof of 10. ∎

######  Corollary 17.

The Separation Problem for linear program (LP-2) can be solved in $O(n^{4})$
time.

###### Proof.

The proof is identical to the proof of 13. ∎

######  Corollary 18.

The $\frac{1}{2}$ -Illusion Removal Problem can be solved in polynomial time.

###### Proof.

LP-2 will solve the $\frac{1}{2}$-Illusion Removal problem just as it solves
MIRE. When a strict majority of the vertices are blue, the two problems are
equivalent. The removal of the strict majority requirement, which is the only
difference between MIRE and $\frac{1}{2}$-IR, changes nothing. ∎

##  5 Majority Illusion Elimination (MIE)

Finally, we arrive at the the general problem. Take $G=(B\cup R,E)$ and let
$N_{E}(v)=\\{u:(u,v)\in E\\}$ be the neighbourhood of $v$. To solve the
general problem, we will create new graphs $G^{a}=(R\cup B,E^{a})$ and
$G^{s}=(R\cup B,E^{s})$. Specifically:

$\bullet$ Create $G^{a}$ from $G$ by removing all edges of $G[R]$.

$\bullet$ Create $G^{r}$ from $G$ by adding all edges of the complement of
$G[B]$.

The remarkable fact now is that an optimal solution to the general problem on
$G=(V,E)$ can be reduced to an optimal solution to the MIAE problem on $G^{a}$
plus an optimal solution to the MIRE problem on $G^{s}$.

######  Theorem 19.

There is an optimal solution $E^{*}$ to the MIE problem on $G$ composed of the
union of the optimal solution $E^{a}$ to the MIAE problem on $G^{a}$ and the
optimal solution $E^{r}$ to the MIRE problem on $G^{r}$

###### Proof.

By 2 and 3, the edges removed from $G$ to create $G^{a}$ are a superset of
those removed in an optimal solution $E^{*}$ to MIE on $G$. These removals are
strictly beneficial, as all edges removed are between two red nodes. Therefore
any optimal solution $E^{a}$ to $MIAE$ on $G^{a}$ will be a subset of the
edges added in some optimal solution $E^{*}$ to MIE on $G$.

By 1 and 3, the edges added to $G$ to create $G^{r}$ are a superset of those
added in an optimal solution $E^{*}$ to MIE on $G$. These additions are
strictly beneficial, as all edges added are between two blue nodes. Therefore
any optimal solution $E^{r}$ to $MIRE$ of $G^{r}$ will be a subset of the
edges removed in some optimal solution $E^{*}$ to MIE on $G^{\prime}$.

Because $|E^{r}|+|E^{a}|\leq|E^{*}|$, all that remains is to show that $E^{r}$
together with $E^{a}$ eliminates illusion in $G$. Observe that in $G^{r}$ the
blue nodes from a clique. Consequently, no blue node is under illusion, and
only red nodes can be under illusion. Therefore the only edges removed in an
optimal solution $E^{r}$ to the MIRE problem will be between two red nodes.
That is, removing an edge between a red and blue node cannot help the red node
and is not necessary for the blue node, as it is not under illusion.

Similarly, in $G^{a}$ the red nodes from an independent set. Consequently, no
red node is under illusion, and only blue nodes can be under illusion.
Therefore the only edges added in an optimal solution $E^{a}$ to the MIAE
problem will be between two blue nodes. That is, adding an edge between a red
and blue node cannot help the blue node and is not necessary for the red node,
as it is not under illusion.

Furthermore, all the red nodes in $G^{r}$ are under exactly the same illusion
as the red nodes in $G$; therefore $E^{r}$ eliminates all illusion on $R$.
Symmetrically, all the blue nodes in $G^{a}$ are under exactly the same
illusion as the blue nodes in $G$; therefore $E^{a}$ eliminates all illusion
on $B$. Thus, crucially, $E^{r}$ and $E^{a}$ do not affect each other, because
they do not add or remove any edges in $(R,B)$. Therefore together they
eliminate all illusion in $G$. The theorem follows. ∎

Theorem 19 implies we can solve the MIE problem in polynomial time. We reduce
it to a MIAE probelm and a MIRE problem, which we can both solve in polynomial
time by the methods developed in Sections 3 and 4.

However, we can exploit Theorem 19 to solve the FIA directly using a single
linear program. This is because the reduction worked by essentially reducing
the problem to to two independent $b$-matching problems within the same graph!
In particular, take $G=(B\cup R,E)$ and define functions

$\displaystyle b^{a}(v)$ $\displaystyle=|N_{E^{*}}(v)\cap
B|+b(v)-r(v)\qquad\forall v\in B$ $\displaystyle b^{r}(v)$
$\displaystyle=|N_{E^{*}}(v)\cap R|+b(v)-r(v)\qquad\forall v\in R$

Our linear program is then

$\displaystyle{\mathrm{(}{\tt LP-3})}\qquad\max\quad\sum\limits_{e\in
E^{*}(G^{*})}-y_{e}$ (47) $\displaystyle\text{s.t.}\ \hskip 56.9055pt\
\displaystyle\sum\limits_{u:u\in N_{E^{*}}(v)\cap B}(1-y_{uv})$
$\displaystyle\leq b^{a}(v)\qquad v\in B(G^{*})$ (48)
$\displaystyle\sum\limits_{\begin{subarray}{c}e:e\in E^{*}(G^{*}[B])\\\ e\in
E^{*}(G^{*}[X])\cup F\end{subarray}}(1-y_{e})$
$\displaystyle\leq\Bigl{\lfloor}\frac{1}{2}\Bigl{(}\sum\limits_{v:v\in
X}b^{a}(v)+|F|\Bigr{)}\Bigr{\rfloor}\ \begin{array}[]{cc}&\forall X\subseteq
B\\\ &\forall F\subseteq\delta_{E^{*}}(X)\end{array}$ (51)
$\displaystyle\displaystyle\sum\limits_{u:u\in N_{E^{*}}(v)\cap R}(1-y_{uv})$
$\displaystyle\leq b^{r}(v)\qquad v\in R(G^{*})$ (52)
$\displaystyle\sum\limits_{\begin{subarray}{c}e:e\in E^{*}(G^{*}[R])\\\ e\in
E^{*}(G^{*}[X])\cup F\end{subarray}}(1-y_{e})$
$\displaystyle\leq\Bigl{\lfloor}\frac{1}{2}\Bigl{(}\sum\limits_{v:v\in
X}b^{r}(v)+|F|\Bigr{)}\Bigr{\rfloor}\ \begin{array}[]{cc}&\forall X\subseteq
R\\\ &\forall F\subseteq\delta_{E^{*}}(X)\end{array}$ (55) $\displaystyle 0\
\leq\ y_{e}$ $\displaystyle\leq 1\qquad e\in E^{*}(G^{*})$ (56)

######  Corollary 20.

The linear program (LP-3) is integral.

###### Proof.

This linear program is equivalent to two independent copies of the
$b^{\prime}$-matching LP, therefore its integrality follows directly from 7
and 8. ∎

######  Corollary 21.

The Separation Problem for linear program (LP-3) can be solved in $O(n^{4})$
time.

###### Proof.

This follows directly from 12. ∎

######  Corollary 22.

The $\frac{1}{2}$-Illusion Problem can be solved in polynomial time.

###### Proof.

From the proof of 3, we know it is always preferable to correct a blue node in
deficit by adding a blue neighbour than removing a red neighbour. However,
without the strict majority restriction, this is not always possible. The fix
is rather simple. For the set of blue nodes $B^{\prime}=\\{v:v\in
B,N_{R}(v)\geq|B|\\}$, we add edges between every node of $B^{\prime}$ to all
nodes of $B$, including $B^{\prime}$, as we know there is a solution that
contains all these edges. Now the remaining edges of the solution to
$\frac{1}{2}$-Illusion consist of optimally removing edges of $G[R\cup
B^{\prime}]$ and optimally adding non-edges of $G[B\setminus B^{\prime}]$,
both of which we can do in polynomial time by 14 and 18. ∎

##  6 Hardness

In this section we present variants of the MIE, MIAE and MIRE problems.

######  Definition.

Let $p\in[0,1],p\in\mathcal{Q}$. We define the $p$-IA problem as follows:
Given a graph $G=(V=R\cup B,E)$ and integer $k$, the objective is to determine
if the addition of at most $k$ edges can ensure each node has at least a
$p$-fraction of blue nodes in its neighbourhood.

######  Definition.

Let $p\in[0,1],p\in\mathcal{Q}$. We define the $p$-IR problem as follows:
Given a graph $G=(V=R\cup B,E)$ and integer $k$, the objective is to determine
if the subtraction of at most $k$ edges can ensure each node has at least a
$p$-fraction of blue nodes in its neighbourhood.

######  Definition.

Let $p\in[0,1],p\in\mathcal{Q}$. We define the $p$-I problem as follows: Given
a graph $G=(V=R\cup B,E)$ and integer $k$, the objective is to determine if
the addition/subtraction of at most $k$ edges can ensure each node has at
least a $p$-fraction of blue nodes in its neighbourhood.

For $p=\frac{1}{2}$, if we add the requirement that blue be the strict
majority, these extended problems correspond to the original MIAE, MIRE and
MIE problems for which we have provided polynomial-time algorithms in the
previous sections of this paper. Our algorithms can be extended to handle the
case when blue is not the true majority, showing that the problems are
solvable in polynomial time when $p=\frac{1}{2}$. Regardless, to show NP-
hardness for other values of $p$, we provide a polynomial time reduction from
the following NP-complete, satisfiability problem.

######  Definition.

XSAT for $l$-CNF${}_{+}^{l}$ is the problem of determining whether a boolean
formula in conjunctive normal form composed of $n$ variables appearing exactly
$l$ times as positive literals within clauses of size exactly $l$ has an
assignment which evaluates to TRUE such that each clause has exactly one
variable assigned TRUE.

######  Theorem 23.

[21][Theorem 29] XSAT for $l$-CNF${}_{+}^{l}$ is NP-complete for any $l\geq 3$

######  Theorem 24.

The $p$-IA problem and $p$-I problem are NP-hard for
$p\in\mathbb{Q},0<p<\frac{1}{2},p\not=\frac{1}{3}$.

###### Proof.

First, we write $p$ as an irreductible fraction $p=\frac{a}{b}$ where
$a,b\in\mathbb{N}$ are coprime and $p<\frac{1}{2}$. This implies $2a<b$.
Therefore, we can write $p=\frac{a}{b}=\frac{a}{a+l}$ for $l\geq 3$, $l>a$,
and $\gcd(a,l)=1$. Note that $\frac{1}{3}$ cannot be written this way because
of the condition $l\geq 3$.

Consider an instance of XSAT for $l$-CNF${}_{+}^{l}$ with $n$ variables and
$n$ clauses, where $n\geq 2l$. We build an auxiliary graph $G=(B\cup R,E)$ of
polynomial size such that there is a solution to this XSAT instance for
$l$-CNF${}_{+}^{l}$ if and only if the $p$-I problem associated with $G$ can
be solved by adding or removing at most $\frac{n}{l}\cdot(l+a)$ edges.
Moreover if there is a solution to this XSAT instance, there is a solution to
the $p$-I problem that add exactly $\frac{n}{l}\cdot(l+a)$ edges and remove no
edges. Consequently, this also works as a reduction to the $p$-IA problem.
Note that $\frac{n}{l}$ must be an integer, as otherwise the XSAT problem
trivially has no solution.

We design the graph $G$ to have nodes of six types: dummy blue nodes $B_{D}$,
where $|B_{D}|=a\cdot n^{2}+l-(2a\cdot n+2)$; equalizing blue nodes $B_{E}$,
where $|B_{E}|=2a\cdot n-(n-1)$; dummy red nodes $R_{D}$, where
$|R_{D}|=l\cdot n^{2}-2l\cdot n+(n-l)$; equalizing red nodes $R_{E}$, where
$|R_{E}|=2l\cdot n-(n-l)$; blue variable nodes $B_{V}$, where $|B_{V}|=n$ (we
have a blue variable node $v_{x}$ for each variable $x$ of the XSAT instance);
and red clause nodes $R_{C}$, where $|R_{C}|=n$ (we have a red clause node
$w_{c}$ for each clause $c$ of the XSAT instance).

We now describe the graph $G$ by detailing the neighborhood of each node. We
remind the reader of the notation $b(v)$ and $r(v)$, which denote the number
of blue and red neighbors of node $v$, respectively.

  * •

Variable nodes: The neighbourhood of $v_{x}$ for all $v_{x}\in B_{V}$ is
$B_{E}\cup R_{E}\cup\\{w_{c}:w_{c}\in R_{C},x\not\in c\text{ in the XSAT
problem}\\}\cup(B_{V}-v_{x})$. Note that $b(v_{x})=\frac{a}{l}\cdot r(v_{x})$
for all $v_{x}\in B_{V}$, and therefore _exactly a $p$-fraction_ of the
neighbourhood of each node of $B_{V}$ is blue.

  * •

Clause nodes: The neighbourhood of $w_{c}$ for all $w_{c}\in R_{C}$ is
$B_{E}\cup R_{E}\cup B_{D}\cup R_{D}\cup\\{v_{x}:v_{x}\in B_{V},x\not\in
C\text{ in the XSAT problem}\\}$. Note that $b(w_{c})=\frac{a}{l}\cdot
r(w_{c})-1$ for all $w_{c}\in R_{C}$, so each $w_{c}\in R_{c}$ can add one
more blue neighbour without violating the $p$-fraction constraint.

  * •

Dummy blue nodes: The neighbourhood of $v$ for all $v\in B_{D}$ is $B_{E}\cup
R_{C}\cup B_{D}-v$. There are $an^{2}+l-n+2$ blue nodes and n red nodes in the
neighbourhood of each $v\in B_{D}$, so there are at least $p$-fraction of blue
nodes in the neighbourhood.

  * •

Dummy red nodes: The neighbourhood of $v$ for all $v\in R_{D}$ is $B_{E}\cup
R_{C}$. There are $2an-(n-1)$ blue nodes and $n$ red nodes in the
neighbourhood of each $v\in R_{D}$, so there are at least $p$-fraction of blue
nodes in the neighbourhood.

  * •

Equalizing blue nodes: The neighbourhood of $v$ for all $v\in B_{E}$ is
$R_{C}\cup R_{D}\cup B_{V}\cup B_{D}\cup B_{E}-v$. There are $an^{2}+l-2$ blue
nodes and $l\cdot n^{2}+2n-2l\cdot n-l$ red nodes in the neighbourhood of each
$v\in B_{E}$, so there are at least $p$-fraction of blue nodes in the
neighbourhood.

  * •

Equalizing red nodes: The neighbourhood of $v$ for all $v\in R_{E}$ is
$R_{C}\cup B_{V}$. There are at least $p$-fraction of blue nodes in the
neighbourhood.

$v_{x_{6}}$$v_{x_{5}}$$v_{x_{4}}$$v_{x_{3}}$$v_{x_{2}}$$v_{x_{1}}$$w_{c_{1}}$$w_{c_{2}}$$w_{c_{3}}$$w_{c_{4}}$$w_{c_{5}}$$w_{c_{6}}$$R_{C}$$B_{V}$$R_{D}$$B_{D}$$R_{E}$$B_{E}$
Figure 6: An example of a network $G$ which reduces the $3-XSAT^{3}_{+}$
problem $(x_{1}\lor x_{2}\lor x_{3})\land(x_{1}\lor x_{2}\lor
x_{4})\land(x_{1}\lor x_{3}\lor x_{4})\land(x_{2}\lor x_{5}\lor
x_{6})\land(x_{3}\lor x_{5}\lor x_{6})\land(x_{4}\lor x_{5}\lor x_{6})$ to
$\frac{1}{4}$-MIE and $\frac{1}{4}$-MIAE

Now that we’ve constructed $G$, consider the $p$-I problem on $G$. Assume
there is a solution to the instance of XSAT for $l$-CNF${}_{+}^{l}$. There is
therefore a set of $\frac{n}{l}$ variables set to TRUE in the solution, each
belonging to $l$ clauses. For each of the true variables $x$, add an edge
between $b_{x}$ and $r_{C}$ for each clause $C$ containing $x$. The result of
this addition of $n$ edges is that all red nodes are no longer under illusion
in $G$. However, there are now $\frac{n}{l}$ blue nodes corresponding to the
TRUE variables which each have $l$ new red neighbours. They each require $a$
new blue neighbours to maintain the blue to red neighborhood ratio
$\frac{a}{l}$. We therefore add $a$ edges to each of them, connecting them to
some of the nodes of $B_{D}$, for a total of $\frac{na}{l}$ new edges. This
fully eliminates illusion using a total of $\frac{n}{l}(a+l)$ edges.

Conversely, assume there is a solution to the $p$-I problem on $G$ which uses
$\frac{n}{l}(a+l)$ edges. Let $x_{r},y_{r}$ denote the number of red
neighbours removed in the solution from $x\in R_{C}$, $y\in B_{V}$
respectively. Let $x_{b},y_{b}$ denote the number of blue neighbours added in
the solution from $x\in R_{C}$, $y\in B_{V}$ respectively. We know that each
$x\in R_{C}$ begins under illusion, which the solution can eliminate by adding
a blue neighbour or removing $\lceil\frac{l}{a}\rceil$ red neighbours. Thus

$x_{b}+\left\lfloor\frac{a}{l}\cdot x_{r}\right\rfloor=1$

for each $x\in R_{C}$. As there are $n$ clauses, and the clause nodes form an
independent set, we have

$n=\sum_{x\in R_{C}}\left(x_{b}+\left\lfloor\frac{a}{l}\cdot
x_{r}\right\rfloor\right)$ (57)

Next, if a clause node adds a blue neighbour, it must be a variable node, as
each clause node is adjacent to all other blue nodes. The variable nodes have
$b(b_{x})=\frac{a}{l}r(b_{x})$ for all $b_{x}\in B_{V}$, therefore adding new
red neighbours increases illusion, which can be removed by removing a
different red neighbour, or adding more blue neighbours. This gives us the
following equation:

$\sum_{x\in R_{C}}x_{b}=\sum_{y\in
B_{V}}\left(y_{r}+\left\lfloor\frac{l}{a}\cdot y_{b}\right\rfloor\right)$ (58)

Summing Equations 57 and 58 gives us

$n=\sum_{x\in R_{C}}\left\lfloor\frac{a}{l}\cdot x_{r}\right\rfloor+\sum_{y\in
B_{V}}\left(y_{r}+\left\lfloor\frac{l}{a}\cdot y_{b}\right\rfloor\right)$ (59)

By initial assumption, there exists a solution which uses $\frac{n}{l}(a+l)$
edges. This means

$\sum_{x\in R_{C}}(x_{r}+x_{b})+\sum_{y\in
B_{V}}(y_{r}+y_{b})\leq\frac{n}{l}(a+l)$ (60)

If we subtract Equations 57 and $\frac{a}{l}\cdot$59 from Inequality 60, this
gives us

$\sum_{x\in R_{C}}\left(x_{r}-\frac{l+a}{l}\cdot\left\lfloor\frac{a}{l}\cdot
x_{r}\right\rfloor\right))+\sum_{y\in B_{V}}\left(\frac{l-a}{l}\cdot
y_{r}+y_{b}-\frac{a}{l}\cdot\left\lfloor\frac{l}{a}\cdot
y_{b}\right\rfloor\right)\leq 0$ (61)

Recall that

$x_{b}+\left\lfloor\frac{a}{l}\cdot x_{r}\right\rfloor=1$

for all $x\in R_{C}$, meaning $x_{r}\in\\{0,\lceil\frac{l}{a}\rceil\\}$. This
means the terms $\sum_{x\in
R_{C}}\left(x_{r}-\frac{l+a}{l}\cdot\lfloor\frac{a}{l}\cdot
x_{r}\rfloor\right))$, $\sum_{y\in B_{V}}\frac{l-a}{l}\cdot y_{r}$ and
$\sum_{y\in B_{V}}\left(y_{b}-\frac{a}{l}\cdot\lfloor\frac{l}{a}\cdot
y_{b}\rfloor\right)$ are all non-negative. They must all be equal to 0 to
satisfy Inequality 60. This requires $x_{r}=0$ for all $x\in R_{C}$, $y_{r}=0$
for all $y\in B_{V}$, and finally
$y_{b}=\frac{a}{l}\cdot\lfloor\frac{l}{a}\cdot y_{b}\rfloor$ for all $y\in
B_{V}$. Note that this final equation implies each $y_{b}$ is a multiple of
$a$ because $gcd(a,l)=1$. This simplifies Equations 57 and 59 to:

$n=\sum_{x\in R_{C}}x_{b}$ (62)

$\frac{n}{l}=\sum_{y\in B_{V}}\frac{y_{b}}{a}$ (63)

Together these form all $\frac{n(l+a)}{l}$ edges of the solution. This and the
fact that each $y_{b}$ is a multiple of $a$ implies there are $\frac{n}{l}$
variable nodes which the solution connects to $l$ clauses each, so that each
clause connects to exactly one of its variables. These correspond to the
variables which satisfy the original X-SAT instance, as desired. ∎

######  Theorem 25.

The $p$-IR problem and $p$-I problem is NP-hard for
$p\in\mathbb{Q},\frac{1}{2}<p<1,p\not=\frac{2}{3}$.

###### Proof.

First, $p=\frac{l}{b}>\frac{1}{2}$ for $l,b\in\mathbb{N}\implies 2l>b$,
therefore we can write $p=\frac{l}{b}=\frac{l}{a+l}$ for $l\geq
3,l>a,gcd(l,a)=1$.

Consider an instance of XSAT for $l$-CNF${}_{+}^{l}$ with $n$ variables and
$n$ clauses. We build an auxiliary graph $G=(B\cup R,E)$ such that there is a
solution to this XSAT for $l$-CNF${}_{+}^{l}$ if and only if the $p$-I problem
can be solved by removing $\frac{n}{l}\cdot(l+a)$ edges and adding no edges.
Consequently, this also works as a reduction to $p$-IR. We design the graph
$G$ to have nodes of seven types: blue variable nodes $B_{V}$, where
$|B_{V}|=n$, and red clause nodes $R_{C}$, where $|R_{C}|=n$, as well as Dummy
blue nodes $B_{D}^{C}$ for each clause $C$, where $|B_{D}^{C}|=ln-(n-1)$,
Equalizing blue nodes $B_{E}$, where $|B_{E}|=l-1$, Dummy red nodes
$R_{D}^{C}$ for each clause $C$, where $|R_{D}^{C}|=an-(l-1)$, Equalizing red
nodes $R_{E}$, where $|R_{E}|=a$, and extra blue nodes $B^{\prime}$, where
$|B^{\prime}|=n^{4}$. $G$ will have the following properties:

  * •

Variable nodes: The neighbourhood of $r_{x}$ for all $r_{x}\in R_{V}$ is
$R_{E}\cup\\{b_{c}:b_{c}\in B_{C},x\in C\text{ in the XSAT problem}\\}$. Note
that $r(r_{x})=\frac{a}{l}b(r_{x})$ for all $r_{x}\in R_{V}$.

  * •

Clause nodes: The neighbourhood of $b_{c}$ for all $b_{c}\in B_{C}$ is
$B_{D}^{c}\cup R_{D}^{c}\cup\\{r_{x}:r_{x}\in R_{V},x\in C\text{ in the XSAT
problem}\\}\cup B_{C}-b_{c}$. Note that $r(b_{c})=\frac{a}{l}\cdot b(b_{c})+1$
for all $b_{c}\in B_{C}$.

  * •

Dummy blue nodes: The neighbourhood of $b_{d}$ for all $b_{d}\in B_{D}^{c}$ is
$B^{\prime}\cup\\{b_{c}\\}$. Note no node of $B_{D}$ is under illusion.

  * •

Dummy red nodes: The neighbourhood of $r_{d}$ for all $r_{d}\in R_{D}^{c}$ is
$B_{E}\cup R_{E}\cup\\{b_{c}\\}$. Note $r(r_{d})=\frac{a}{l}b(r_{d})$ for all
$r_{d}\in R_{D}$.

  * •

Equalizing blue nodes: The neighbourhood of $b_{e}$ for all $b_{e}\in B_{E}$
is $R_{D}\cup B^{\prime}$. Note no node of $B_{E}$ is under illusion.

  * •

Equalizing red nodes: The neighbourhood of $r_{e}$ for all $r_{e}\in R_{E}$ is
$B^{\prime}\cup R_{V}\cup\bigcup_{c\text{ is a clause}}R_{D}^{c}$. Note no
node of $R_{E}$ is under illusion.

  * •

Extra blue nodes: The neighbourhood of $b^{\prime}$ for all $b^{\prime}\in
B^{\prime}$ is $B^{\prime}\cup R_{E}\cup B_{E}$. Note no node of $B^{\prime}$
is under illusion.

With $G$ constructed, the reader can see that its construction is analogous to
that in 24, and a nearly identical argument can be applied to complete the
proof. ∎

######  Theorem 26.

The $p$-IA problem is NP-hard for
$p\in\mathbb{Q},\frac{1}{2}<p<1,p\not=\frac{2}{3}$.

###### Proof.

First, $p=\frac{l}{b}>\frac{1}{2}$ for $l,b\in\mathbb{N}\implies 2l>b$,
therefore we can write $p=\frac{l}{b}=\frac{l}{a+l}$ for $l\geq
3,l>a,gcd(l,a)=1$.

Consider an instance of XSAT for $l$-CNF${}_{+}^{l}$ with $n$ variables and
$n$ clauses, where $n\geq 2l$. We build an auxiliary graph $G=(B\cup R,E)$
such that there is a solution to this XSAT for $l$-CNF${}_{+}^{l}$ if and only
if the $p$-IA problem can be solved by adding $\frac{n}{l}\cdot(l+a)$ edges.
We design the graph $G$ to have nodes of eight types: Dummy blue nodes
$B_{D}$, where $|B_{D}|=ln^{2}-(l-1)n$, Dummy red nodes $R_{D}$, where
$|R_{D}|=an^{2}-a(n-2)+\frac{n}{l}$, Equalizing red nodes $R_{E}$, where
$|R_{E}|=a$, Equalizing blue nodes $B_{E}$, where $|B_{E}|=l-1$, blue variable
nodes $B_{V}$, where $|B_{V}|=n$, blue clause nodes $B_{C}$, where
$|B_{C}|=n$, extra red nodes $R^{\prime}$, where $|R^{\prime}|=a(n-2)$, and
extra blue nodes $B^{\prime}$, where $|B^{\prime}|=(l-2)n-(l-1)$. $G$ will
have the following properties:

  * •

Variable nodes: The neighbourhood of $b_{x}$ for all $b_{x}\in B_{V}$ is
$B^{\prime}\cup R^{\prime}\cup\\{b_{c}:b_{c}\in B_{C},x\not\in C\text{ in the
XSAT problem}\\}\cup(B_{V}-b_{x})$. Note that
$b(b_{x})=l(n-2)=\frac{l}{a}a(n-2)=\frac{l}{a}r(b_{x})$ for all $b_{x}\in
B_{V}$.

  * •

Clause nodes: The neighbourhood of $b_{c}$ for all $b_{c}\in R_{C}$ is
$B^{\prime}\cup R^{\prime}\cup R_{E}\cup B_{E}\cup\\{b_{x}:b_{x}\in
B_{V},x\not\in C\text{ in the XSAT problem}\\}\cup B_{C}-b_{c}$. Note that
$b(b_{c})=l(n-1)-1=\frac{l}{a}a(n-1)-1=\frac{l}{a}r(b_{c})-1$ for all
$b_{c}\in B_{C}$.

  * •

Dummy blue nodes: The neighbourhood of $b_{d}$ for all $b_{d}\in B_{D}$ is
$R_{E}\cup B_{E}\cup R^{\prime}\cup B^{\prime}\cup B_{D}-b_{d}$. Note that no
node of $B_{D}$ is under illusion.

  * •

Dummy red nodes: The neighbourhood of $r_{d}$ for all $r_{d}\in R_{D}$ is
$R_{E}\cup B^{\prime}$. Note no node of $R_{D}$ is under illusion.

  * •

Equalizing blue nodes: The neighbourhood of $b_{e}$ for all $b_{e}\in B_{E}$
is $B_{D}\cup B_{C}\cup B^{\prime}$. Note no node of $B_{E}$ is under
illusion.

  * •

Equalizing red nodes: The neighbourhood of $r_{e}$ for all $r_{e}\in R_{E}$ is
$R^{\prime}\cup B^{\prime}\cup R_{D}\cup B_{D}\cup B_{C}\cup B_{E}$. Note each
node $r_{e}$ requires $\frac{n}{l}$ new blue neighbours to correct its
illusion.

  * •

Extra blue nodes: The neighbourhood of $b^{\prime}$ for all $b^{\prime}\in
B^{\prime}$ is $B_{V}\cup R_{D}\cup R_{E}\cup B_{D}\cup B_{C}\cup B_{E}\cup
B^{\prime}-b^{\prime}$. Note no node of $B^{\prime}$ is under illusion.

  * •

Extra red nodes: The neighbourhood of $r^{\prime}$ for all $r^{\prime}\in
R^{\prime}$ is $B_{V}\cup R_{E}\cup B_{D}\cup B_{C}\cup B_{E}$. Note no node
of $R^{\prime}$ is under illusion.

With $G$ constructed, the reader can see that any solution to $p$-IA on $G$
must add $\frac{an}{l}$ edges to correct the deficit of the red nodes. Given
this, the proof that a solution using a total of $\frac{n(l+a)}{l}$ edges
exists if and only if there is a solution to the X-SAT problem follows
directly from the proof of 24. ∎

######  Theorem 27.

The $p$-IR problem is NP-hard for
$p\in\mathbb{Q},0<p<\frac{1}{2},p\not=\frac{1}{3}$.

###### Proof.

First, $p=\frac{a}{b}<\frac{1}{2}$ for $a,b\in\mathbb{N}\implies 2a<b$,
therefore we can write $p=\frac{a}{b}=\frac{a}{a+l}$ for $l\geq
3,l>a,gcd(l,a)=1$.

Consider an instance of XSAT for $l$-CNF${}_{+}^{l}$ with $n$ variables and
$n$ clauses. We build an auxiliary graph $G=(B\cup R,E)$ such that there is a
solution to this XSAT for $l$-CNF${}_{+}^{l}$ if and only if the $p$-IR
problem can be solved by removing $\frac{n}{l}\cdot(l+a)$ edges. We design the
graph $G$ to have nodes of eight types: Dummy blue nodes $B_{D}$, where
$|B_{D}|=a$ Dummy red nodes $R_{D}$, where $|R_{D}|=1$, Equalizing red nodes
$R_{E}$, where $|R_{E}|=l$, Equalizing blue nodes $B_{E}$, where $|B_{E}|=a$,
red variable nodes $R_{V}$, where $|R_{V}|=n$, red clause nodes $R_{C}$, where
$|R_{C}|=n$, extra red nodes $R^{\prime}$, where $|R^{\prime}|=\frac{n}{l}$,
and extra blue nodes $B^{\prime}$, where $|B^{\prime}|=n$. $G$ will have the
following properties:

  * •

Variable nodes: The neighbourhood of $r_{x}$ for all $r_{x}\in R_{V}$ is
$B_{E}\cup\\{r_{c}:r_{c}\in R_{C},x\in C\text{ in the XSAT problem}\\}$. Note
that $b(r_{x})=a=\frac{a}{l}a=\frac{a}{l}r(r_{x})$ for all $r_{x}\in R_{V}$.

  * •

Clause nodes: The neighbourhood of $r_{c}$ for all $r_{c}\in R_{C}$ is
$B_{D}\cup\\{r_{x}:r_{x}\in R_{V},x\in C\text{ in the XSAT problem}\\}$. Note
that $r(r_{c})=l+1=\frac{l}{a}a+1=\frac{l}{a}b(r_{c})$ for all $r_{c}\in
R_{C}$.

  * •

Dummy blue nodes: The neighbourhood of $b_{d}$ for all $b_{d}\in B_{D}$ is
$R_{C}\cup B^{\prime}$. Note that no node of $B_{D}$ is under illusion.

  * •

Dummy red nodes: The neighbourhood of $r_{d}$ for all $r_{d}\in R_{D}$ is
$R_{C}\cup B^{\prime}$. Note no node of $R_{D}$ is under illusion.

  * •

Equalizing blue nodes: The neighbourhood of $b_{e}$ for all $b_{e}\in B_{E}$
is $R^{\prime}\cup R_{V}\cup B^{\prime}$. Note each node $b_{e}$ requires
$\frac{n}{l}$ fewer red neighbours to correct its illusion.

  * •

Equalizing red nodes: The neighbourhood of $r_{e}$ for all $r_{e}\in R_{E}$ is
$R^{\prime}\cup B^{\prime}$. Note no node of $R_{E}$ is under illusion.

  * •

Extra blue nodes: The neighbourhood of $b^{\prime}$ for all $b^{\prime}\in
B^{\prime}$ is $R_{E}\cup B_{D}\cup R_{D}\cup B_{E}\cup
B^{\prime}-b^{\prime}$. Note no node of $B^{\prime}$ is under illusion.

  * •

Extra red nodes: The neighbourhood of $r^{\prime}$ for all $r^{\prime}\in
R^{\prime}$ is $B_{E}\cup R_{E}$. Note
$b(r^{\prime})=a=\frac{a}{l}l=\frac{a}{l}r(r^{\prime})$.

With $G$ constructed, the reader can see that any solution to $p$-IR on $G$
must add $\frac{an}{l}$ edges to correct the deficit of the red nodes. Given
this, the proof that a solution using a total of $\frac{n(l+a)}{l}$ edges
exists if and only if there is a solution to the X-SAT problem follows
directly from the proof of 24. ∎

##  7 Conclusion

We’ve settled the $q$-Illusion Elimination problems studied in [12] for the
special $q=0$ case. While the previous paper showed hardness for $q=(0,1)$ and
a trivial solution for $q=1$, we present here the surprising result that fully
determining and eliminating illusion can be solved in polynomial time. The
three problems, MIAE, MIRE, and MIE, have simple linear programs with integer
solutions.

We also define a natural extension to all three problems. For any $p\in[0,1]$,
the $p$-IA, $p$-IR, and $p$-I problems ask if it is possible to alter a
network to ensure the neighbourhood of every node has a $p$-fraction of blue
nodes by adding edges, removing edges, or both respectively. These problems
reduce to MIAE, MIRE and MIE when $p=\frac{1}{2}$, and just as in those
problems, we ask that the total number of blue nodes be such that the problems
are solvable regardless of the initial network given. We show that these
problems are hard for
$p\in(0,\frac{1}{3})\cup(\frac{1}{3},\frac{1}{2})\cup(\frac{1}{2},\frac{2}{3})\cup(\frac{2}{3},1)$.

In terms of future work, our $p$-IA, $p$-IR, and $p$-I problems have two
$p$-values for which there is no polynomial time algorithm nor a hardness
result: $p=\frac{1}{3}$ and $p=\frac{2}{3}$. Interestingly, if we add edge
weights to the linear programs used to solve MIAE, MIRE and MIE, we can create
linear programs to solve the $p$-IA, $p$-IR, and $p$-I problems. All values of
$p$ except for $p=0,\frac{1}{2},1$ result in a program that is no longer
totally dual integral. However, $p=\frac{1}{3},\frac{2}{3}$ are the only other
values for which the program is half integral. Therefore, it is entirely
possible that for $p=\frac{1}{3},\frac{2}{3}$, these problems are solvable in
polynomial time, which would be an interesting result.

## References

  * Bara et al. [2021] J. Bara, O. Lev, and P. Turrini.  Predicting voting outcomes in presence of communities.  In _Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2021)_ , pages 151–159, 2021.
  * Becker et al. [2023] R. Becker, G. D’Angelo, and S. Ghobadi.  Improving fairness in information exposure by adding links.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 37, pages 14119–14126, 2023.
  * Benevenuto et al. [2006] F. Benevenuto, A. Laender, and B. Alves.  The $h$-index paradox: your coauthors have a higher $h$-index than you do.  _Scientometrics_ , 106:469–474, 2006.
  * Castiglioni et al. [2020] M. Castiglioni, D. Ferraioli, and N. Gatti.  Election control in social networks via edge addition or removal.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 1878–1885, 2020.
  * Cook [1983] W. Cook.  Operations that preserve total dual integrality.  _Operations Research Letters_ , 2(1):31–35, 1983.
  * Doucette et al. [2019] J. Doucette, A. Tsang, H. Hosseini, K. Larson, and R. Cohen.  Inferring true voting outcomes in homophilic social networks.  _Autonomous Agents and Multi-Agent Systems_ , 33:298–329, 2019.
  * Edmonds and Giles [1977] J. Edmonds and R. Giles.  A min-max relation for submodular functions on graphs.  In P. Hammer, E. Johnson, B. Korte, and G. Nemhauser, editors, _Studies in Integer Programming_ , volume 1 of _Annals of Discrete Mathematics_ , pages 185–204. Elsevier, 1977.
  * Eom and Jo [2014] Y. Eom and H. Jo.  Generalized friendship paradox in complex networks: The case of scientific collaboration.  _Scientoific Reports_ , 4:4603, 2014.
  * Faliszewski et al. [2022] P. Faliszewski, R. Gonen, M. Koutecký, and N. Talmon.  Opinion diffusion and campaigning on society graphs*.  _Journal of Logic and Computation_ , 32(6):1162–1194, 2022.
  * Feld [1991] S. Feld.  Why your friends have more friends than you do.  _Am. J. Sociol_ , 96:1464–1477, 1991.
  * Fioravantes et al. [2024] Foivos Fioravantes, Abhiruk Lahiri, Antonio Lauerbach, Marie Diana Sieper, and Samuel Wolf.  Eliminating majority illusion.  hal-04574647, 2024.
  * Grandi et al. [2023] U. Grandi, L. Kanesh, G. Lisowski, R. Sridharan, and P. Turrini.  Identifying and eliminating majority illusion in social networks.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 37(4):5062–5069, 2023.
  * Grötschel et al. [1988] M. Grötschel, L. Lovász, and A. Schrijver.  _Geometric Algorithms and Combinatorial Optimization_.  Springer-Verlag, 1988.
  * Johnson et al. [2020] N. Johnson, N. Velásquez, N. Restrepo, R. Leahy, N. Gabriel, S. El Oud, M. Zheng, P. Manrique, S. Wuchty, and Y. Lupu.  The online competition between pro- and anti-vaccination views.  _Nature_ , 582(7811):230–233, 2020.
  * Kempe et al. [2020] D. Kempe, S. Yu, and Y. Vorobeychik.  Inducing equilibria in networked public goods games through network structure modification.  In _Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems_ , pages 611–619, 2020.
  * Lerman et al. [2016] K. Lerman, X. Yan, and X-Z. Wu.  The “majority illusion” in social networks.  _PLOS ONE_ , 11(2):1–13, 2016.
  * Letchford et al. [2008] A. Letchford, G. Reinelt, and D. Theis.  Odd minimum cut sets and $b$-matchings revisited.  _SIAM Journal on Discrete Mathematics_ , 22(4):1480–1487, 2008.
  * Liu et al. [2023] X. Liu, S. Kato, F. Ren, G. Su, M. Zhang, and W. Gu.  Information gerrymandering in elections.  In S. Wu, W. Yang, M. Amin, B-H. Kang, and G. Xu, editors, _Knowledge Management and Acquisition for Intelligent Systems_ , pages 83–97. Springer Singapore, 2023.
  * McPherson et al. [2001] M. McPherson, L. Smith-Lovin, and J. Cook.  Birds of a feather: Homophily in social networks.  _Annual Review of Sociology_ , 27(1):415–444, 2001.
  * Padberg and Rao [1982] M. Padberg and M. Rao.  Odd minimum cut-sets and $b$-matchings.  _Mathematics of Operations Research_ , 7(1):67–80, 1982.
  * Schmidt [2011] Tatjana Schmidt.  _Computational complexity of SAT, XSAT and NAE-sat for linear and mixed horn CNF formulas_.  Südwestdeutscher Verlag für Hochschulschriften, 2011.
  * Schrijver [2003] A. Schrijver.  _Combinatorial Optimization: Polyhedra and Efficiency_ , volume B.  Springer-Verlag, 2003.
  * Stewart et al. [2019] A. Stewart, M. Mosleh, M. Diakonova, A. Arechar, D. Rand, and J. Plotkin.  Information gerrymandering and undemocratic decisions.  _Nature_ , 573(7772):117–121, 2019.
  * Wilder and Vorobeychik [2018] B. Wilder and Y. Vorobeychik.  Controlling elections through social influence.  In _Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS)_ , page 265–273. International Foundation for Autonomous Agents and Multiagent Systems, 2018.
  * Yu et al. [2021] S. Yu, D. Kempe, and Y. Vorobeychik.  Altruism design in networked public goods games.  _arXiv:2105.00505_ , 2021.
  * Zhou and Zhang [2021] X. Zhou and Z. Zhang.  Maximizing influence of leaders in social networks.  In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_, pages 2400–2408, 2021.