Subgraph Sparsification and Nearly Optimal Ultrasparsifiers

Details Subgraph Sparsification and Nearly Optimal Ultrasparsifiers Subgraph Sparsification and Nearly Optimal Ultrasparsifiers

2009-12-08

arxiv.org/abs/0912.1623v1

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.

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-275175