Document Open Access Logo

The HOMFLY-PT Polynomial is Fixed-Parameter Tractable

Author Benjamin A. Burton

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.18.pdf
  • Filesize: 1 MB
  • 14 pages

Document Identifiers

Author Details

Benjamin A. Burton

Cite As Get BibTex

Benjamin A. Burton. The HOMFLY-PT Polynomial is Fixed-Parameter Tractable. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.18

Abstract

Many polynomial invariants of knots and links, including the Jones and HOMFLY-PT polynomials, are widely used in practice but #P-hard to compute. It was shown by Makowsky in 2001 that computing the Jones polynomial is fixed-parameter tractable in the treewidth of the link diagram, but the parameterised complexity of the more powerful HOMFLY-PT polynomial remained an open problem. Here we show that computing HOMFLY-PT is fixed-parameter tractable in the treewidth, and we give the first sub-exponential time algorithm to compute it for arbitrary links.

Subject Classification

Keywords
  • Knot theory
  • knot invariants
  • parameterised complexity

Metrics

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

References

  1. Benjamin A. Burton. Introducing Regina, the 3-manifold topology software. Experiment. Math., 13(3):267-272, 2004. Google Scholar
  2. Benjamin A. Burton, Ryan Budney, William Pettersson, et al. Regina: Software for low-dimensional topology. http://regina-normal.github.io/, 1999-2018. Google Scholar
  3. Federico Comoglio and Maurizio Rinaldi. A topological framework for the computation of the HOMFLY polynomial and its application to proteins. PLoS ONE, 6(4):e18693, 2011. Google Scholar
  4. Bruno Courcelle. On context-free sets of graphs and their monadic second-order theory. In Graph-Grammars and their Application to Computer Science (Warrenton, VA, 1986), volume 291 of Lecture Notes in Comput. Sci., pages 133-146. Springer, Berlin, 1987. Google Scholar
  5. Bruno Courcelle. Graph rewriting: An algebraic and logic approach. In Handbook of Theoretical Computer Science, Vol. B, pages 193-242. Elsevier, Amsterdam, 1990. Google Scholar
  6. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, Cham, 2015. Google Scholar
  7. P. Freyd, D. Yetter, J. Hoste, W. B. R. Lickorish, K. Millett, and A. Ocneanu. A new polynomial invariant of knots and links. Bull. Amer. Math. Soc. (N.S.), 12(2):239-246, 1985. Google Scholar
  8. F. Jaeger, D. L. Vertigan, and D. J. A. Welsh. On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Cambridge Philos. Soc., 108(1):35-53, 1990. Google Scholar
  9. Robert J. Jenkins, Jr. A Dynamic Programming Approach to Calculating the HOMFLY Polynomial for Directed Knots and Links. Master’s thesis, 1989. Google Scholar
  10. Vaughan F. R. Jones. A polynomial invariant for knots via von Neumann algebras. Bull. Amer. Math. Soc. (N.S.), 12(1):103-111, 1985. Google Scholar
  11. Louis H. Kauffman. State models for link polynomials. Enseign. Math. (2), 36(1-2):1-37, 1990. Google Scholar
  12. Ton Kloks. Treewidth: Computations and Approximations, volume 842 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 1994. Google Scholar
  13. W. B. Raymond Lickorish. An Introduction to Knot Theory. Number 175 in Graduate Texts in Mathematics. Springer, New York, 1997. Google Scholar
  14. Richard J. Lipton and Robert Endre Tarjan. A separator theorem for planar graphs. SIAM J. Appl. Math., 36(2):177-189, 1979. Google Scholar
  15. J. A. Makowsky. Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width. Discrete Appl. Math., 145(2):276-290, 2005. Google Scholar
  16. J. A. Makowsky and J. P. Mariño. The parameterized complexity of knot polynomials. J. Comput. Syst. Sci., 67(4):742-756, 2003. Google Scholar
  17. H. R. Morton and H. B. Short. Calculating the 2-variable polynomial for knots presented as closed braids. J. Algorithms, 11(1):117-131, 1990. Google Scholar
  18. Masahiko Murakami, Fumio Takeshita, and Seiichi Tani. Computing HOMFLY polynomials of 2-bridge links from 4-plat representation. Discrete Appl. Math., 162:271-284, 2014. Google Scholar
  19. Józef H. Przytycki. The first coefficient of Homflypt and Kauffman polynomials: Vertigan proof of polynomial complexity using dynamic programming. Preprint, arXiv:\allowbreak 1707.07733, 2017. Google Scholar
  20. Józef H. Przytycki and Paweł Traczyk. Invariants of links of Conway type. Kobe J. Math., 4(2):115-139, 1988. Google Scholar
  21. L. Traldi. On the colored Tutte polynomial of a graph of bounded tree-width. Discrete Applied Mathematics, 154.6:1032-1036, 2006. Google Scholar
  22. D. J. A. Welsh. Complexity: Knots, Colourings and Counting, volume 186 of London Math. Soc. Lecture Note Ser. Cambridge Univ. Press, Cambridge, 1993. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact