Abstract
We devise a framework for proving tight lower bounds under the counting exponential-time hypothesis #ETH introduced by Dell et al. (2014)
[18]. Our framework allows us to convert classical #P-hardness results for counting problems into tight lower bounds under #ETH, thus ruling out algorithms with running time 2o(n) graphs with n vertices and O(n) edges. As exemplary applications of this framework, we obtain tight lower bounds under #ETH for the evaluation of the zero-one permanent, the matching polynomial, and the Tutte polynomial on all non-easy points except for one line. This remaining line was settled very recently by Brand et al. (2016)
[18]. Our framework allows us to convert classical #P-hardness results for counting problems into tight lower bounds under #ETH, thus ruling out algorithms with running time 2o(n) graphs with n vertices and O(n) edges. As exemplary applications of this framework, we obtain tight lower bounds under #ETH for the evaluation of the zero-one permanent, the matching polynomial, and the Tutte polynomial on all non-easy points except for one line. This remaining line was settled very recently by Brand et al. (2016)
| Originalsprog | Engelsk |
|---|---|
| Tidsskrift | Information and Computation |
| Vol/bind | 261 |
| Sider (fra-til) | 265 |
| Antal sider | 280 |
| ISSN | 0890-5401 |
| DOI | |
| Status | Udgivet - aug. 2018 |
| Udgivet eksternt | Ja |
Emneord
- Tutte polynomial
- Independent set polynomial
- Matching polynomial
- Permanent
- Counting complexity
- Exponential-time hypothesis