Collective-Influence-Guided Feedback-Vertex-Set Selection for network dismantling
MSc Thesis Defense by: Aryaman Ahluwalia
Date: Wednesday, August 19, 2026
Time: 10:00 AM 11:00 AM
Location: Essex Hall 122
Abstract:
Network dismantling asks for the smallest set of nodes whose removal leaves no connected component larger than a chosen threshold. It is NP-hard, so practical work relies on heuristics, whose reported margins over one another are small enough that attribution becomes the difficulty. This thesis proposes a two-phase structural pipeline. Phase 1 decycles the 2-core by depth-first search back-edge detection: each back edge certifies exactly one cycle, and one vertex of that cycle is removed, selected by its radius-one Collective Influence. Phase 2 fragments the resulting forest by greedy Collective Influence removal. Phase 1 is shown to return a valid feedback vertex set in O(|F|(n+m)) time. A first realisation, making no selection among a cycle’s vertices, inflates that set to roughly 70% of the network against about 21% inclusion-minimal, and is reported as a negative result. Both approaches are evaluated against Random removal, CoreHD, Collective In-fluence and WEAK-NEIGHBOR, on Erdos–Rényi and configuration-model graphs and on two real contact networks. The proposed strategies are competitive with the established heuristics but do not beat them: the best variant is level with WEAK-NEIGHBOR at 0.191 on Erdos–Rényi graphs and ahead of CoreHD’s 0.193, a margin of 0.2 percentage points lying well inside instance-to-instance spread. Competitive performance is confined to sparse graphs. Controls explore what that comparison reports. Every strategy hands off to the same greedy fill once the graph becomes acyclic, and that shared tail is 84 to 86% of each synthetic sequence; with the second phase held fixed and optimal, 86 to 90% of the total is the feedback vertex set itself. A cycle-rank bound forces a constant fraction of the network once the average degree reaches four. The contribution is empirical and explanatory.
Keywords: Network dismantling, Feedback vertex set, Collective Influence, 2-core decycling, Graph heuristics, Network Robustness
Thesis Committee:
Internal Reader: Dr. Ikjot Saini
External Reader: Dr. Tirupati Bolisetti
Advisor: Dr. Asish Mukhopadhyay
Chair: Dr. Shaon Bhatta Shuvo