Computer Science – Data Structures and Algorithms
Scientific paper
2012-04-12
Computer Science
Data Structures and Algorithms
Scientific paper
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{\Omega}(\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.
No associations
LandOfFree
On Vertex Sparsifiers with Steiner Nodes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Vertex Sparsifiers with Steiner Nodes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Vertex Sparsifiers with Steiner Nodes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-142892