Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, March 28, 2023, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Martin Fürer (Pennsylvania State University)
Most NP-hard graph problems can be solved efficiently when restricted to graphs of small width and provided with a corresponding tree decomposition. Thus, it is essential to find good tree decompositions efficiently. The goal is to approximate the width by a small constant factor and to have an efficient FPT (fixed parameter tractable) algorithm. FPT means that the time is O(f(k)g(n)) where k is the parameter (in this case the treewidth), n is the size of the input, f is a computable function and g is bounded by a polynomial. Korhonen’s  new algorithm achieves a ratio of 2 with g linear. However, f remains a stumbling block for fast algorithms. Tree Decomposition (of width at most k) is NP-complete. Therefore, f(k) = O*(ck), achieved by several algorithms, is theoretically satisfactory, but the base c is large. (O* omits polynomial factors.) This talk is about decreasing c. It starts with a quick review of the classical O*(43k) n2 algorithm of Robertson and Seymour  and the 2O(k log k) n log n improvement by Reed . Joint work with Mahdi Belbasi.
Automatic MiSe System Software Version 1.4803M | admin login