N&O Seminar: Daniel Vaz (Max-Planck-Institut für Informatik)
- https://www.cwi.nl/research/groups/networks-and-optimization/events/n-o-seminar-daniel-vaz-max-planck-institut-fur-informatik
- N&O Seminar: Daniel Vaz (Max-Planck-Institut für Informatik)
- 2019-02-27T14:00:00+01:00
- 2019-02-27T15:00:00+01:00
- A New Reduction-To-Tree Technique for Graph Connectivity Problems
- What Networks & Optimization English
- When 27-02-2019 from 14:00 to 15:00 (Europe/Amsterdam / UTC100)
- Where L016
- Contact Name Daniel Dadush
-
Add event to calendar
iCal
Title: A New Reduction-To-Tree Technique for Graph Connectivity Problems
Tree Embedding is a ubiquitous concept in algorithms design that allows one to turn a graph optimization problem into the same problem on tree instances. The use of such a general technique has a downside: a loss of a O(log n) factor in the approximation ratio, which is unavoidable even on special graph classes, such as bounded-treewidth graphs, expanders, and grids.
In our work, we show a new "reduction-to-tree" technique that reduces a "graph connectivity/cut problem" to a (potentially bigger) instance of a Constraint Satisfaction Problem, related to the original problem. Using this technique, we can solve the problem with the same approximation ratio as on tree instances of the problem, with running time depending on the treewidth. We apply this technique to break the O(log n) tree embedding barrier for some group Steiner problems on bounded-treewidth graphs.
Joint work with Parinya Chalermsook, Syamantak Das, Guy Even, and Bundit Laekhanukit.