
























Given an undirected graph $G=(V,E)$ with edge capacities $c_e\geq 1$ for $e\in E$ and a subset $T$ of $k$ vertices called terminals, we say that a graph $H$ is a quality-$q$ cut sparsifier for $G$ iff $T\subseteq V(H)$, and for any partition $(A,B)$ of $T$, the values of the minimum cuts separating $A$ and $B$ in graphs $G$ and $H$ are within a factor $q$ from each other. We say that $H$ is a quality-$q$ flow sparsifier for $G$ iff $T\subseteq V(H)$, and for any set $D$ of demands over the terminals, the values of the minimum edge congestion incurred by fractionally routing the demands in $D$ in graphs $G$ and $H$ are within a factor $q$ from each other. So far vertex sparsifiers have been studied in a restricted setting where the sparsifier $H$ is not allowed to contain any non-terminal vertices, that is $V(H)=T$. For this setting, efficient algorithms are known for constructing quality-$O(\log k/\log\log k)$ cut and flow vertex sparsifiers, as well as a lower bound of $\tildeΩ(\sqrt{\log k})$ on the quality of any flow or cut sparsifier. We study flow and cut sparsifiers in the more general setting where Steiner vertices are allowed, that is, we no longer require that $V(H)=T$. We show algorithms to construct constant-quality cut sparsifiers of size $O(C^3)$ in time $\poly(n)\cdot 2^C$, and constant-quality flow sparsifiers of size $C^{O(\log\log C)}$ in time $n^{O(\log C)}\cdot 2^C$, where $C$ is the total capacity of the edges incident on the terminals.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。