You (Almost) Can't Beat Brute Force for 3-Matroid Intersection
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915453435117568 |
|---|---|
| author | Doron-Arad, Ilan Kulik, Ariel Shachnai, Hadas |
| author_facet | Doron-Arad, Ilan Kulik, Ariel Shachnai, Hadas |
| contents | 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, the fastest known algorithm for $3$-MI is exactly brute force with runtime $2^{n}/poly(n)$, where $n$ is the number of elements. Our first 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^{\frac{1}{\ell-1}} \cdot \log (n)}\right)$, for any fixed $\ell\geq 3$. We further obtain: (i) an algorithm that solves $\ell$-MI faster than brute force in time $2^{n-Ω\left(\log^2 (n)\right)} $ (ii) a parameterized running time lower bound of $2^{(\ell-2) \cdot k \cdot \log k} \cdot poly(n)$ for $\ell$-MI, where the parameter $k$ is the rank of the matroids. We obtain these two results by generalizing the Monotone Local Search technique of Fomin et al. (J. ACM'19). Broadly speaking, our generalization converts any parameterized algorithm for a subset problem into an exponential-time algorithm which is faster than brute-force. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_02217 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | You (Almost) Can't Beat Brute Force for 3-Matroid Intersection Doron-Arad, Ilan Kulik, Ariel Shachnai, Hadas Data Structures and Algorithms 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, the fastest known algorithm for $3$-MI is exactly brute force with runtime $2^{n}/poly(n)$, where $n$ is the number of elements. Our first 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^{\frac{1}{\ell-1}} \cdot \log (n)}\right)$, for any fixed $\ell\geq 3$. We further obtain: (i) an algorithm that solves $\ell$-MI faster than brute force in time $2^{n-Ω\left(\log^2 (n)\right)} $ (ii) a parameterized running time lower bound of $2^{(\ell-2) \cdot k \cdot \log k} \cdot poly(n)$ for $\ell$-MI, where the parameter $k$ is the rank of the matroids. We obtain these two results by generalizing the Monotone Local Search technique of Fomin et al. (J. ACM'19). Broadly speaking, our generalization converts any parameterized algorithm for a subset problem into an exponential-time algorithm which is faster than brute-force. |
| title | You (Almost) Can't Beat Brute Force for 3-Matroid Intersection |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2412.02217 |