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
3A

MultipleSource MultipleSink Maximum Flow in Directed Planar Graphs in NearLinear TimeWe give an $O(n log^3 n)$ algorithm that, given an nnode directed planar graph with arc capacities, a set of source nodes, and a set of sink nodes, finds a maximum flow from the sources to the sinks. Previously, the fastest algorithms known for this problem were those for general graphs.

Minimum Weight Cycles and Triangles: Equivalences and AlgorithmsWe consider the fundamental algorithmic problem of finding a cycle of minimum weight in a weighted graph. In particular, we show that the minimum weight cycle problem in an undirected $n$node graph with edge weights in $\{1,\ldots,M\}$ or in a directed $n$node graph with edge weights in $\{M,\ldots , M\}$ and no negative cycles can be efficiently reduced to finding a minimum weight {\em triangle} in an $\Theta(n)$node \emph{undirected} graph with weights in $\{1,\ldots,O(M)\}$. Roughly speaking, our reductions imply the following surprising phenomenon: a minimum cycle with an arbitrary number of weighted edges can be ``encoded'' using only \emph{three} edges within roughly the same weight interval! This resolves a longstanding open problem posed in a seminal work by Itai and Rodeh [SIAM J. Computing 1978 and STOC'77] on minimum cycle in unweighted graphs. A direct consequence of our efficient reductions are $\tilde{O}(Mn^{\omega})\leq \tilde{O}(Mn^{2.376})$time algorithms using fast matrix multiplication (FMM) for finding a minimum weight cycle in both undirected graphs with integral weights from the interval $[1,M]$ and directed graphs with integral weights from the interval $[M,M]$. The latter seems to reveal a strong separation between the all pairs shortest paths (APSP) problem and the minimum weight cycle problem in directed graphs as the fastest known APSP algorithm has a running time of $O(M^{0.681}n^{2.575})$ by Zwick [J. ACM 2002]. In contrast, when only combinatorial algorithms are allowed (that is, without FMM) the only known solution to minimum weight cycle is by computing APSP. Interestingly, any separation between the two problems in this case would be an amazing breakthrough as by a recent paper by Vassilevska W. and Williams [FOCS'10], any $O(n^{3\eps})$time algorithm ($\eps>0$) for minimum weight cycle immediately implies a $O(n^{3\delta})$time algorithm ($\delta>0$) for APSP.

Graph Connectivities, Network Coding, and Expander GraphsIn this paper we present a new algebraic formulation to compute edge connectivities in a directed graph, using the ideas developed in network coding. This reduces the problem of computing edge connectivities to solving systems of linear equations, thus allowing us to use tools in linear algebra to design new algorithms. Using the algebraic formulation we obtain faster algorithms for computing single source edge connectivities and all pairs edge connectivities, in some settings the amortized time to compute the edge connectivity for one pair is sublinear. Through this connection, we have also found an interesting use of expanders and superconcentrators to design fast algorithms for some graph connectivity problems.

Maximum EdgeDisjoint Paths in Planar Graphs with Congestion 2We study the maximum edgedisjoint path problem (\medp) in planar graphs $G=(V,E)$. We are given a set of terminal pairs $s_it_i$, $i=1,2 \ldots , k$ and wish to find a maximum {\em routable} subset of demands. That is, a subset of demands that can be connected by edgedisjoint paths. It is wellknown that there is an integrality gap of $\Omega(\sqrt{n})$ for this problem even on a gridlike graph, and hence in planar graphs (Garg et al.). In contrast, Chekuri et al. show that for planar graphs, if {\sc LP} is the optimal solution to the natural LP relaxation for \medp, then there is a subset which is routable in $2G$ that is of size $\Omega(\textsc{opt} /O(\log n))$. Subsequently they showed that $\Omega(\textsc{opt})$ is possible with congestion $4$ (i.e., in $4G$) instead of $2$. We strengthen this latter result to show that a constant approximation is possible also with congestion $2$ (and this is tight via the integrality gap grid example). We use a basic framework from work by Chekuri et al. At the heart of their approach is a 2phase algorithm that selects an OkamuraSeymour instance. Each of their phases incurs a factor 2 congestion. It is possible to reduce one of the phases to have congestion 1. In order to achieve an overall congestion 2, however, the two phases must share capacity more carefully. For the Phase 1 problem, we extract a problem called {\em rooted clustering} that appears to be an interesting problem class in itself.

Online Nodeweighted Steiner Tree and Related ProblemsWe obtain the first online algorithms for the nodeweighted Steiner tree, Steiner forest and group Steiner tree problems that achieve a polylogarithmic competitive ratio. Our algorithm for the Steiner tree problem runs in polynomial time, while those for the other two problems take quasipolynomial time. Our algorithms can be viewed as online LP rounding algorithms in the framework of Buchbinder and Naor; however, while the {\em natural} LP formulation of these problems do lead to fractional algorithms with a polylogarithmic competitive ratio, we are unable to round these LPs online without losing a polynomial factor. Therefore, we design new LP formulations for these problems drawing on a combination of paradigms such as {\em spider decompositions}, {\em lowdepth Steiner trees}, {\em generalized group Steiner problems}, etc. and use the additional structure provided by these to round the more sophisticated LPs losing only a polylogarithmic factor in the competitive ratio. As further applications of our techniques, we also design polynomialtime online algorithms with polylogarithmic competitive ratios for two fundamental network design problems in edgeweighted graphs: the group Steiner forest problem (thereby resolving an open question raised by Chekuri {\em et al}) and the single source $\ell$vertex connectivity problem (which complements similar results for the corresponding edgeconnectivity problem due to Gupta {\em et al}).