Node-Connectivity Terminal Backup, Separately-Capacitated Multiflow, and Discrete Convexity

Abstract

The terminal backup problems (Anshelevich and Karagiozova (2011)) form a class of network design problems: Given an undirected graph with a requirement on terminals, the goal is to find a minimum cost subgraph satisfying the connectivity requirement. The node-connectivity terminal backup problem requires a terminal to connect other terminals with a number of node-disjoint paths. This problem is not known whether is NP-hard or tractable. Fukunaga (2016) gave a $4/3$-approximation algorithm based on LP-rounding scheme using a general LP-solver. In this paper, we develop a combinatorial algorithm for the relaxed LP to find a half-integral optimal solution in $O(m\log (nUA)\cdot \mathrm{MF}(kn,m+k^{2}n))$ time, where $n$ is the number of nodes, $m$ is the number of edges, $k$ is the number of terminals, $A$ is the maximum edge-cost, $U$ is the maximum edge-capacity, and $\mathrm{MF}(n^{\prime },m^{\prime })$ is the time complexity of a max-flow algorithm in a network with $n^{\prime }$ nodes and $m^{\prime }$ edges. The algorithm implies that the $4/3$-approximation algorithm for the node-connectivity terminal backup problem is also efficiently implemented. For the design of algorithm, we explore a connection between the node-connectivity terminal backup problem and a new type of a multiflow, called a separately-capacitated multiflow. We show a min-max theorem which extends Lovász-Cherkassky theorem to the node-capacity setting. Our results build on discrete convexity in the node-connectivity terminal backup problem.

arXiv commentA preliminary version of this paper was appeared in the proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP 2020)

References in corpus (2)

• A Cost-Scaling Algorithm for Minimum-Cost Node-Capacitated Multiflow Problem
• A cost-scaling algorithm for computing the degree of determinants