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.