The Generalized Terminal Backup Problem

Attila Bernáth, Yusuke Kobayashi, Tatsuya Matsuoka


We consider the following network design problem, that we call the Generalized Terminal Backup Problem: given a graph (or a hypergraph) $G_0=(V, {E}_0)$, a set of (at least 2) terminals $T\subseteq V$ and a requirement $r(t)$ for every $t\in T$, find a multigraph $G=(V,E)$ such that $\lambda_{G_0+G}(t, T-t)\ge r(t)$ for any $t\in T$. In the minimum cost version the objective is to find $G$ minimizing the total cost $c(E)=\sum_{uv\in E}c(uv)$, given also costs $c(uv)\ge 0$ for every pair $u,v\in V$. In the degree-specified version the question is to decide whether such a $G$ exists, satisfying that the number of edges is a prescribed value $m(v)$ at each node $v\in V$. The Terminal Backup Problem solved in [1] is the special case where $G_0$ is the empty graph and $r(t)=1$ for every terminal $t\in T$. We solve the Generalized Terminal Backup Problem in the following two cases.

  1. In the first case we solve the degree-specified version by a splitting-off theorem. This splitting-off theorem in turn provides the solution for the minimum cost version in the case when $c$ is node-induced, that is $c(uv)=w(u)+w(v)$ for some node weights $w:V\to \Rset_+$.
  2. In the second solved case we turn to the general minimum cost version, and we are able to solve it when $G_0$ is the empty graph. This includes the \textbf{Terminal Backup Problem} [1] ($r\equiv 1$) and the \textbf{Maximum-Weight $b$-matching Problem} ($T=V$). The solution depends on an interesting new variant of a theorem of Lov\'asz and Cherkassky, and on the solution of the so-called Simplex Matching problem [1].
Our algorithms run in strongly polynomial time for both problems.

Previous version can be found here.

Bibtex entry:

AUTHOR = {Bern{\'a}th, Attila and Kobayashi, Yusuke and Matsuoka, Tatsuya},
TITLE = {The Generalized Terminal Backup Problem},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2013},
NUMBER = {TR-2013-07}

Last modification: 13.3.2018. Please email your comments to Tamás Király!