Abstract:
Network dismantling is the problem of identifying a minimal set of vertices whose removal breaks a graph into connected components of bounded size. This work studies a dismantling strategy based on approximating the Feedback Vertex Set (FVS), which removes cycles and reduces the network to a forest. The remaining tree components are then further fragmented by iteratively removing tree centers to minimize the size of the largest connected component. The proposed approach combines approximation algorithms for the FVS problem with structural properties of trees to obtain an efficient dismantling sequence. Its performance is evaluated on synthetic and real-world networks and compared with existing dismantling heuristics.
Keywords: Network Dismantling, Feedback Vertex Set, Tree Centers, Graph Algorithms, Complex Networks.
Thesis Committee:
Internal Reader: Dr. Ikjot Saini
Internal Reader: Dr. Tirupati Bolisetti
Advisor: Dr. Asish Mukhopadhyay
Location: 122 Essex Hall