Arnold Filtser: Clan Embeddings into Trees, and Low Treewidth Graphs
This event is free and open to the publicAdd to Google Calendar
A celebrated bypass to this problem is stochastic embedding with logarithmic expected distortion. Another bypass is Ramsey-type embedding, where the distortion guarantee applies only to a subset of the points. However, both these solutions fail to provide an embedding into a single tree with a worst-case distortion guarantee on all pairs.
We then focus on minor-free graphs of diameter parameterized by , which were known to be stochastically embeddable into bounded treewidth graphs with expected additive distortion . We devise Ramsey-type embedding and clan embedding analogs of the stochastic embedding. We use these embeddings to construct the first (bicriteria quasi-polynomial time) approximation scheme for the metric -dominating set and metric -independent set problems in minor-free graphs.