Computer Science – Discrete Mathematics
Scientific paper
2009-12-08
Computer Science
Discrete Mathematics
Scientific paper
We consider a variation of the spectral sparsification problem where we are required to keep a subgraph of the original graph. Formally, given a union of two weighted graphs $G$ and $W$ and an integer $k$, we are asked to find a $k$-edge weighted graph $W_k$ such that $G+W_k$ is a good spectral sparsifer of $G+W$. We will refer to this problem as the subgraph (spectral) sparsification. We present a nontrivial condition on $G$ and $W$ such that a good sparsifier exists and give a polynomial time algorithm to find the sparsifer. %$O(\frac{n}{k})\log n \tilde{O}(\log \log n)$ As a significant application of our technique, we show that for each positive integer $k$, every $n$-vertex weighted graph has an $(n-1+k)$-edge spectral sparsifier with relative condition number at most $\frac{n}{k} \log n \tilde{O}(\log\log n)$ where $\tilde{O}()$ hides lower order terms. Our bound is within a factor of $\tilde{O}(\log \log n)$ from optimal. This nearly settles a question left open by Spielman and Teng about ultrasparsifiers, which is a key component in their nearly linear-time algorithms for solving diagonally dominant symmetric linear systems. We also present another application of our technique to spectral optimization in which the goal is to maximize the algebraic connectivity of a graph (e.g. turn it into an expander) with a limited number of edges.
Kolla Alexandra
Makarychev Yury
Saberi Amin
Teng Shanghua
No associations
LandOfFree
Subgraph Sparsification and Nearly Optimal Ultrasparsifiers 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 Subgraph Sparsification and Nearly Optimal Ultrasparsifiers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Subgraph Sparsification and Nearly Optimal Ultrasparsifiers will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-275175