arxiv: 2604.02395 · v1 · submitted 2026-04-02 · 💻 cs.DS · cs.CC· cs.MA

Recognition: no theorem link

Eliminating Illusion in Directed Networks

Sougata Jana , Sanjukta Roy

Authors on Pith no claims yet

Pith reviewed 2026-05-13 21:01 UTC · model grok-4.3

classification 💻 cs.DS cs.CCcs.MA

keywords illusion eliminationdirected networksp-illusionNP-hardnessW[2]-hardnesstreewidthrecoloringsocial networks

0 comments

The pith

Finding the minimum recolorings to eliminate p-illusion in directed networks is NP-hard even on grids and bipartite DAGs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines the task of changing the fewest vertex colors in a directed red-blue network so that no vertex sees at least a p-fraction of red out-neighbors when the global majority is blue. It establishes that this minimum-recoloring problem is NP-hard for the majority case p = 1/2 even on grids and both NP-hard and W[2]-hard parameterized by the number of recolorings for every p in (0,1) even on bipartite DAGs. The authors supply polynomial-time algorithms for outerplanar networks, outward grids, trees, and cycles, plus fixed-parameter tractable algorithms when the underlying undirected graph has bounded treewidth or when the number of initially illusioned vertices is small. These boundaries separate the cases where efficient exact solutions are possible from those where they are not.

Core claim

In a directed network with red and blue vertices, a vertex suffers p-illusion when at least p of its out-neighbors are red. The directed illusion elimination problem asks for the smallest set of vertices to recolor so that no p-illusion remains, for any fixed p in (0,1). This problem is NP-hard for p = 1/2 even on grid graphs and W[2]-hard parameterized by solution size on bipartite DAGs for every p. It is solvable in polynomial time on outerplanar networks, outward grids, trees, and cycles, and it is fixed-parameter tractable parameterized by the treewidth of the underlying undirected graph or by the number of vertices that begin under illusion.

What carries the argument

The p-illusion flag, triggered when the fraction of red out-neighbors meets or exceeds p against the global color majority, and the minimum vertex recoloring set that removes every such flag.

Load-bearing premise

Illusion depends strictly on the fraction of red out-neighbors versus the global color majority, with no other social or temporal factors involved.

What would settle it

A polynomial-time algorithm computing the minimum recolorings on arbitrary grids or bipartite DAGs would contradict the stated NP-hardness and W[2]-hardness results.

Figures

Figures reproduced from arXiv: 2604.02395 by Sanjukta Roy, Sougata Jana.

**Figure 1.** Figure 1: Illusions in different networks For example, the two colors can represent a two-party election.1 If there are more blue voters than red, then we say that blue is the majority. A voter is under majority illusion if it has strictly more red out-neighbors than blue out-neighbors. There can be instances where some or all vertices are under majority illusion (see [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

**Figure 2.** Figure 2: Cycle gadget for variable x: edge (v x(2ℓx) ,v 1 x ) not shown. Proof. Let ϕ be an instance of the PLANAR MONOTONE RECTILINEAR 3-SAT problem. Let k be the number of variables in ϕ. We construct an instance (G, f,k ′ ) of DIFR. The vertex set of G is constructed as follows: (i) For every variable x, we add two sets of variable vertices, namely the positive variable vertices {v i x |i ∈ [ℓx]} and the negativ… view at source ↗

**Figure 3.** Figure 3: Grid reduction excerpt from Theorem 1. We show that the constructed graph G is planar by providing the following embedding. Embedding of G. To find a grid embedding of the graph constructed so far, we adapt the planar rectilinear embedding of the incidence graph of ϕ. We embed the cycle gadget for a variable x along the horizontal and vertical legs connected to x in the rectilinear embedding. Let c be a cl… view at source ↗

**Figure 4.** Figure 4: Construction in Theorem 2, with A1 = {u1,u2}, A2 = {u1,u3,un} (ii) For each ui ∈ Aj , add edge (vj ,ri), and add edges (vj ,bℓ), for ℓ = 1,2,...,x j , for each j ∈ [m], where xj is a natural number such that j pdj−1 1−p k ≤ xj < l pdj 1−p m . Note that the number xj exists since p < 1 and dj > l 1 p m (i.e., pdj −1 > 0). Let us call the graph so created as G = (V,E). This completes the construction. It can… view at source ↗

**Figure 5.** Figure 5: The two cases in the proof of Proposition 2 [PITH_FULL_IMAGE:figures/full_fig_p014_5.png] view at source ↗

read the original abstract

We study illusion elimination problems on directed social networks where each vertex is colored either red or blue. A vertex is under \textit{majority illusion} if it has more red out-neighbors than blue out-neighbors when there are more blue vertices than red ones in the network. In a more general phenomenon of $p$-illusion, at least $p$ fraction of the out-neighbors (as opposed to $1/2$ for majority) of a vertex is red. In the directed illusion elimination problem, we recolor minimum number of vertices so that no vertex is under $p$-illusion, for $p\in (0,1)$. Unfortunately, the problem is NP-hard for $p =1/2$ even when the network is a grid. Moreover, the problem is NP-hard and W[2]-hard when parameterized by the number of recolorings for each $p \in (0,1)$ even on bipartite DAGs. Thus, we can neither get a polynomial time algorithm on DAGs, unless P=NP, nor we can get a FPT algorithm even by combining solution size and directed graph parameters that measure distance from acyclicity, unless FPT=W[2]. We show that the problem can be solved in polynomial time in structured, sparse networks such as outerplanar networks, outward grids, trees, and cycles. Finally, we show tractable algorithms parameterized by treewidth of the underlying undirected graph, and by the number of vertices under illusion.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper defines p-illusion elimination on directed graphs and gives standard hardness plus some tractable cases, but the modeling choices limit how far the results travel.

read the letter

The main takeaway is that minimum recoloring to remove all p-illusions is NP-hard on grids for p=1/2 and W[2]-hard parameterized by solution size on bipartite DAGs for any p in (0,1). On the positive side the authors give polynomial-time algorithms for outerplanar graphs, outward grids, trees and cycles, plus FPT results by treewidth of the underlying undirected graph and by the number of initially illusory vertices. These are clean separations using familiar techniques for local recoloring problems. The extension from majority illusion to general p is the clearest new piece. The results line up with what one would expect from reductions on grids and dynamic programming on bounded-treewidth graphs, so the internal logic holds without obvious gaps. The main soft spot is the model itself: illusion is defined strictly by the fraction of red out-neighbors versus the global color count, with no room for other influences such as edge weights, temporal effects or vertex-specific thresholds. That choice makes the hardness results sharper but also narrows the practical scope. The paper is aimed at people working on parameterized algorithms for social-network problems. A reader already interested in recoloring or influence problems on directed graphs will get concrete complexity boundaries and some usable algorithms for sparse cases. It is worth sending to peer review because the problem is new, the classifications are explicit, and the positive results are on natural graph classes.

Referee Report

0 major / 3 minor

Summary. The paper studies the directed illusion elimination problem on vertex-colored directed networks, where a vertex is under p-illusion if at least a p-fraction of its out-neighbors are red (for p in (0,1)), with the global color majority determining the illusion threshold. The central claims are that the minimum-recoloring problem is NP-hard for p=1/2 even on grids, NP-hard and W[2]-hard parameterized by the number of recolorings for every p in (0,1) even on bipartite DAGs, solvable in polynomial time on outerplanar networks, outward grids, trees, and cycles, and FPT when parameterized by treewidth of the underlying undirected graph or by the number of initially illusory vertices.

Significance. If the stated hardness and algorithmic results hold, the work provides a useful complexity map for a natural recoloring problem motivated by social-network phenomena. The combination of strong intractability results (including W[2]-hardness on bipartite DAGs) with positive polynomial-time and FPT results on restricted classes (trees, cycles, bounded-treewidth graphs) is a standard but valuable contribution to algorithmic graph theory applied to network intervention problems.

minor comments (3)

[Abstract] Abstract: the term 'outward grids' is used without definition; a one-sentence clarification of the orientation or embedding would help readers unfamiliar with the class.
The dynamic-programming algorithms parameterized by treewidth are asserted to exist, but the state space (how illusion status and color counts are tracked across bags) should be sketched explicitly in the main text to allow verification of the running-time bound.
The reduction establishing W[2]-hardness on bipartite DAGs is described at a high level; confirming that the construction preserves the p-illusion predicate for arbitrary p in (0,1) would strengthen the claim.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work on the directed illusion elimination problem and for recommending minor revision. The provided summary accurately reflects the paper's main contributions regarding NP-hardness results on grids and bipartite DAGs, polynomial-time solvability on restricted classes such as trees and outerplanar networks, and FPT results parameterized by treewidth or the number of illusory vertices.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper establishes NP-hardness via explicit reductions from known problems (e.g., on grids for p=1/2 and on bipartite DAGs for general p) and W[2]-hardness parameterized by solution size, together with FPT algorithms via treewidth DP and by counting initially illusory vertices. These are standard complexity-theoretic techniques that do not reduce to self-definitions, fitted parameters renamed as predictions, or load-bearing self-citations. The illusion predicate is defined directly from the input graph and color counts without circular reference to the output recoloring set. No ansatz or uniqueness theorem is smuggled in; the results are self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the standard assumption that the input is a finite directed graph with a 2-coloring and that illusion is defined solely by out-neighbor color fractions versus global majority. No free parameters or invented entities are introduced.

axioms (2)

domain assumption The input is a finite directed graph whose vertices are colored red or blue.
Basic modeling choice stated in the problem definition.
domain assumption Illusion is determined exclusively by the fraction of red out-neighbors compared with the global color majority.
Core definition of p-illusion used throughout the hardness and algorithm statements.

pith-pipeline@v0.9.0 · 5568 in / 1331 out tokens · 34136 ms · 2026-05-13T21:01:57.739304+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

[1]

Majority colorings of sparse digraphs.The Electronic Journal of Combinatorics, pages P2–31, 2021

Michael Anastos, Ander Lamaison, Raphael Steiner, and Tibor Szabó. Majority colorings of sparse digraphs.The Electronic Journal of Combinatorics, pages P2–31, 2021

work page 2021
[2]

Oxford University Press, 1992

Roy M Anderson and Robert M May.Infectious diseases of humans: dynamics and control. Oxford University Press, 1992

work page 1992
[3]

Approximation algorithms for np-complete problems on planar graphs.Journal of the ACM (JACM), 41(1):153–180, 1994

Brenda S Baker. Approximation algorithms for np-complete problems on planar graphs.Journal of the ACM (JACM), 41(1):153–180, 1994

work page 1994
[4]

Predicting voting outcomes in presence of communities

Jacques Bara, Omer Lev, and Paolo Turrini. Predicting voting outcomes in presence of communities. InProceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2021), pages 151–159. International Foundation for Autonomous Agents and Multiagent Systems; ACM, 2021

work page 2021
[5]

A partial k-arboretum of graphs with bounded treewidth.Theoretical computer science, 209(1-2):1–45, 1998

Hans L Bodlaender. A partial k-arboretum of graphs with bounded treewidth.Theoretical computer science, 209(1-2):1–45, 1998. 21

work page 1998
[6]

Manipulating opinion diffusion in social networks

Robert Bredereck and Edith Elkind. Manipulating opinion diffusion in social networks. InIJCAI International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence, 2017

work page 2017
[7]

Extending the graph theory of majority illusions.Master’s thesis, 2025

Naomï Broersma. Extending the graph theory of majority illusions.Master’s thesis, 2025

work page 2025
[8]

Election control in social networks via edge addition or removal

Matteo Castiglioni, Diodato Ferraioli, and Nicola Gatti. Election control in social networks via edge addition or removal. InProceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 1878–1885, 2020

work page 2020
[9]

Springer, 2015

Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.Parameterized algorithms, volume 5. Springer, 2015

work page 2015
[10]

Optimal binary space partitions for segments in the plane

Mark De Berg and Amirali Khosravi. Optimal binary space partitions for segments in the plane. International Journal of Computational Geometry & Applications, 22(03):187–205, 2012

work page 2012
[11]

Eliminating majority illusion is easy

Jack Dippel, Max Dupré la Tour, April Niu, Sanjukta Roy, and Adrian Vetta. Eliminating majority illusion is easy. InProceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 13763–13770, 2025

work page 2025
[12]

Doucette, A

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

work page 2019
[13]

An algorithmic theory of integer programming.arXiv preprint arXiv:1904.01361, 2019

Friedrich Eisenbrand, Christoph Hunkenschröder, Kim-Manuel Klein, Martin Kouteck`y, Asaf Levin, and Shmuel Onn. An algorithmic theory of integer programming.arXiv preprint arXiv:1904.01361, 2019

work page arXiv 1904
[14]

Opinion diffusion and cam- paigning on society graphs.Journal of Logic and Computation, 32(6):1162–1194, 2022

Piotr Faliszewski, Rica Gonen, Martin Kouteck `y, and Nimrod Talmon. Opinion diffusion and cam- paigning on society graphs.Journal of Logic and Computation, 32(6):1162–1194, 2022

work page 2022
[15]

Why your friends have more friends than you do.American Journal of Sociology, 96(6):1464–1477, 1991

Scott L Feld. Why your friends have more friends than you do.American Journal of Sociology, 96(6):1464–1477, 1991

work page 1991
[16]

Twitter spam and false accounts prevalence, detection and characterization: A survey

Emilio Ferrara. Twitter spam and false accounts prevalence, detection and characterization: A survey. arXiv preprint arXiv:2211.05913, 2022

work page arXiv 2022
[17]

Herd immunity: a rough guide.Clinical infectious diseases, 52(7):911–916, 2011

Paul Fine, Ken Eames, and David L Heymann. Herd immunity: a rough guide.Clinical infectious diseases, 52(7):911–916, 2011

work page 2011
[18]

Eliminating majority illusion

Foivos Fioravantes, Abhiruk Lahiri, Antonio Lauerbach, Lluís Sabater, Marie Diana Sieper, and Samuel Wolf. Eliminating majority illusion. InProceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, pages 749–757, 2025

work page 2025
[19]

The effect of social media on elections: Evidence from the united states.Journal of the European Economic Association, 22:1495—-1539, 2024

Thomas Fujiwara, Karsten Müller, and Carlo Schwarz. The effect of social media on elections: Evidence from the united states.Journal of the European Economic Association, 22:1495—-1539, 2024

work page 2024
[20]

Computers and intractability; a guide to the theory of np- completeness, 1990

Michael R Garey and David S Johnson. Computers and intractability; a guide to the theory of np- completeness, 1990

work page 1990
[21]

Identifying and eliminating majority illusion in social networks

Umberto Grandi, Lawqueen Kanesh, Grzegorz Lisowski, Ramanujan Sridharan, and Paolo Turrini. Identifying and eliminating majority illusion in social networks. InProceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 5062–5069, 2023. 22

work page 2023
[22]

An nˆ5/2 algorithm for maximum matchings in bipartite graphs

John E Hopcroft and Richard M Karp. An nˆ5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing, 2(4):225–231, 1973

work page 1973
[23]

On integer programming, discrepancy, and convolution.Mathematics of Operations Research, 48(3):1481–1495, 2023

Klaus Jansen and Lars Rohwedder. On integer programming, discrepancy, and convolution.Mathematics of Operations Research, 48(3):1481–1495, 2023

work page 2023
[24]

Johnson, N

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

work page 2020
[25]

Influential nodes in a diffusion model for social networks

David Kempe, Jon Kleinberg, and Éva Tardos. Influential nodes in a diffusion model for social networks. Ininternational colloquium on automata, languages, and programming, pages 1127–1138. Springer, 2005

work page 2005
[26]

Inducing equilibria in networked public goods games through network structure modification.arXiv preprint arXiv:2002.10627, 2020

David Kempe, Sixie Yu, and Yevgeniy V orobeychik. Inducing equilibria in networked public goods games through network structure modification.arXiv preprint arXiv:2002.10627, 2020

work page arXiv 2002
[27]

Majority colourings of digraphs.The Electronic Journal of Combinatorics, pages P2–25, 2017

Stephan Kreutzer, Sang-il Oum, Paul Seymour, Dominic van der Zypen, and David R Wood. Majority colourings of digraphs.The Electronic Journal of Combinatorics, pages P2–25, 2017

work page 2017
[28]

majority illusion

Kristina Lerman, Xiaoran Yan, and Xin-Zeng Wu. The" majority illusion" in social networks.PloS one, 11(2):e0147617, 2016

work page 2016
[29]

A faster parameterized algorithm for treedepth

Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar. A faster parameterized algorithm for treedepth. InInternational Colloquium on Automata, Languages, and Programming, pages 931–942. Springer, 2014

work page 2014
[30]

Majority illusion drives the spontaneous emergence of alternative states in common-pool resource games with network-based information

Nicolas Schrama, Andrew R Tilman, and Vítor V Vasconcelos. Majority illusion drives the spontaneous emergence of alternative states in common-pool resource games with network-based information. iScience, 2025

work page 2025
[31]

On the graph theory of majority illusions

Maaike Venema-Los, Zoé Christoff, and Davide Grossi. On the graph theory of majority illusions. In European Conference on Multi-Agent Systems, pages 17–31. Springer, 2023

work page 2023
[32]

Wilder and Y

B. Wilder and Y . V orobeychik. Controlling elections through social influence. InProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), page 265–273. International Foundation for Autonomous Agents and Multiagent Systems, 2018

work page 2018
[33]

Manipulating elections by changing voter perceptions

Junlin Wu, Andrew Estornell, Lecheng Kong, and Yevgeniy V orobeychik. Manipulating elections by changing voter perceptions. In31st International Joint Conference on Artificial Intelligence, IJCAI 2022, pages 557–563. International Joint Conferences on Artificial Intelligence, 2022

work page 2022
[34]

Zhou and Z

X. Zhou and Z. Zhang. Maximizing influence of leaders in social networks. InProceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 2400–2408, 2021. 23 A Appendix We have a PTASfor thep-DIFRproblem on planar graphs. A.1 A PTAS for Planar Graphs We use the classical layering technique introduced by [3] for designing approx...

work page 2021