Discriminantal subset convolution: Refining exterior-algebraic methods for parameterized algorithms

摘要

We give a simplified account of the recent algebraic methods obtained for the longest path problem of Brand, Dell and Husfeldt (STOC'18) and Brand (ESA'19). To this end, we introduce a new kind of subset convolution, discriminantal subset convolution, which we motivate as a distillate of exterior-algebraic operations. The algorithm in the new presentation achieves the almost competitive bound of 2.619k⋅poly(n), first achieved by Fomin et al. (2016) [8], for deterministically finding paths of length k, while it allows for the same running time for the k-internal out-branching problem, improving upon Brand (ESA'19) and reproducing the state-of-the-art of Brand and Pratt (ICALP'21).