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 convo...
详细信息
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 center dot 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). (c) 2022 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).
暂无评论