Polynomial-Time Algorithms for Links

Abstract

Every link in the 3-sphere admits a generalised T-link presentation. In this paper, we give an explicit polynomial-time algorithm which, given a signed Artin braid word and the number of strands, computes such a presentation. Combining this construction with Yamada--Vogel braiding gives a polynomial-time conversion from arbitrary oriented combinatorial link diagrams to generalised T-link parameters. We prove polynomial bounds on the number of strands and crossings in the resulting braid. As an application, we prove that a link property or a link invariant is computable in polynomial time from diagrams if and only if the corresponding problem is solvable in polynomial time from generalised T-link parameters, with parameter input measured by the total number of strands and crossings in the corresponding braid diagram. Whenever a classification criterion or an explicit invariant formula is available in these parameters, it can be applied to the original link by substituting the parameters obtained from the diagram. A polynomial-time test or evaluation then gives a polynomial-time procedure on diagrams. We also establish the corresponding transfer for approximating real-valued invariants to prescribed accuracy.

Polynomial-time classical algorithms for mean-field models up to the glass transition
Alexander Schmidhuber, Alexander Zlokapa
arXiv5 Oct 2026PreprintarXiv licenceFull textMathematical physics Condensed matterarXiv
Improved polynomial-time algorithms for detecting and recovering planted Θ(√n)-cliques
Dmitriy Kunisky, Songtao Mao
arXiv21 Sep 2026PreprintarXiv licenceFull textStatisticsarXiv
The Links--Gould polynomial of an alternating link is alternating
Matthew Harper, Ben-Michael Kohli
arXiv13 Oct 2026PreprintCC BY 4.0Full textGeometry & topologyarXiv
The colored Jones polynomial does not determine the Links--Gould polynomial
Stavros Garoufalidis, Shana Yunsheng Li
arXiv5 Oct 2026PreprintarXiv licenceFull textGeometry & topologyarXiv
A note on the convergence guarantees of RLT-based algorithms for polynomial optimization
Alejandro Barros-González, Julio González-Díaz, Brais González-Rodríguez +1
arXiv5 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{paiva2026polynomialtime,
  title = {{Polynomial-Time Algorithms for Links}},
  author = {Thiago de Paiva and Yi Liu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.42077},
  eprint = {2610.42077},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.42077},
}

RIS

TY  - UNPB
TI  - Polynomial-Time Algorithms for Links
AU  - Thiago de Paiva
AU  - Yi Liu
PY  - 2026
DA  - 2026/10/30
PB  - arXiv
DO  - 10.48550/arxiv.2610.42077
UR  - https://arxiv.org/abs/2610.42077
AB  - Every link in the 3-sphere admits a generalised T-link presentation. In this paper, we give an explicit polynomial-time algorithm which, given a signed Artin braid word and the number of strands, computes such a presentation. Combining this construction with Yamada--Vogel braiding gives a polynomial-time conversion from arbitrary oriented combinatorial link diagrams to generalised T-link parameters. We prove polynomial bounds on the number of strands and crossings in the resulting braid. As an application, we prove that a link property or a link invariant is computable in polynomial time from diagrams if and only if the corresponding problem is solvable in polynomial time from generalised T-link parameters, with parameter input measured by the total number of strands and crossings in the corresponding braid diagram. Whenever a classification criterion or an explicit invariant formula is available in these parameters, it can be applied to the original link by substituting the parameters obtained from the diagram. A polynomial-time test or evaluation then gives a polynomial-time procedure on diagrams. We also establish the corresponding transfer for approximating real-valued invariants to prescribed accuracy.
ER  -

Abstract

Related

Cite