  The largest eigenvalue of the adjacency matrix of a network (referred to as
the spectral radius) is an important metric in its own right. Further, for
several models of epidemic spread on networks (e.g., the `flu-like' SIS model),
it has been shown that an epidemic dies out quickly if the spectral radius of
the graph is below a certain threshold that depends on the model parameters.
This motivates a strategy to control epidemic spread by reducing the spectral
radius of the underlying network.
  In this paper, we develop a suite of provable approximation algorithms for
reducing the spectral radius by removing the minimum cost set of edges
(modeling quarantining) or nodes (modeling vaccinations), with different time
and quality tradeoffs. Our main algorithm, \textsc{GreedyWalk}, is based on the
idea of hitting closed walks of a given length, and gives an
$O(\log^2{n})$-approximation, where $n$ denotes the number of nodes; it also
performs much better in practice compared to all prior heuristics proposed for
this problem. We further present a novel sparsification method to improve its
running time.
  In addition, we give a new primal-dual based algorithm with an even better
approximation guarantee ($O(\log n)$), albeit with slower running time. We also
give lower bounds on the worst-case performance of some of the popular
heuristics. Finally we demonstrate the applicability of our algorithms and the
properties of our solutions via extensive experiments on multiple synthetic and
real networks.
