[DMO] Tomohiro Koana: Determinantal sieving

14 juni 2024 16:00 t/m 17:00 - Locatie: Lecture Hall G, 36.HB.00.230 | Zet in mijn agenda

"We introduce a new, remarkably powerful tool to the toolbox of algebraic FPT algorithms, determinantal sieving. Given a polynomial P(x_1,..,x_n) over a field F of characteristic 2, on a set of variables X={x_1,...,x_n}, and a linear matroid M=(X, I) over F of rank k, in 2^k evaluations of P we can sieve for those terms in the monomial expansion of P which are multilinear and whose support is a basis for M. The known tools of multilinear detection and constrained multilinear detection then correspond to the case where M is a uniform matroid and the truncation of a disjoint union of uniform matroids, respectively. More generally, let the odd support of a monomial m be the set of variables which have odd degree in m. Using 2^k evaluations of P, we can sieve for those terms m whose odd support spans M. Applying this framework to well-known efficiently computable polynomial families allows us to simplify, generalize and improve on a range of algebraic FPT algorithms, such as:
* Solving q-Matroid Intersection in time O*(2^{(q-2)k}) and q-Matroid Parity in time O*(2^{qk}), improving on O*(4^{qk}) for matroids represented over general fields (Brand and Pratt, ICALP 2021)
* T-Cycle, Colourful (s,t)-Path, Colourful (S,T)-Linkage in undirected graphs, and the more general Rank k (S,T)-Linkage problem over so-called frameworks (see Fomin et al., SODA 2023), all in O*(2^k) time, improving on O*(2^{k+|S|}) and O*(2^{|S|+O(k^2 log(k+|F|))}), respectively
* Many instances of the Diverse X paradigm, finding a collection of r solutions to a problem with a minimum mutual distance of d in time O*(2^{r^2 d/2}), improving solutions for k-Distinct Branchings from time 2^{O(k \log k)} to O*(2^k) (Bang-Jensen et al., ESA 2021), and for Diverse Perfect Matchings from O*(2^{2^{O(rd)}}) to O*(2^{r^2d/2}) (Fomin et al., STACS 2021)
For several other problems, such as Set Cover, Steiner Tree, Graph Motif and Subgraph Isomorphism, where the current algorithms are either believed to be optimal or are proving exceedingly difficult to improve, we show matroid-based generalisations at no increased cost to the running time. In the above, all matroids are assumed to be represented over fields of characteristic 2 and all algorithms use polynomial space. Over general fields, we achieve similar results at the cost of using exponential space by working over the exterior algebra. For a class of arithmetic circuits we call strongly monotone, this is even achieved without any loss of running time. However, the odd support sieving result appears to be specific to working over characteristic 2.
This is joint work with Eduard Eiben and Magnus Wahlström."