Flexible Graph Connectivity Approximating network design problems between 1-and 2-connectivity

• 成果类型: Article
• 署名作者: Adjiashvili, David; Hommelsheim, Felix; Muhlenthaler, Moritz
• 署名单位: Swiss Federal Institutes of Technology Domain; ETH Zurich; Dortmund University of Technology; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01664-9
• 发表日期: 2022
• 页码: 409-441
• 关键词: algorithms

摘要

We introduce and study the problem Flexible Graph Connectivity, which in contrast to many classical connectivity problems features a non-uniform failure model. We distinguish between safe and unsafe resources and postulate that failures can only occur among the unsafe resources. Given an undirected edge-weighted graph and a set of unsafe edges, the task is to find a minimum-cost subgraph that remains connected after removing at most k unsafe edges. We give constant-factor approximation algorithms for this problem for k = 1 as well as for unit costs and k >= 1. Our approximation guarantees are close to the known best bounds for special cases, such as the 2-edge-connected spanning subgraph problem and the tree augmentation problem. 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.