  Graph connectivity and network design problems are among the most fundamental
problems in combinatorial optimization. The minimum spanning tree problem, the
two edge-connected spanning subgraph problem (2-ECSS) and the tree augmentation
problem (TAP) are all examples of fundamental well-studied network design tasks
that postulate different initial states of the network and different
assumptions on the reliability of network components. In this paper we motivate
and study \emph{Flexible Graph Connectivity} (FGC), a problem that mixes
together both the modeling power and the complexities of all aforementioned
problems and more. In a nutshell, FGC asks to design a connected network, while
allowing to specify different reliability levels for individual edges. While
this non-uniform nature of the problem makes it appealing from the modeling
perspective, it also renders most existing algorithmic tools for dealing with
network design problems unfit for approximating FGC.
  In this paper we develop a general algorithmic approach for approximating FGC
that yields approximation algorithms with ratios that are very close to the
best known bounds for many special cases, such as 2-ECSS and TAP. Our algorithm
and analysis combine various techniques including a weight-scaling algorithm, a
charging argument that uses a variant of exchange bijections between spanning
trees and a factor revealing min-max-min optimization problem.
