Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor
Speaker:Reut Levi
coming from:Université Paris Diderot - Paris 7 and École Normale Supérieure, France.
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Monday, 9 March 2015
Duration:30 Minutes
Building:E1 4
Motivated by the problem of testing planarity and related properties, we study the problem of designing efficient {\em partition oracles\/}.

A {\em partition oracle\/} is a procedure that, given access to the incidence lists representation of a bounded-degree graph $G= (V,E)$ and a parameter $\eps$, when queried on a vertex $v\in V$, returns the part (subset of vertices) which $v$ belongs to in a partition of all graph vertices. The partition should be such that all parts are small, each part is connected, and if the graph has certain properties, the total number of edges between parts is at most $\eps |V|$.
In this work we give a partition oracle for graphs with excluded minors whose query complexity is quasi-polynomial in $1/\eps$, thus improving on the result of Hassidim et al. ({\em Proceedings of FOCS 2009}) who gave a partition oracle with query complexity exponential in $1/\eps$. This improvement implies corresponding improvements in the complexity of testing planarity and other properties that are characterized by excluded minors as well as sublinear-time approximation algorithms that work under the promise that the graph has an excluded minor.

Name(s):Christina Fries
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Created:Christina Fries/AG1/MPII/DE, 02/23/2015 12:02 PM Last modified:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Christina Fries, 02/26/2015 01:56 PM
  • Christina Fries, 02/23/2015 12:08 PM -- Created document.