[DMO] Norbert Zeh: An FPT Algorithm for Scanwidth

27 oktober 2023 14:00 t/m 15:00 - Locatie: 08.150 Van Katwijkzaall | Zet in mijn agenda

We show that the scanwidth of a directed acyclic graph can be computed in O(f(k) * poly(n)) time, where k is the scanwidth. The scanwidth is yet another width measure of graphs, one that has been shown to be useful in phylogenetics; as an example, the tree containment problem can be solved efficiently when parameterized by the scanwidth of the network given as part of the input. Recently, Holtgrefe presented an O(n^f(k)) algorithm to compute the scanwidth of a DAG, leaving open the question whether there exists an algorithm with FPT running time (O(f(k) * poly(n))). Over the last two weeks, Holtgrefe, van Iersel, Jones, and I developed such an algorithm, borrowing ideas from similar algorithms for treewidth, pathwidth, and cutwidth. This talk reviews what scanwidth is and describes our algorithm.