An approximation algorithm for the maximum spectral subgraph problem
Bazgan, Cristina; Beaujean, Paul; Gourdin, Eric (2022), An approximation algorithm for the maximum spectral subgraph problem, Journal of Combinatorial Optimization, 44, 3, p. 1880–1899. 10.1007/s10878-020-00552-w
Type
Article accepté pour publication ou publiéDate
2022Journal name
Journal of Combinatorial OptimizationVolume
44Number
3Publisher
Springer
Pages
1880–1899
Publication identifier
Metadata
Show full item recordAuthor(s)
Bazgan, CristinaLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Beaujean, Paul

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Orange Labs [Chatillon]
Gourdin, Eric
Orange Labs [Issy les Moulineaux]
Abstract (EN)
Modifying the topology of a network to mitigate the spread of an epidemic with epidemiological constant λ amounts to the NP-hard problem of finding a partial subgraph with maximum number of edges and spectral radius bounded above by λ. A software-defined network capable of real-time topology reconfiguration can then use an algorithm for finding such subgraph to quickly remove spreading malware threats without deploying specific security countermeasures. In this paper, we propose a novel randomized approximation algorithm based on the relaxation and rounding framework that achieves a O(logn) approximation in the case of finding a subgraph with spectral radius bounded by λ∈[logn,λ1(G)) where λ1(G) is the spectral radius of the input graph and n is the number of nodes. We combine this algorithm with a maximum matching algorithm to obtain a O(log2n)-approximation algorithm for all values of λ. We also describe how the mathematical programming formulation we give has several advantages over previous approaches which attempted at finding a subgraph with minimum spectral radius given an edge removal budget. Finally, we show that the analysis of our randomized rounding scheme is essentially tight by relating it to classical results from random graph theory.Subjects / Keywords
Approximation algorithm; Relaxation and rounding; Semidefiniteprogramming; Spectral graph theory; Random graphsRelated items
Showing items related by title and author.
-
Bazgan, Cristina; Beaujean, Paul; Gourdin, Eric (2018) Communication / Conférence
-
Bazgan, Cristina; Chlebíková, Janka; Dallard, Clément; Pontoizeau, Thomas (2019) Article accepté pour publication ou publié
-
Bazgan, Cristina; Monnot, Jérôme; Hassin, Refael (2005) Article accepté pour publication ou publié
-
Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2011) Communication / Conférence
-
Bourgeois, Nicolas; Giannakos, Aristotelis; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2017) Article accepté pour publication ou publié