Part of the joint STOC/SoCG 2016 workshop day
Date:
June 18th, 2016
Location:
Hyatt Regency in Cambridge
Organizers:
Ken-ichi Kawarabayashi and
Anastasios Sidiropoulos
The workshop will focus on recent algorithmic advancements on problems on topologically restricted graphs, such as planar, surface-embedded, small treewidth, minor-free graphs, and graphs of small crossing number. The goal will be to emphasize developments that are of importance in the areas of fixed parameter tractability, approximation algorithms, topological graph theory, and metric embeddings. The program will attempt to highlight developments that are of importance in all of these areas, and emphasize technical connections between them.
Chandra Chekuri, University of Illinois at Urbana-Champaign (the talk by Chandra Chekuri has been cancelled)
Éric Colin de Verdière, École Normale Supérieure (Paris)
Petr Hliněný, Masaryk University
Philip Klein, Brown University
Robert Krauthgamer, Weizmann Institute of Science
Daniel Lokshtanov, University of Bergen
Amir Nayyeri, Oregon State University
Morning session
9:00am - 9:30am | Petr Hliněný, Masaryk University |
Title:
Toroidal Grid Minors, Embedding Stretch, and Crossing Number Abstract: We introduce a new embedding density parameter for graphs embedded on orientable surfaces, called the stretch, and approximately relate this parameter to the size of the largest possible (and nontrivial) toroidal grid which is a minor of the graph. The approximation bounds depend only on the genus and the maximum degree. We show how to efficiently compute the stretch of a given embedding and how the stretch relates to the (planar) crossing number of the embedded graph. This talk is based on joint work with S. Cabello, M. Chimani and G. Salazar. |
|
  | |
9:35am - 10:05am | Daniel Lokshtanov, University of Bergen |
Title:
Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering Abstract: We prove the following theorem. Given a planar graph $G$ and an integer $k$, it is possible in polynomial time to randomly sample a subset $A$ of vertices of $G$ with the following properties:
Based on a joint work with Fedor V. Fomin, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh |
|
  | |
10:10am - 10:40am | Amir Nayyeri, Oregon State University |
Title:
Minimum cuts on surface embedded graphs Abstract: The algorithmic problem of computing minimum cuts in graphs has been the focus of many studies in the past few decades. In planar graphs, nearly linear time algorithms has been discovered for computing an st-minimum cut, a global minimum cut, and the Gomory-Hu tree (that represents all minimum cuts). All these algorithms rely heavily on the fact that in planar graphs the dual of a cut is a cycle. Generalizing these algorithm has been challenging as this duality cease to exist in surfaces of positive genus. In this talk, I will describe algorithms for computing minimum cuts on genus g surfaces. The running time of all these algorithm are of the form $O(f(g)n\text{polylog} n)$. The key insight is computing short cycles in all homology classes and combining them to construct the dual of the minimum cut. I describe ideas for computing minimum homologous cycles and assembling them. I will explain methods from three different papers that are results of joint work with Glencora Borradaile, Jeff Erickson, David Eppstein, Kyle Fox, Christian Wulff-Nilsen. |
Afternoon session
3:30pm - 4:00pm | Éric Colin de Verdière, École Normale Supérieure (Paris) |
Title:
Multicuts in planar and bounded-genus graphs with bounded number of terminals Abstract: Given an undirected, edge-weighted graph $G$ together with pairs of vertices, called pairs of terminals, the minimum multicut problem asks for a minimum-weight set of edges such that, after deleting these edges, the two terminals of each pair belong to different connected components of the graph. Relying on topological techniques, we provide a polynomial-time algorithm for this problem in the case where $G$ is embedded on a fixed surface of genus $g$ (e.g., when $G$ is planar) and has a fixed number $t$ of terminals. The running time is a polynomial of degree $O\big(\sqrt{g^2+gt}\big)$ in the input size. In the planar case, our result corrects an error in an extended abstract by Bentz [Int. Workshop on Parameterized and Exact Computation, 109--119, 2012]. The minimum multicut problem is also a generalization of the multiway cut problem, a.k.a. multiterminal cut problem; even for this special case, no dedicated algorithm was known for graphs embedded on surfaces. |
|
  | |
4:05pm - 4:35pm | Robert Krauthgamer, Weizmann Institute of Science |
Title:
Cutting corners cheaply, or how to remove Steiner points Abstract: I will show how the Steiner Point Removal (SPR) problem can always be solved with polylogarithmic distortion, which answers a question posed by Chan, Xia, Konjevod, and Richa (2006). Specifically, for every edge-weighted graph $G=(V,E,w)$ and a subset of terminals $T\subset V$, there is a graph only on the terminals, denoted $G'=(T,E',w')$, which is a minor of $G$ and the shortest-path distance between any two terminals is approximately equal in $G'$ and in $G$, namely within factor $O(\log^5 |T|)$. Our existence proof is constructive and gives a randomized polynomial-time algorithm. Joint work with Lior Kamma and Huy L. Nguyen |
|
  | |
4:40pm - 5:20pm | Philip Klein, Brown University |
Title:
Approximation Schemes for Planar Graphs: A Survey of Methods Abstract: In addressing an NP-hard problem in combinatorial optimization, one way to cope is to use an approximation scheme, an algorithm that, for any given $\epsilon>0$, produces a solution whose value is within a $1+\epsilon$ factor of optimal. For many problems on graphs, obtaining such accurate approximations is NP-hard if the input is allowed to be any graph but is tractable if the input graph is required to be planar. Research on polynomial-time approximation schemes for optimization problems in planar graphs goes back to the pioneering work of Lipton and Tarjan (1977) and Baker (1983). Since then, however, the scope of problems amenable to approximation has broadened considerably. In this talk I will outline some of the approaches used, especially those that have led to recent results. |
|
  |