Arnaud de Mesmay (lab. IGM, Univ. G. Eiffel, Marne la Vallée)

In this talk, we will investigate two cutting problems for graphs embedded on surfaces. The first one is the Multiway cut problem: given a set of terminals, find the smallest set of edges whose removal disconnects all the terminals. The second one is the Shortest Cut Graph problem: find the shortest subgraph whose removal cuts the surface into a topological disk. Despite their apparent differences, we will see that these two problems can be handled using very similar tools, for establishing upper bounds as well as lower bounds.

For both problems, the best known exact algorithms are exponential and not fixed parameter tractable with respect to the genus nor the number of terminals. We justify this by showing lower bounds based on the Exponential Time Hypothesis which are tight up to a logarithmic factor, as well as \(W[1]\)-hardness. In order to circumvent this hardness, we explain how to obtain \((1+\epsilon)\) - approximation algorithms for both problems which run in time \(O(n \log n)\), where the \(O()\) hides an FPT dependency on \(\epsilon\), the genus and the number of terminals.

Lower bounds for problems with graphs embedded in the plane typically involve grid-like structures. The main novel idea in order to prove the new lower bounds is to identify which structures instead of grids we should use to obtain almost tight lower bounds parameterized by the genus. For the algorithms, the main flavor is the use of topological tools, mixed with more standard techniques from approximation algorithms. This talk will try to convey the intuition as to why these tools are needed, without requiring any prior knowledge on topology or graphs embedded on surfaces.

This is based on joint works with Vincent Cohen-Addad, Éric Colin de Verdière and Dániel Marx.