FOCS 2011
TechTalks from event: FOCS 2011
We will be uploading the videos for FOCS 2011 during the week of Nov 28th 2011. If you find any discrepancy, please let us know by clicking on report error link on talk page. If you did not permit the video to be published and by mistake we have published your talk, please notify us immediately at support AT weyond.com
1A

MinMax Graph Partitioning and SmallSet ExpansionWe study graph partitioning problems from a minmax perspective, in which an input graph on $n$ vertices should be partitioned into $k$ parts, and the objective is to minimize the maximum number of edges leaving a single part. The two main versions we consider are where the $k$ parts need to be of equalsize, and where they must separate a set of $k$ given terminals. We consider a common generalization of these two problems, and design for it an $O(\sqrt{\log n\log k})$approximation algorithm. This improves over an $O(\log2 n)$ approximation for the second version due to Svitkina and Tardos \cite{ST04}, and roughly $O(k\log n)$ approximation for the first version that follows from other previous work. We also give an improved $O(1)$approximation algorithm for graphs that exclude any fixed minor. Along the way, we study the $\rho$Unbalanced Cut problem, whose goal is to find, in an input graph $G=(V,E)$, a set $S\subseteq V$ of size $S=\rho n$ that minimizes the number of edges leaving $S$. We provide a bicriteria approximation of $O(\sqrt{\log{n}\log{(1/\rho)}})$; when the input graph excludes a fixedminor we improve this guarantee to $O(1)$. Note that the special case $\rho = 1/2$ is the wellknown Minimum Bisection problem, and indeed our bounds generalize those of Arora, Rao and Vazirani \cite{ARV08} and of Klein, Plotkin, and Rao~\cite{KPR93}. Our algorithms work also for the closely related Small Set Expansion (SSE) problem, which asks for a set $S\subseteq V$ of size $0<S \leq \rho n$ with minimum edgeexpansion, and was suggested recently by Raghavendra and Steurer~\cite{RS10}. In fact, our algorithm handles more general, weighted, versions of both problems. Previously, an $O(\log n)$ true approximation for both $\rho$Unbalanced Cut and Small Set Expansion follows from R\"acke~\cite{Racke08}.

The Graph Minor Algorithm with Parity ConditionsWe generalize the seminal Graph Minor algorithm of Robertson and Seymour to the parity version. We give polynomial time algorithms for the following problems: \begin{enumerate} \item the parity $H$minor (Odd $K_k$minor) containment problem, and \item the disjoint paths problem with $k$ terminals and the parity condition for each path, \end{enumerate} as well as several other related problems. We present an $O(m \alpha(m,n) n)$ time algorithm for these problems for any fixed $k$, where $n,m$ are the number of vertices and the number of edges, respectively, and the function $\alpha(m,n)$ is the inverse of the Ackermann function (see Tarjan \cite{tarjan}). Note that the first problem includes the problem of testing whether or not a given graph contains $k$ disjoint odd cycles (which was recently solved in \cite{tony,oddstoc}), if $H$ consists of $k$ disjoint triangles. The algorithm for the second problem generalizes the Robertson Seymour algorithm for the $k$disjoint paths problem. As with the RobertsonSeymour algorithm for the $k$disjoint paths problem for any fixed $k$, in each iteration, we would like to either use the presence of a huge clique minor, or alternatively exploit the structure of graphs in which we cannot find such a minor. Here, however, we must take care of the parity of the paths and can only use an ``odd clique minor". This requires new techniques to describe the structure of the graph when we cannot find such a minor. We emphasize that our proof for the correctness of the above algorithms does not depend on the full power of the Graph Minor structure theorem \cite{RS16}. Although the original Graph Minor algorithm of Robertson and Seymour does depend on it and our proof does have similarities to their arguments, we can avoid the structure theorem by building on the shorter proof for the correctness of the graph minor algorithm in \cite{kw}. Consequently, we are able to avoid the much of the heavy machinery of the Graph Minor structure theory. Our proof is less than 50 pages.

Separator Theorems for MinorFree and Shallow MinorFree Graphs with ApplicationsAlon, Seymour, and Thomas generalized Lipton and Tarjan's planar separator theorem and showed that a $K_h$minor free graph with $n$ vertices has a separator of size at most $h^{3/2}\sqrt n$. They gave an algorithm that, given a graph $G$ with $m$ edges and $n$ vertices and given an integer $h\geq 1$, outputs in $O(\sqrt{hn}m)$ time such a separator or a $K_h$minor of $G$. Plotkin, Rao, and Smith gave an $O(hm\sqrt{n\log n})$ time algorithm to find a separator of size $O(h\sqrt{n\log n})$. Kawarabayashi and Reed improved the bound on the size of the separator to $h\sqrt n$ and gave an algorithm that finds such a separator in $O(n^{1 + \epsilon})$ time for any constant $\epsilon > 0$, assuming $h$ is constant. This algorithm has an extremely large dependency on $h$ in the running time (some power tower of $h$ whose height is itself a function of $h$), making it impractical even for small $h$. We are interested in a small polynomial time dependency on $h$ and we show how to find an $O(h\sqrt{n\log n})$size separator or report that $G$ has a $K_h$minor in $O(\poly(h)n^{5/4 + \epsilon})$ time for any constant $\epsilon > 0$. We also present the first $O(\poly(h)n)$ time algorithm to find a separator of size $O(n^c)$ for a constant $c < 1$. As corollaries of our results, we get improved algorithms for shortest paths and maximum matching. Furthermore, for integers $\ell$ and $h$, we give an $O(m + n^{2 + \epsilon}/\ell)$ time algorithm that either produces a $K_h$minor of depth $O(\ell\log n)$ or a separator of size at most $O(n/\ell + \ell h^2\log n)$. This improves the shallow minor algorithm of Plotkin, Rao, and Smith when $m = \Omega(n^{1 + \epsilon})$. We get a similar running time improvement for an approximation algorithm for the problem of finding a largest $K_h$minor in a given graph.

A constant factor approximation algorithm for unsplittable flow on pathsIn this paper, we present the first constantfactor approximation algorithm for the unsplittable flow problem on a path. This represents a large improvement over the previous best polynomial time approximation algorithm for this problem in its full generality, which was an $O(\log n)$approximation algorithm; it also answers an open question by Bansal et~al.[SODA'09]. The approximation ratio of our algorithm is $7+\epsilon$ for any $\epsilon>0$. In the unsplittable flow problem on a path, we are given a capacitated path $P$ and $n$ tasks, each task having a demand, a profit, and start and end vertices. The goal is to compute a maximum profit set of tasks such that the total demand of the selected tasks does not exceed the capacity of any edge on $P$. This is a wellstudied problem that occurs naturally in various settings, and therefore it has been studied under alternative names, such as resource allocation, bandwidth allocation, resource constrained scheduling and temporal knapsack. Poly nomial time constant factor approximation algorithms for the problem were previously known only under the nobottleneck assumption (in which the maximum task demand must be no greater than the minimum edge capacity). We introduce several novel algorithmic techniques, which might be of independent interest: a framework which reduces the problem to instances with a bounded range of capacities, and a new geometrically inspired dynamic program which solves a special case of the maximum weight independent set of rectangles problem to optimality. We also give the first proof that the problem is strongly NPhard; we show that this is true even if all edge capacities are equal and all demands are either 1, 2, or 3.