id: 05544685 dt: j an: 05544685 au: Ishii, Toshimasa ti: Minimum augmentation of edge-connectivity with monotone requirements in undirected graphs. so: Discrete Optim. 6, No. 1, 23-36 (2009). py: 2009 pu: Elsevier B. V., Amsterdam la: EN cc: ut: undirected graph; connectivity augmentation problem; monotone requirement; polynomial time deterministic algorithm ci: li: doi:10.1016/j.disopt.2008.08.002 ab: Summary: For a finite ground set $V$, we call a set-function $r:2^V\to\Bbb Z^+$ monotone, if $r(X’)\ge r(X)$ holds for each $X’\subseteq X\subseteq V$, where $\Bbb Z^+$ is the set of nonnegative integers. Given an undirected multigraph $G=(V,E)$ and a monotone requirement function $r:2^V\to\Bbb Z^+$, we consider the problem of augmenting $G$ by a smallest number of new edges, so that the resulting graph $G’$ satisfies $d_{G’}(X)\ge r(X)$ for each $\emptyset\ne X\subset V$, where $d_G(X)$ denotes the degree of a vertex set $X$ in $G$. This problem includes the edge-connectivity augmentation problem, and in general, it is NP-hard, even if a polynomial time oracle for $r$ is available. In this paper, we show that the problem can be solved in $O(n^4(m+n\log n+q))$ time, under the assumption that each $\emptyset\ne X\subset V$ satisfies $r(X)\ge2$ whenever $r(X)>0$, where $n=|V|$, $m=|\{\{u,v\}\mid (u,v)\in E\}|$, and $q$ is the time required to compute $r(X)$ for each $X\subseteq V$. rv: