💻 computer science

What Makes Majority Illusion Easy to Detect?

This paper investigates the computational complexity of detecting the "majority illusion" in social networks by analyzing how various structural properties influence the tractability of determining whether a network configuration exists where a significant fraction of agents mistakenly perceive a minority opinion as dominant.

Original authors: Šimon Schierreich, Ildikó Schlotter

Published 2026-06-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Šimon Schierreich, Ildikó Schlotter

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 a social network as a giant party where everyone is wearing either a Blue shirt or a Red shirt. In this paper, the authors are studying a weird psychological glitch called the "Majority Illusion."

Here is the glitch: Even if 60% of the party is wearing Blue, a specific person might look around at their immediate circle of friends and see that most of them are wearing Red. Because humans tend to think "my friends represent the world," that person mistakenly believes Red is the dominant color. If enough people have this wrong impression, the whole party's decision-making gets twisted.

The paper asks a very specific question: How hard is it for a computer to figure out if a party layout exists where this illusion happens?

The authors treat the party layout as a map (a graph) and try to find the "rules" that make solving this puzzle easy or impossible. Here is a breakdown of their findings using simple analogies:

1. The "Super-Connector" Rule (Vertex Integrity)

The Concept: Imagine a party where there are a few famous "Super-Connectors" who know everyone, and then there are many small, isolated groups of friends who only know each other.
The Finding: If the party has this structure, the computer can solve the puzzle very quickly.
The Analogy: Think of the Super-Connectors as the "VIPs" at the door. If you just figure out what color the VIPs are wearing, the rest of the party (the small groups) is easy to predict because they are isolated. The authors used a complex math trick (called "N-fold Integer Programming") to prove that if you can break the party down into a few VIPs and small, independent clusters, the problem becomes easy to solve.

2. The "Tree" vs. "Forest" Rule (Feedback Edge Set)

The Concept: Imagine the party connections form a tree (no loops, just branches).
The Finding: If the party looks like a tree, the computer can solve it quickly. Even better, if the party is almost a tree (you only need to cut a few "bridges" to turn it into a tree), it's still easy.
The Analogy: A tree is a simple path with no circles. If you have a few extra bridges creating loops, the computer can just "cut" those bridges, solve the puzzle for the tree, and then glue the bridges back in.
The Surprise: However, if you have to remove people (vertices) to turn the party into a tree, the problem becomes impossible for the computer to solve efficiently. It's like saying, "If we just kick a few people out, the party becomes simple." The authors found that even removing a few people doesn't make the math easy; the complexity explodes.

3. The "Star" and "Path" Trap

The Concept:

Stars: One person in the middle with many friends radiating out (like a starfish).
Paths: People standing in a single line, holding hands.
The Finding:
If the party is just a bunch of separate lines (paths), the computer can solve it instantly. It's like arranging beads on a string; there's a clear pattern.
But, if the party is almost a bunch of stars (you just need to remove a few people to make them stars), the problem becomes impossible to solve efficiently.
The Analogy: A line of people is predictable. But if you have a few "hub" people connecting many stars, the web of influence gets tangled in a way that creates a mathematical nightmare for the computer.

4. The "Clubs" Rule (Distance to Cliques)

The Concept: Imagine the party is made up of several tight-knit clubs (cliques) where everyone in the club knows everyone else.
The Finding:

If you have to remove a few people to get these perfect clubs, the problem is "hard" (though not impossible, it gets slower as the party grows).
If you have to remove a few friendships (edges) to get these perfect clubs, the problem becomes easy again.
The Analogy:
Removing People: If you have to kick people out to fix the clubs, you are changing the structure of the groups in a way that creates too many variables.
Removing Friendships: If you just have to cut a few bad connections to make the clubs perfect, the computer can easily handle it. It's like fixing a messy room by just moving a few items (edges) rather than throwing out the furniture (people).

The Big Picture: What Makes It Easy?

The authors conclude that for a computer to easily detect this "Majority Illusion," the social network usually needs to fall into one of three categories:

It's almost a tree (you only need to cut a few bridges).
It's made of small, independent islands (you can remove a few "Super-Connectors" to leave small groups).
It's almost a collection of perfect clubs (you only need to cut a few friendships to make the clubs perfect).

If the network is messy in any other way (like needing to remove people to fix the structure, or having complex loops), the computer hits a wall and the problem becomes computationally "intractable"—meaning it would take longer than the age of the universe to solve for a large party.

In short: The paper maps out exactly which social network shapes allow us to quickly spot when people are being tricked by their friends, and which shapes make it a mathematical impossibility.

Technical Summary: What Makes Majority Illusion Easy to Detect?

Problem Definition

The paper investigates the computational complexity of detecting Majority Illusion in social networks. Formally, a social network is modeled as an undirected graph $G = (N, E)$ where vertices represent agents and edges represent social relationships. Agents are assigned a binary label (e.g., "red" or "blue"). An agent is under majority illusion if they perceive the minority label as dominant within their local neighborhood.

The central decision problem is the $q$ -Majority Illusion problem: Given a graph $G$ and a rational $q \in [0, 1]$ , does there exist a binary labeling of the agents such that the majority color is one specific label (say, blue), yet at least a $q$ -fraction of agents have a strict majority of neighbors with the minority label (red)?

Previous work by Grandi et al. (2025) established that this problem is NP-complete in general, even for restricted graph classes like bipartite graphs, planar graphs, or graphs with maximum degree 6. While they provided Fixed-Parameter Tractable (FPT) algorithms for parameters like vertex cover number and neighborhood diversity, and showed the problem is in XP for treewidth, they left open the question of which structural restrictions render the problem efficiently solvable (FPT) versus intractable.

Methodology

The authors employ the framework of parameterized complexity to analyze the tractability of the $q$ -Majority Illusion problem. They systematically study the problem with respect to various structural graph parameters, including:

Vertex Integrity ($vi(G)$): The minimum size of a vertex set whose removal leaves components of bounded size.
Feedback Edge Set ($fes(G)$) and Feedback Vertex Set ($fvs(G)$): The minimum number of edges or vertices to remove to make the graph acyclic.
Distance to Graph Classes: Parameters measuring the vertex or edge distance to specific classes such as disjoint stars, disjoint paths, and cluster graphs (disjoint unions of cliques).
Treedepth ($td(G)$) and Treewidth ($tw(G)$): Standard structural parameters.

The methodology involves two primary algorithmic techniques:

N-fold Integer Linear Programming (ILP): Used to prove FPT results for parameters like vertex integrity. The problem is formulated as an N-fold IP where constraints are separated into global constraints (ensuring the global majority and total count of illusioned agents) and local constraints (ensuring local neighborhood conditions for specific components).
Dynamic Programming (DP): Used for tree-like structures (trees, paths) and graphs close to such structures. For trees, the authors design a polynomial-time algorithm for a related "Max List Majority Illusion" problem, which serves as a subroutine for FPT algorithms based on feedback edge sets.

For hardness results, the authors provide parameterized reductions from known W[1]-hard problems, specifically Multidimensional Subset Sum (and its Halfset variant) and Capacitated Vertex Cover.

Key Contributions and Results

1. Fixed-Parameter Tractability (FPT)

The paper establishes FPT algorithms for several new parameterizations:

Vertex Integrity ($vi(G)$): The authors prove that $q$ -Majority Illusion is in FPT when parameterized by vertex integrity. The algorithm guesses the labeling of the "separator" set $M$ and uses N-fold ILP to extend this labeling to the remaining small components. This result also yields an improved running time for the vertex cover number ($vc(G)$), reducing the complexity from doubly exponential ( $2^{2^{O(vc)}}$ ) to single exponential ( $2^{O(vc^2 \log vc)}$ ).
Feedback Edge Set ($fes(G)$): The problem is shown to be in FPT when parameterized by the feedback edge set number. The approach involves guessing the labeling of vertices incident to the feedback edges, transforming the graph into a tree with "gadgets" (pendant leaves), and solving the resulting instance using a polynomial-time dynamic programming algorithm on trees.
Cluster Edge Deletion Number ($cdn(G)$): For graphs that become a disjoint union of cliques after removing a bounded number of edges, the problem is in FPT. The algorithm guesses the labeling of the endpoints of the removed edges and uses dynamic programming over the cliques, leveraging the fact that the status of agents within a clique depends only on the number of red agents and the fixed external connections.

2. W[1]-Hardness and Intractability

The paper provides strong negative results, showing that the problem remains hard even for graphs that are "close" to simple structures:

Distance to Disjoint Stars ($dds(G)$): The problem is W[1]-hard when parameterized by the vertex distance to disjoint stars. This is proven via a reduction from Multidimensional Halfset Sum.
Distance to Disjoint Paths ($ddp(G)$): Similarly, the problem is W[1]-hard when parameterized by the vertex distance to disjoint paths.
Treedepth ($td(G)$): The problem is W[1]-hard when parameterized by treedepth. This resolves a significant open question from Grandi et al. (2025), implying that an FPT algorithm for treewidth (which is bounded by treedepth) is unlikely under standard complexity assumptions.
Distance to Cluster Graphs ($dcg(G)$): The problem is in XP but W[1]-hard when parameterized by the vertex distance to cluster graphs. This contrasts with the FPT result for edge distance to cluster graphs ($cdn(G)$).

3. Polynomial-Time Solvability on Specific Classes

The authors provide a linear-time algorithm for graphs that are unions of disjoint paths. They derive a closed-form expression for the maximum number of agents under majority illusion in a path based solely on the number of agents, showing that the problem is trivially solvable on paths and disjoint paths.

Significance and Conclusion

The paper's primary contribution is a comprehensive "map" of the computational complexity landscape for the Majority Illusion detection problem. It clarifies the boundary between tractable and intractable instances by identifying specific structural properties that enable efficient detection.

The authors conclude that for the problem to be tractable (FPT), the social network must satisfy one of three conditions:

It is within a bounded edge-distance from a class where the problem is polynomial-time solvable (e.g., trees via feedback edge set, or cluster graphs via cluster edge deletion).
It is within a bounded vertex-distance from components of bounded size (e.g., via vertex integrity).
It consists of a bounded number of well-structured blocks (e.g., bounded neighborhood diversity).

The results highlight a sharp dichotomy: while removing a small number of edges to reach a simple structure often yields FPT algorithms, removing a small number of vertices to reach the same structure often leads to W[1]-hardness. The paper leaves open the complexity of the problem when parameterized by the twin-cover number, noting that it lies between the vertex distance to cluster graphs (XP) and the edge distance to cluster graphs (FPT), and questions whether the additional twin structure allows for an FPT algorithm.