An approximation algorithm for the maximum spectral subgraph problem

Cristina Bazgan (), Paul Beaujean () and Éric Gourdin ()
Additional contact information
Cristina Bazgan: Université Paris-Dauphine, Université PSL, CNRS, LAMSADE
Paul Beaujean: Université Paris-Dauphine, Université PSL, CNRS, LAMSADE
Éric Gourdin: Orange Labs

Journal of Combinatorial Optimization, 2022, vol. 44, issue 3, No 26, 1880-1899

Abstract: Abstract Modifying the topology of a network to mitigate the spread of an epidemic with epidemiological constant $$\lambda $$ λ amounts to the NP-hard problem of finding a partial subgraph with maximum number of edges and spectral radius bounded above by $$\lambda $$ λ . 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(\log n)$$ O ( log n ) approximation in the case of finding a subgraph with spectral radius bounded by $$\lambda \in [\log n, \lambda _1(G))$$ λ ∈ [ log n , λ 1 ( G ) ) where $$\lambda _1(G)$$ λ 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(\log ^2 n)$$ O ( log 2 n ) -approximation algorithm for all values of $$\lambda $$ λ . 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.

Keywords: Approximation algorithm; Relaxation and rounding; Semidefinite programming; Spectral graph theory; Random graphs (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00552-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:3:d:10.1007_s10878-020-00552-w

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00552-w

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().