N&O Seminar: Daniel Vaz (Max-Planck-Institut für Informatik)

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.