TechTalks from event: IEEE FOCS 2010

51st Annual IEEE Symposium on Foundations of Computer Science

  • A separator theorem in minor-closed classes Authors: Ken-ichi Kawarabayashi and Bruce Reed
    It is shown that for each $t$, there is a separator of size $O(t sqrt{n})$ in any $n$-vertex graph $G$ with no $K_t$-minor.

    This settles a conjecture of Alon, Seymour and Thomas (J. Amer. Math. Soc., 1990 and STOC'90), and generalizes a result of Djidjev (1981), and Gilbert, Hutchinson and Tarjan (J. Algorithm, 1984), independently, who proved that every graph with $n$ vertices and genus $g$ has a separator of order $O(sqrt{gn})$, because $K_t$ has genus $Omega(t^2)$.

    The bound $O(t sqrt{n})$ is best possible because every 3-regular expander graph with $n$ vertices is a graph with no $K_t$-minor for $t=cn^{1/2}$, and with no separator of size $dn$ for appropriately chosen positive constants $c,d$.

    In addition, we give an $O(n^2)$ time algorithm to obtain such a separator, and then give a sketch how to obtain such a separator in $O(n^{1+epsilon})$ time for any $epsilon > 0$. Finally, we discuss several algorithm aspects of our separator theorem, including a possibility to obtain a separator of order $g(t)sqrt{n}$, for some function $g$ of $t$, in an $n$-vertex graph $G$ with no $K_t$-minor in $O(n)$ time.

  • Optimal stochastic planarization Authors: Anastasios Sidiropoulos
    It has been shown by Indyk and Sidiropoulos [IS07] that any graph of genus g>0 can be stochastically embedded into a distribution over planar graphs with distortion 2^O(g). This bound was later improved to O(g^2) by Borradaile, Lee and Sidiropoulos [BLS09]. We give an embedding with distortion O(log g), which is asymptotically optimal.

    Apart from the improved distortion, another advantage of our embedding is that it can be computed in polynomial time. In contrast, the algorithm of [BLS09] requires solving an NP-hard problem.

    Our result implies in particular a reduction for a large class of geometric optimization problems from instances on genus-g graphs, to corresponding ones on planar graphs, with a O(log g) loss factor in the approximation guarantee.

  • Solving linear systems through nested dissection Authors: Noga Alon and Raphael Yuster
    The generalized nested dissection method, developed by Lipton, Rose, and Tarjan, is a seminal method for solving a linear system $Ax=b$ where $A$ is a symmetric positive definite matrix. The method runs extremely fast whenever $A$ is a well-separable matrix (such as matrices whose underlying support is planar or avoids a fixed minor). In this work we extend the nested dissection method to apply to {em any} non-singular well-separable matrix over {em any} field. The running times we obtain essentially match those of the nested dissection method.
  • Approaching optimality for solving SDD linear systems Authors: Iannis Koutis and Gary L. Miller and Richard Peng
    We present an algorithm that on input a graph $G$ with $n$ vertices and $m+n-1$ edges and a value $k$, produces an {em incremental sparsifier} $hat{G}$ with $n-1 + m/k$ edges, such that the condition number of $G$ with $hat{G}$ is bounded above by $ ilde{O}(klog^2 n)$, with probability $1-p$. The algorithm runs in time

    $$ ilde{O}((m log{n} + nlog^2{n})log(1/p)).$$

    As a result, we obtain an algorithm that on input an $n imes n$ symmetric diagonally dominant matrix $A$ with $m+n-1$ non-zero entries and a vector $b$, computes a vector $ar{x}$ satisfying $||x-A^{+}b||_A<epsilon ||A^{+}b||_A $, in time

    $$ ilde{O}(mlog^2{n}log(1/epsilon)).$$

    The solver is based on a recursive application of the incremental sparsifier that produces a hierarchy of graphs which is then used to construct a recursive preconditioned Chebyshev iteration.

  • Fast approximation algorithms for cut-based graph problems Authors: Aleksander Madry
    We present a general method of designing fast approximation algorithms for cut-based minimization problems in undirected graphs. In particular, we develop a technique that given any such problem that can be approximated quickly on trees, allows approximating it almost as quickly on general graphs while only losing a poly-logarithmic factor in the approximation guarantee. We present a general method of designing fast approximation algorithms for undirected cut-based minimization problems. More precisely, we develop a technique that given any such cut-based problem that can be approximated quickly on trees, allows approximating it almost as quickly on general graphs while only losing a poly-logarithmic factor in the approximation guarantee.

    To illustrate the applicability of our paradigm, we focus our attention on the undirected sparsest cut problem with general demands, and the balanced separator problem. By a simple use of our framework, we obtain poly-logarithmic approximation algorithms for these problems that run in time close to linear. This establishes, in particular, the first poly-logarithmic-approximation algorithm for the generalized sparsest cut problem whose running time breaks the multicommodity flow barrier of $Omega(n^2)$ time, and the first algorithms achieving such approximation ratio for the balanced separator and the (uniform) sparsest cut problem while running in time $o(m+n^{3/2})$.

    The main tool behind our result is an efficient procedure that decomposes general graphs into simpler ones while approximately preserving the cut-flow structure. This decomposition is inspired by hierarchical tree decompositions that were developed in the context of oblivious routing schemes.

  • Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability Authors: Konstantin Makarychev and Yury Makarychev
    We study vertex cut and flow sparsifiers that were recently introduced by Moitra (2009), and Leighton and Moitra (2010). Our results improve and generalize the results by Moitra (2009), and Leighton and Moitra (2010). We give a new polynomial-time algorithm for constructing O(log k / log log k) cut and flow sparsifiers, matching the best existential upper bound on the quality of a sparsifier, and improving the previous algorithmic upper bound of O(log^2 k / log log k). We show that flow sparsifiers can be obtained from linear operators approximating minimum metric extensions. We introduce the notion of (linear) metric extension operators, prove that they exist, and give an exact polynomial-time algorithm for finding optimal operators.

    We then establish a direct connection between flow and cut sparsifiers and Lipschitz extendability of maps in Banach spaces, a notion studied in functional analysis since 1950s. Using this connection, we prove a lower bound of Omega(sqrt{log k /log log k}) for flow sparsifiers and a super-constant lower bound for cut sparsifiers. We show that if a certain open question posed by Ball in 1992 has a positive answer, then there exist ilde O(sqrt{log k}) cut sparsifiers. On the other hand, any lower bound on cut sparsifiers better than ilde Omega(sqrt{log k}) would imply a negative answer to this question.

  • Vertex Sparsifiers and Abstract Rounding Algorithms Authors: Moses Charikar and Tom Leighton and Shi Li and Ankur Moitra
    The notion of vertex sparsification (in particular cut-sparsification) is introduced in (M, 2009), where it was shown that for any graph $G = (V, E)$ and a subset of $k$ terminals $K subset V$, there is a polynomial time algorithm to construct a graph $H = (K, E_H)$ emph{on just the terminal set} so that simultaneously for all cuts $(A, K-A)$, the value of the minimum cut in $G$ separating $A$ from $K -A$ is approximately the same as the value of the corresponding cut in $H$. Then approximation algorithms can be run directly on $H$ as a proxy for running on $G$, yielding approximation guarantees independent of the size of the graph. In this work, we consider how well cuts in the sparsifier $H$ can approximate the minimum cuts in $G$, and whether algorithms that use such reductions need to incur a multiplicative penalty in the approximation guarantee depending on the quality of the sparsifier.

    We give the first super-constant lower bounds for how well a cut-sparsifier $H$ can simultaneously approximate all minimum cuts in $G$. We prove a lower bound of $Omega(log^{1/4} k)$ -- this is polynomially-related to the known upper bound of $O(log k/log log k)$. This is an exponential improvement on the $Omega(log log k)$ bound given in (LM, 2010) which in fact was for a stronger vertex sparsification guarantee, and did not apply to cut sparsifiers.

    Despite this negative result, we show that for many natural problems, we do not need to incur a multiplicative penalty for our reduction. Roughly, we show that any rounding algorithm which also works for the $0$-extension relaxation can be used to construct good vertex-sparsifiers for which the optimization problem is easy. Using this, we obtain optimal $O(log k)$-competitive Steiner oblivious routing schemes, which generalize the results in cite{R}. We also demonstrate that for a wide range of graph packing problems (which includes maximum concurrent flow, maximum multiflow and multicast routing, among others, as a special case), the integr

  • A non-linear lower bound for planar epsilon-nets Authors: Noga Alon
    We show that the minimum possible size of an $epsilon$-net for point objects and line (or rectangle)-ranges in the plane is (slightly) bigger than linear in $1/epsilon$. This settles a problem raised by Matousek, Seidel and Welzl in 1990.
  • The sub-exponential upper bound for on-line chain partitioning Authors: Bartomiej Bosek and Tomasz Krawczyk
    he main question in the on-line chain partitioning problem is to determine whether there exists an algorithm that partitions on-line posets of width at most $w$ into polynomial number of chains -- see Trotter's chapter emph{Partially ordered sets} in the emph{Handbook of Combinatorics}. So far the best known on-line algorithm of Kierstead used at most $(5^w-1)/4$ chains; on the other hand Szemer'{e}di proved that any on-line algorithm requires at least $inom{w+1}{2}$ chains. These results were obtained in the early eighties and since then no progress in the general case has been done.

    We provide an on-line algorithm that partitions orders of width $w$ into at most $w^{16log{w}}$ chains. This yields the first sub-exponential upper bound for on-line chain partitioning problem.

  • Improved Bounds for Geometric Permutations Authors: Natan Rubin and Haim Kaplan and Micha Sharir
    We show that the number of geometric permutations of an arbitrary collection of $n$ pairwise disjoint convex sets in $ eals^d$, for $dgeq 3$, is $O(n^{2d-3}log n)$, improving Wenger's 20 years old bound of $O(n^{2d-2})$.