Fine-Grained Dichotomies for the Tutte Plane and Boolean #CSP

Authors Cornelius Brand, Holger Dell, Marc Roth



PDF
Thumbnail PDF

File

LIPIcs.IPEC.2016.9.pdf
  • Filesize: 485 kB
  • 14 pages

Document Identifiers

Author Details

Cornelius Brand
Holger Dell
Marc Roth

Cite AsGet BibTex

Cornelius Brand, Holger Dell, and Marc Roth. Fine-Grained Dichotomies for the Tutte Plane and Boolean #CSP. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.IPEC.2016.9

Abstract

Jaeger, Vertigan, and Welsh (1990) proved a dichotomy for the complexity of evaluating the Tutte polynomial at fixed points: The evaluation is #P-hard almost everywhere, and the remaining points admit polynomial-time algorithms. Dell, Husfeldt, and Wahlén (2010) and Husfeldt and Taslaman (2010), in combination with the results of Curticapean (2015), extended the #P-hardness results to tight lower bounds under the counting exponential time hypothesis #ETH, with the exception of the line y=1, which was left open. We complete the dichotomy theorem for the Tutte polynomial under #ETH by proving that the number of all acyclic subgraphs of a given n-vertex graph cannot be determined in time exp(o(n)) unless #ETH fails. Another dichotomy theorem we strengthen is the one of Creignou and Hermann (1996) for counting the number of satisfying assignments to a constraint satisfaction problem instance over the Boolean domain. We prove that all #P-hard cases cannot be solved in time exp(o(n)) unless #ETH fails. The main ingredient is to prove that the number of independent sets in bipartite graphs with n vertices cannot be computed in time exp(o(n)) unless #ETH fails. In order to prove our results, we use the block interpolation idea by Curticapean (2015) and transfer it to systems of linear equations that might not directly correspond to interpolation.
Keywords
  • computational complexity
  • counting problems
  • Tutte polynomial
  • exponential time hypothesis
  • forests
  • independent sets

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Andreas Björklund. Counting perfect matchings as fast as Ryser. In Proceedings of the 23rd Symposium on Discrete Algorithms, SODA 2012, pages 914-921, 2012. URL: http://dx.doi.org/10.1137/1.9781611973099.73.
  2. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Computing the Tutte polynomial in vertex-exponential time. In Proceedings of the 47th annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, pages 677-686, 2008. URL: http://dx.doi.org/10.1109/FOCS.2008.40.
  3. Jin-Yi Cai and Xi Chen. Complexity of counting CSP with complex weights. In Proceedings of the 44th Symposium on Theory of Computing, STOC 2012, pages 909-920, 2012. URL: http://dx.doi.org/10.1137/100814585.
  4. Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Computational complexity of holant problems. SIAM Journal on Computing, 40(4):1101-1132, 2011. URL: http://dx.doi.org/10.1137/100814585.
  5. Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. A duality between clause width and clause density for SAT. In Proceedings of the 21st Annual IEEE Conference on Computational Complexity, CCC'06, pages 252-260, Washington, DC, USA, 2006. IEEE Computer Society. URL: http://dx.doi.org/10.1109/CCC.2006.6.
  6. Nadia Creignou and Miki Hermann. Complexity of generalized satisfiability counting problems. Information and Computation, 125(1):1-12, 1996. URL: http://dx.doi.org/10.1006/inco.1996.0016.
  7. Radu Curticapean. Block interpolation: A framework for tight exponential-time counting complexity. In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015, pages 380-392. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_31.
  8. Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlén. Exponential time complexity of the permanent and the Tutte polynomial. ACM Transactions on Algorithms, 10, 2014. URL: http://dx.doi.org/10.1145/2635812.
  9. Holger Dell, Thore Husfeldt, and Martin Wahlén. Exponential time complexity of the permanent and the Tutte polynomial. In Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP 2010, pages 426-437, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14165-2_37.
  10. Joanna Ellis-Monaghan and Iain Moffatt. CRC handbook on the Tutte polynomial and related topics. CRC press, in preparation. Google Scholar
  11. Geoffrey Grimmett and Colin McDiarmid, editors. Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh. Oxford Lecture Series in Mathematics and Its Applications (Book 34). Oxford University Press, 2007. Google Scholar
  12. Thore Husfeldt and Nina Taslaman. The exponential time complexity of computing the probability that a graph is connected. In Proceedings of the 5th International Symposium on Parameterized and Exact Computation, IPEC 2010, pages 192-203, 2010. URL: http://dx.doi.org/10.1007/978-3-642-17493-3_19.
  13. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. URL: http://dx.doi.org/10.1006/jcss.2000.1727.
  14. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. URL: http://dx.doi.org/10.1006/jcss.2001.1774.
  15. François Jaeger, Dirk L. Vertigan, and Dominic J. A. Welsh. On the computational complexity of the Jones and Tutte polynomials. Mathematical proceedings of the Cambridge Philosophical Society, 108(1):35-53, 1990. URL: http://dx.doi.org/10.1017/S0305004100068936.
  16. J. Scott Provan and Michael O Ball. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM Journal on Computing, 12(4):777-788, 1983. URL: http://dx.doi.org/10.1137/0212053.
  17. Alan D. Sokal. The multivariate Tutte polynomial (alias Potts model) for graphs and matroids. In Surveys in Combinatorics, volume 327 of London Mathematical Society Lecture Note Series, pages 173-226, 2005. Google Scholar
  18. Nina Sofia Taslaman. Exponential-Time Algorithms and Complexity of NP-Hard Graph Problems. PhD thesis, IT-Universitetet i København, 2013. Google Scholar
  19. Seinosuke Toda. PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 20(5):865-877, 1991. URL: http://dx.doi.org/10.1137/0220053.
  20. Leslie G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2):189-201, 1979. URL: http://dx.doi.org/10.1016/0304-3975(79)90044-6.
  21. Dirk Llewellyn Vertigan. On the computational complexity of Tutte, Jones, Homfly and Kauffman invariants. PhD thesis, University of Oxford, 1991. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail