You (Almost) Can't Beat Brute Force for 3-Matroid Intersection

The $\ell$-matroid intersection ($\ell$-MI) problem asks if $\ell$ given matroids share a common basis. Already for $\ell = 3$, notable canonical NP-complete special cases are 3-Dimensional Matching and Hamiltonian Path on directed graphs. However, while these problems admit exponential-time algorithms that improve the simple brute force significantly (e.g., Eiben-Koana-Wahlström (SODA’24)), the fastest known algorithm for 3-MI on general matroids is exactly brute force with runtime $2^n/\mathrm{poly}(n)$, where $n$ is the number of elements. Our main result shows that, in fact, brute force cannot be significantly improved, by ruling out an algorithm for $\ell$-MI with runtime $o\left( 2^{\,n - 5 \cdot n^{\tfrac{1}{\ell-1}} \cdot \log(n)} \right)$, for any fixed $\ell \ge 3$. For $3$-MI, this gives a lower bound of $o\left( 2^{\,n - 5 \cdot \sqrt{n} \cdot \log(n)} \right)$. Our negative result raises the following natural questions: (i) Is there an algorithm for 3-MI with runtime strictly better than brute force? (ii) Can we separate the parameterized complexity of 3-MI from the important special case on linear matroids (parameterized by the rank of the matroids $k$)? In particular, can a lower bound match the existing $c^{k^2} \cdot \mathrm{poly}(n)$ algorithm of Huang-Ward (SIDMA’23) for general $\ell$-MI parameterized by the rank? We make progress towards obtaining affirmative answers to the above questions. In particular, we present (i) an algorithm which solves $\ell$-MI faster than brute force in time $2^{\,n - \Omega((\log^2 n))}$ for any $\ell \ge 3$, and (ii) a parameterized running time lower bound of $2^{(\ell-2)\cdot k \cdot \log k} \cdot \mathrm{poly}(n)$ for $\ell$-MI, for any $\ell \ge 3$. We obtain these results by generalizing the Monotone Local Search technique of Fomin-Gaspers-Lokshtanov-Saurabh (J. ACM’19). Broadly speaking, given a subset problem, our generalization transforms any algorithm parameterized by solution size, with runtime of the form $f(k) \cdot \mathrm{poly}(n)$, into an exponential-time algorithm with runtime depending on $f$. This implies that any $f(k) \cdot \mathrm{poly}(n)$ time parameterized algorithm for a subset problem yields a $2^{\,n - \omega(\log n)}$ time algorithm beating brute force, which may be of independent interest.