💻 computer science

Eliminating Illusion in Directed Networks

This paper investigates the NP-hard and W[2]-hard complexity of eliminating $p$ -illusion in directed networks by recoloring vertices, while identifying polynomial-time solutions for specific sparse structures and establishing fixed-parameter tractability with respect to the underlying graph's treewidth and the number of affected vertices.

Original authors: Sougata Jana, Sanjukta Roy

Published 2026-04-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sougata Jana, Sanjukta Roy

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are walking through a crowded town square. Everyone is wearing either a Red shirt or a Blue shirt.

In this town, there's a strange psychological trick called "The Illusion."

The Problem: The "False Majority" Illusion

Let's say 60% of the whole town is wearing Blue (the true majority). However, because of how the town is laid out, a specific person named Alice might only see her immediate neighbors. If Alice's neighbors are mostly Red, she looks around and thinks, "Wow, Red is clearly the dominant color here!"

Even though Red is actually the minority in the whole town, Alice is under an illusion. She believes the minority opinion is the majority.

This paper studies what happens when this illusion spreads through a Directed Network. Think of a directed network like a one-way street system or a social media feed where you follow people, but they don't necessarily follow you back.

The Goal: We want to stop this illusion. We want to make sure that every single person in the town sees enough Blue neighbors to realize, "Oh, Blue is actually the majority."
The Cost: To fix this, we have to change people's shirts. We can take a Red shirt and paint it Blue. But painting shirts costs money (or effort). We want to fix the illusion by changing the minimum number of shirts possible.

The authors ask: Is this a solvable puzzle, or is it a nightmare?

The Plot Twist: It's a Nightmare (Mostly)

The researchers discovered that for most types of town layouts, this puzzle is incredibly hard. In computer science terms, it's NP-hard.

The Grid Nightmare: Imagine the town is a perfect grid (like a city block). Even if the streets are one-way, figuring out the cheapest way to fix the illusion is so complex that no computer can solve it quickly, no matter how powerful it is. It's like trying to solve a Rubik's cube that keeps changing its rules while you're holding it.
The "Acyclic" Trap: You might think, "What if the town has no loops? What if everyone only influences people 'downstream' (like a corporate hierarchy)?" You'd think that would make it easier. The authors proved that even in these simple, loop-free hierarchies, the problem remains incredibly difficult. It's so hard that if we could solve it quickly, we would break the fundamental rules of computer science (proving P=NP).

The "p-Illusion" Twist:
The authors didn't just stop at "Majority." They introduced a variable called $p$ .

Maybe you don't need 51% Blue to feel safe; maybe you need 90% (like a vaccine herd immunity).
Or maybe you just need to see a tiny minority (like 10%) to feel represented.
The paper shows that no matter what percentage you pick, the problem remains a computational nightmare on complex networks.

The Silver Lining: Where It Gets Easy

Just because the puzzle is hard in a chaotic city doesn't mean it's hard everywhere. The authors found specific "town shapes" where the solution is easy to find:

The Outward Grid: Imagine a grid where everyone only looks Right and Down. If the influence only flows in one direction (like water flowing down a slide), we can solve the puzzle quickly.
Trees and Cycles: If the network looks like a family tree (one parent, many kids) or a simple circle, we can use a step-by-step recipe (an algorithm) to fix the shirts efficiently.
Sparse Networks: If the town is small and people don't have too many neighbors, the math becomes manageable.

The "Magic" Shortcuts (Parameterized Algorithms)

The authors also found two "cheat codes" that make the problem solvable, even in messy towns, if certain conditions are met:

The "Tree-Like" Structure: If the town's layout is "tree-like" (mathematically measured by something called treewidth), we can solve it. Think of this as the town having very few cross-streets and mostly long, straight avenues.
The "Few Victims" Rule: What if only a handful of people are currently suffering from the illusion? The authors showed that if the number of "sick" people is small, we can fix the problem quickly, regardless of how big the town is. It's like a doctor saying, "I can cure the whole city if only 5 people are sick, even if the city has a million people."

The Real-World Takeaway

Why does this matter?

Politics & Ads: Politicians and advertisers use these illusions to make a fringe idea look like a mainstream movement. This paper helps us understand how hard it is to "debunk" those lies by changing just a few key opinions.
Public Health: In a pandemic, if people think "everyone is vaccinated" (even if they aren't), they might stop getting shots. This research helps us figure out the minimum number of people we need to convince to stop the false perception.
Social Media: It explains why your "echo chamber" feels so real, even if the rest of the world disagrees.

Summary in One Sentence

The paper proves that while fixing false perceptions in complex, one-way social networks is usually a mathematically impossible task for computers, there are specific, structured situations where we can efficiently find the cheapest way to set the record straight.

1. Problem Definition

The paper addresses the computational complexity of Illusion Elimination in directed social networks.

Context: In social networks, agents (vertices) hold opinions (colored Red or Blue). A "majority illusion" occurs when a vertex perceives the minority opinion (Red) as the majority among its out-neighbors, even if the global network has more Blue vertices.
Generalization ( $p$ -illusion): The authors generalize this to $p$ -illusion, where a vertex $v$ $v$ is under illusion if the fraction of its red out-neighbors exceeds a threshold $p \in (0,1)$ $p \in (0, 1)$ .
- If $p=1/2$ , this is the standard majority illusion.
- If $p > 1/2$ , it models scenarios requiring super-majority (e.g., herd immunity).
- If $p < 1/2$ , it models the misperception of minority groups.
The Problem ( $p$ -DIFR): Given a directed graph $G=(V,E)$ , a coloring function $f$ , and an integer $k$ , can we recolor at most $k$ vertices (specifically changing Red to Blue, as recoloring Blue is never beneficial) such that no vertex remains under $p$ -illusion?
Goal: Find the minimum number of recolorings to make the graph illusion-free.

2. Methodology and Approach

The authors employ a mix of complexity theory, graph theory, and algorithmic design:

Complexity Reductions: They reduce known NP-complete and W[2]-hard problems (specifically Planar Monotone Rectilinear 3-SAT and Hitting Set) to the $p$ -DIFR problem to establish hardness results.
Structural Analysis: They analyze how graph topology (grids, DAGs, trees, cycles) influences tractability.
Algorithmic Techniques:
- Greedy/Reduction Rules: For specific structures like cycles and outward grids, they use safe reduction rules (e.g., if a vertex has only one red out-neighbor, it must be recolored).
- Graph Matching: For outward grids, they reduce the problem to finding a Minimum Vertex Cover on an auxiliary bipartite graph.
- Dynamic Programming (DP): For trees and graphs with bounded treewidth, they design DP algorithms that track the state of vertices in a tree decomposition (bag) and the number of recolored neighbors.
- Integer Linear Programming (ILP): They formulate the problem as an ILP to prove Fixed-Parameter Tractability (FPT) with respect to the number of vertices currently under illusion.

3. Key Contributions and Results

A. Hardness Results (Intractability)

The paper establishes that the problem is computationally difficult even on restricted graph classes:

NP-Completeness on Grids: The problem is NP-complete even when the graph is a directed grid. This implies no polynomial-time algorithm exists for planar graphs or grids unless P=NP.
W[2]-Hardness on DAGs: The problem is W[2]-hard when parameterized by the solution size $k$ $k$ (number of recolorings), even on bipartite Directed Acyclic Graphs (DAGs).
- Significance: This rules out the existence of Fixed-Parameter Tractable (FPT) algorithms parameterized by $k$ for DAGs (unless FPT=W[2]).
- It also implies hardness with respect to parameters measuring distance from acyclicity (e.g., directed feedback vertex set, directed treewidth).
Hardness on Subgraphs: The undirected version of the problem is also NP-hard on subgraphs of grids.

B. Tractable Cases (Polynomial Time)

Despite the general hardness, the authors identify specific topologies where the problem is solvable in polynomial time:

Outward Grids: Directed grids where edges flow only "right" and "down" (hierarchical flow). The problem is solvable in $O(mn\sqrt{mn})$ .
Trees and Cycles:
- Directed Cycles: Solvable in linear time $O(n)$ .
- Directed Trees: Solvable in $O(n^4)$ using dynamic programming.
- Underlying Undirected Trees/Cycles: The problem remains polynomial even if the direction of edges in a tree or cycle is arbitrary.
Outerplanar Graphs: The problem is solvable in polynomial time for $\lambda$ -outerplanar graphs.

C. Parameterized Algorithms (FPT)

The authors provide FPT algorithms for specific parameters:

Parameterized by Treewidth and Maximum Deficiency ( $D$ ):
- They design a DP algorithm on a tree decomposition of the underlying undirected graph.
- Runtime: $O((2D)^{tw} \cdot n^{O(1)})$ , where $tw$ is the treewidth and $D$ is the maximum deficiency (number of extra red neighbors needed to fix).
Parameterized by Number of Illusion Vertices ( $|X_p|$ ):
- Using an ILP formulation with $|X_p|$ constraints, they show the problem is FPT with respect to the number of vertices currently under illusion.
- Runtime: $2^{|X_p|\log|X_p|} \cdot n^{O(1)}$ .

4. Significance and Implications

Theoretical Boundary: The paper draws a sharp line between tractable and intractable cases for illusion elimination. It demonstrates that while acyclic graphs (DAGs) are often "easy" in other contexts, the directed nature of influence makes illusion elimination hard even there.
Real-world Application: The results are crucial for designing network interventions. For example, in vaccination campaigns (where $p$ -illusion models herd immunity thresholds), the paper suggests that if the network is a general grid or complex DAG, finding the optimal set of agents to influence is computationally infeasible. However, for hierarchical structures (out-trees, outward grids), efficient strategies exist.
Generalization: By moving from majority ( $p=1/2$ ) to general $p$ -illusion, the paper provides a framework applicable to various social phenomena, from political polarization to public health.

5. Summary of Complexity Table

Graph Class	DIFR (Majority, $p=1/2$ )	p-DIFR (General $p$ )
Directed Grids	NP-complete	NP-complete
Bipartite DAGs	NP-complete (W[2]-hard by $k$ )	NP-complete (W[2]-hard by $k$ )
Outward Grids	P	P
Trees / Cycles	P	P
Outerplanar	P	P
General Graphs	FPT (by $tw + D$)	FPT (by $tw + D$ and $\|X_p\|$ )

In conclusion, the paper provides a comprehensive complexity landscape for eliminating social illusions in directed networks, proving that while the problem is generally hard, efficient solutions exist for structured, sparse, or hierarchical networks.