16 Search Results for "Spreer, Jonathan"

Document
DOI: 10.4230/LIPIcs.ESA.2025.37
Hardness of Computation of Quantum Invariants on 3-Manifolds with Restricted Topology

Authors: Henrique Ennes and Clément Maria

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Quantum invariants in low-dimensional topology offer a wide variety of valuable invariants about knots and 3-manifolds, presented by explicit formulas that are readily computable. Their computational complexity has been actively studied and is tightly connected to topological quantum computing. In this article, we prove that for any 3-manifold quantum invariant in the Reshetikhin-Turaev model, there is a deterministic polynomial time algorithm that, given as input an arbitrary closed 3-manifold M, outputs a closed 3-manifold M' with the same quantum invariant, such that M' is hyperbolic, contains no low genus embedded incompressible surface, and is presented by a strongly irreducible Heegaard diagram. Our construction relies on properties of Heegaard splittings and the Hempel distance. At the level of computational complexity, this proves that the hardness of computing a given quantum invariant of 3-manifolds is preserved even when severely restricting the topology and the combinatorics of the input. This positively answers a question raised by Samperton [Samperton, 2023].
Cite as

Henrique Ennes and Clément Maria. Hardness of Computation of Quantum Invariants on 3-Manifolds with Restricted Topology. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ennes_et_al:LIPIcs.ESA.2025.37,
  author =	{Ennes, Henrique and Maria, Cl\'{e}ment},
  title =	{{Hardness of Computation of Quantum Invariants on 3-Manifolds with Restricted Topology}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{37:1--37:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.37},
  URN =		{urn:nbn:de:0030-drops-245057},
  doi =		{10.4230/LIPIcs.ESA.2025.37},
  annote =	{Keywords: 3-manifold, Heegaard splitting, Hempel distance, Quantum invariant, polynomial time reduction}
}
Artifact
Software
DOI: 10.4230/artifacts.23286
AlexHe98/idealedge

Authors: Alexander He

Abstract
Cite as

Alexander He. AlexHe98/idealedge (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23286,
   title = {{AlexHe98/idealedge}}, 
   author = {He, Alexander},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:ebcbe72831246d6d99ed7ff98f3cc00940ed808c;origin=https://github.com/AlexHe98/idealedge;visit=swh:1:snp:0aecbae79b28d96e564539477e07d7c034f15e2a;anchor=swh:1:rev:9025c724d3c0c208f67a3b711a9342810c7d8909}{\texttt{swh:1:dir:ebcbe72831246d6d99ed7ff98f3cc00940ed808c}} (visited on 2025-06-20)},
   url = {https://github.com/AlexHe98/idealedge},
   doi = {10.4230/artifacts.23286},
}
Artifact
Software
DOI: 10.4230/artifacts.23281
raburke/Dim4Census

Authors: Rhuaidi Antonio Burke, Benjamin A. Burton, and Jonathan Spreer

Abstract
Cite as

Rhuaidi Antonio Burke, Benjamin A. Burton, Jonathan Spreer. raburke/Dim4Census (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23281,
   title = {{raburke/Dim4Census}}, 
   author = {Burke, Rhuaidi Antonio and Burton, Benjamin A. and Spreer, Jonathan},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:ee5ac0c76fdef9983c5de8a0be93f7684dd9a796;origin=https://github.com/raburke/Dim4Census;visit=swh:1:snp:a7fee9b4ed22b6bf281127e889c432095a216a58;anchor=swh:1:rev:54753c465209c14b34834a5f13cfe373b53ca4c6}{\texttt{swh:1:dir:ee5ac0c76fdef9983c5de8a0be93f7684dd9a796}} (visited on 2025-06-20)},
   url = {https://github.com/raburke/Dim4Census},
   doi = {10.4230/artifacts.23281},
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.55
A Practical Algorithm for Knot Factorisation

Authors: Alexander He, Eric Sedgwick, and Jonathan Spreer

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We present an algorithm for computing the prime factorisation of a knot, which is practical in the following sense: using Regina, we give an implementation that works well for inputs of reasonable size, including prime knots from the 19-crossing census. The main new ingredient in this work is an object that we call an "edge-ideal triangulation", which is what our algorithm uses to represent knots. As other applications, we give an alternative proof that prime knot recognition is in coNP, and present some new complexity results for triangulations. Beyond knots, our work showcases edge-ideal triangulations as a tool for potential applications in 3-manifold topology.
Cite as

Alexander He, Eric Sedgwick, and Jonathan Spreer. A Practical Algorithm for Knot Factorisation. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{he_et_al:LIPIcs.SoCG.2025.55,
  author =	{He, Alexander and Sedgwick, Eric and Spreer, Jonathan},
  title =	{{A Practical Algorithm for Knot Factorisation}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{55:1--55:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.55},
  URN =		{urn:nbn:de:0030-drops-232075},
  doi =		{10.4230/LIPIcs.SoCG.2025.55},
  annote =	{Keywords: Prime and composite knots, (crushing) normal surfaces, edge-ideal triangulations, co-NP certificate, triangulation complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.67
Hard Diagrams of Split Links

Authors: Corentin Lunel, Arnaud de Mesmay, and Jonathan Spreer

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Deformations of knots and links in ambient space can be studied combinatorially on their diagrams via local modifications called Reidemeister moves. While it is well-known that, in order to move between equivalent diagrams with Reidemeister moves, one sometimes needs to insert excess crossings, there are significant gaps between the best known lower and upper bounds on the required number of these added crossings. In this article, we study the problem of turning a diagram of a split link into a split diagram, and we show that there exist split links with diagrams requiring an arbitrarily large number of such additional crossings. More precisely, we provide a family of diagrams of split links, so that any sequence of Reidemeister moves transforming a diagram with c crossings into a split diagram requires going through a diagram with Ω(√c) extra crossings. Our proof relies on the framework of bubble tangles, as introduced by the first two authors, and a technique of Chambers and Liokumovitch to turn homotopies into isotopies in the context of Riemannian geometry.
Cite as

Corentin Lunel, Arnaud de Mesmay, and Jonathan Spreer. Hard Diagrams of Split Links. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 67:1-67:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lunel_et_al:LIPIcs.SoCG.2025.67,
  author =	{Lunel, Corentin and de Mesmay, Arnaud and Spreer, Jonathan},
  title =	{{Hard Diagrams of Split Links}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{67:1--67:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.67},
  URN =		{urn:nbn:de:0030-drops-232191},
  doi =		{10.4230/LIPIcs.SoCG.2025.67},
  annote =	{Keywords: Knot theory, hard knot and link diagrams, Reidemeister moves, extra crossings, split links, bubble tangles, compression representativity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.38
An Algorithm for Tambara-Yamagami Quantum Invariants of 3-Manifolds, Parameterized by the First Betti Number

Authors: Colleen Delaney, Clément Maria, and Eric Samperton

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Quantum topology provides various frameworks for defining and computing invariants of manifolds inspired by quantum theory. One such framework of substantial interest in both mathematics and physics is the Turaev-Viro-Barrett-Westbury state sum construction, which uses the data of a spherical fusion category to define topological invariants of triangulated 3-manifolds via tensor network contractions. In this work we analyze the computational complexity of state sum invariants of 3-manifolds derived from Tambara-Yamagami categories. While these categories are the simplest source of state sum invariants beyond finite abelian groups (whose invariants can be computed in polynomial time) their computational complexities are yet to be fully understood. We first establish that the invariants arising from even the smallest Tambara-Yamagami categories are #P-hard to compute, so that one expects the same to be true of the whole family. Our main result is then the existence of a fixed parameter tractable algorithm to compute these 3-manifold invariants, where the parameter is the first Betti number of the 3-manifold with ℤ/2ℤ coefficients. Contrary to other domains of computational topology, such as graphs on surfaces, very few hard problems in 3-manifold topology are known to admit FPT algorithms with a topological parameter. However, such algorithms are of particular interest as their complexity depends only polynomially on the combinatorial representation of the input, regardless of size or combinatorial width. Additionally, in the case of Betti numbers, the parameter itself is computable in polynomial time. Thus while one generally expects quantum invariants to be hard to compute classically, our results suggest that the hardness of computing state sum invariants from Tambara-Yamagami categories arises from classical 3-manifold topology rather than the quantum nature of the algebraic input.
Cite as

Colleen Delaney, Clément Maria, and Eric Samperton. An Algorithm for Tambara-Yamagami Quantum Invariants of 3-Manifolds, Parameterized by the First Betti Number. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{delaney_et_al:LIPIcs.SoCG.2025.38,
  author =	{Delaney, Colleen and Maria, Cl\'{e}ment and Samperton, Eric},
  title =	{{An Algorithm for Tambara-Yamagami Quantum Invariants of 3-Manifolds, Parameterized by the First Betti Number}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{38:1--38:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.38},
  URN =		{urn:nbn:de:0030-drops-231901},
  doi =		{10.4230/LIPIcs.SoCG.2025.38},
  annote =	{Keywords: 3-manifold, quantum invariant, fixed parameter tractable algorithm, topological parameter, Gauss sums, topological quantum field theory}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.28
Small Triangulations of 4-Manifolds and the 4-Manifold Census

Authors: Rhuaidi Antonio Burke, Benjamin A. Burton, and Jonathan Spreer

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We present a framework to classify PL-types of large censuses of triangulated 4-manifolds, which we use to classify the PL-types of all triangulated 4-manifolds with up to 6 pentachora. This is successful except for triangulations homeomorphic to the 4-sphere, CP², and the rational homology sphere QS⁴(2), where we find at most four, three, and two PL-types respectively. We conjecture that they are all standard. In addition, we look at the cases resisting classification and discuss the combinatorial structure of these triangulations - which we deem interesting in their own rights.
Cite as

Rhuaidi Antonio Burke, Benjamin A. Burton, and Jonathan Spreer. Small Triangulations of 4-Manifolds and the 4-Manifold Census. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{burke_et_al:LIPIcs.SoCG.2025.28,
  author =	{Burke, Rhuaidi Antonio and Burton, Benjamin A. and Spreer, Jonathan},
  title =	{{Small Triangulations of 4-Manifolds and the 4-Manifold Census}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.28},
  URN =		{urn:nbn:de:0030-drops-231805},
  doi =		{10.4230/LIPIcs.SoCG.2025.28},
  annote =	{Keywords: computational low-dimensional topology, triangulations, census of triangulations, 4-manifolds, PL standard 4-sphere, Pachner graph, mathematical software, experiments in low-dimensional topology}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.18
Finding a Shortest Curve That Separates Few Objects from Many

Authors: Therese Biedl, Éric Colin de Verdière, Fabrizio Frati, Anna Lubiw, and Günter Rote

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We present a fixed-parameter tractable (FPT) algorithm to find a shortest curve that encloses a set of k required objects in the plane while paying a penalty for enclosing unwanted objects. The input is a set of interior-disjoint simple polygons in the plane, where k of the polygons are required to be enclosed and the remaining optional polygons have non-negative penalties. The goal is to find a closed curve that is disjoint from the polygon interiors and encloses the k required polygons, while minimizing the length of the curve plus the penalties of the enclosed optional polygons. If the penalties are high, the output is a shortest curve that separates the required polygons from the others. The problem is NP-hard if k is not fixed, even in very special cases. The runtime of our algorithm is O(3^k n³), where n is the number of vertices of the input polygons. We extend the result to a graph version of the problem where the input is a connected plane graph with positive edge weights. There are k required faces; the remaining faces are optional and have non-negative penalties. The goal is to find a closed walk in the graph that encloses the k required faces, while minimizing the weight of the walk plus the penalties of the enclosed optional faces. We also consider an inverted version of the problem where the required objects must lie outside the curve. Our algorithms solve some other well-studied problems, such as geometric knapsack.
Cite as

Therese Biedl, Éric Colin de Verdière, Fabrizio Frati, Anna Lubiw, and Günter Rote. Finding a Shortest Curve That Separates Few Objects from Many. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.SoCG.2025.18,
  author =	{Biedl, Therese and Colin de Verdi\`{e}re, \'{E}ric and Frati, Fabrizio and Lubiw, Anna and Rote, G\"{u}nter},
  title =	{{Finding a Shortest Curve That Separates Few Objects from Many}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.18},
  URN =		{urn:nbn:de:0030-drops-231701},
  doi =		{10.4230/LIPIcs.SoCG.2025.18},
  annote =	{Keywords: Enclosure, curve, separation, weakly simple polygon, Euler tour}
}
Document
DOI: 10.4230/DagRep.14.2.120
Triangulations in Geometry and Topology (Dagstuhl Seminar 24072)

Authors: Maike Buchin, Jean Cardinal, Arnaud de Mesmay, Jonathan Spreer, and Alex He

Published in: Dagstuhl Reports, Volume 14, Issue 2 (2024)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar "Triangulations in Geometry and Topology" (24072). The seminar was held from February 12 to February 16, 2024, gathered 31 participants, and started with four introductory talks and an open problem session. Then the participants spread into small groups to work on open problems on diverse topics including reconfiguration of geometric shapes, geodesics on triangulated surfaces, distances in flip graphs, geometric cycles and algorithms in 3-manifold topology.
Cite as

Maike Buchin, Jean Cardinal, Arnaud de Mesmay, Jonathan Spreer, and Alex He. Triangulations in Geometry and Topology (Dagstuhl Seminar 24072). In Dagstuhl Reports, Volume 14, Issue 2, pp. 120-163, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{buchin_et_al:DagRep.14.2.120,
  author =	{Buchin, Maike and Cardinal, Jean and de Mesmay, Arnaud and Spreer, Jonathan and He, Alex},
  title =	{{Triangulations in Geometry and Topology (Dagstuhl Seminar 24072)}},
  pages =	{120--163},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{14},
  number =	{2},
  editor =	{Buchin, Maike and Cardinal, Jean and de Mesmay, Arnaud and Spreer, Jonathan and He, Alex},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.14.2.120},
  URN =		{urn:nbn:de:0030-drops-205017},
  doi =		{10.4230/DagRep.14.2.120},
  annote =	{Keywords: computational geometry, geometric topology, triangulations}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.42
On the Width of Complicated JSJ Decompositions

Authors: Kristóf Huszár and Jonathan Spreer

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
Motivated by the algorithmic study of 3-dimensional manifolds, we explore the structural relationship between the JSJ decomposition of a given 3-manifold and its triangulations. Building on work of Bachman, Derby-Talbot and Sedgwick, we show that a "sufficiently complicated" JSJ decomposition of a 3-manifold enforces a "complicated structure" for all of its triangulations. More concretely, we show that, under certain conditions, the treewidth (resp. pathwidth) of the graph that captures the incidences between the pieces of the JSJ decomposition of an irreducible, closed, orientable 3-manifold M yields a linear lower bound on its treewidth tw (M) (resp. pathwidth pw(M)), defined as the smallest treewidth (resp. pathwidth) of the dual graph of any triangulation of M. We present several applications of this result. We give the first example of an infinite family of bounded-treewidth 3-manifolds with unbounded pathwidth. We construct Haken 3-manifolds with arbitrarily large treewidth - previously the existence of such 3-manifolds was only known in the non-Haken case. We also show that the problem of providing a constant-factor approximation for the treewidth (resp. pathwidth) of bounded-degree graphs efficiently reduces to computing a constant-factor approximation for the treewidth (resp. pathwidth) of 3-manifolds.
Cite as

Kristóf Huszár and Jonathan Spreer. On the Width of Complicated JSJ Decompositions. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 42:1-42:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{huszar_et_al:LIPIcs.SoCG.2023.42,
  author =	{Husz\'{a}r, Krist\'{o}f and Spreer, Jonathan},
  title =	{{On the Width of Complicated JSJ Decompositions}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{42:1--42:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.42},
  URN =		{urn:nbn:de:0030-drops-178920},
  doi =		{10.4230/LIPIcs.SoCG.2023.42},
  annote =	{Keywords: computational 3-manifold topology, fixed-parameter tractability, generalized Heegaard splittings, JSJ decompositions, pathwidth, treewidth, triangulations}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.13
Parametrized Complexity of Expansion Height

Authors: Ulrich Bauer, Abhishek Rathod, and Jonathan Spreer

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Deciding whether two simplicial complexes are homotopy equivalent is a fundamental problem in topology, which is famously undecidable. There exists a combinatorial refinement of this concept, called simple-homotopy equivalence: two simplicial complexes are of the same simple-homotopy type if they can be transformed into each other by a sequence of two basic homotopy equivalences, an elementary collapse and its inverse, an elementary expansion. In this article we consider the following related problem: given a 2-dimensional simplicial complex, is there a simple-homotopy equivalence to a 1-dimensional simplicial complex using at most p expansions? We show that the problem, which we call the erasability expansion height, is W[P]-complete in the natural parameter p.
Cite as

Ulrich Bauer, Abhishek Rathod, and Jonathan Spreer. Parametrized Complexity of Expansion Height. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:LIPIcs.ESA.2019.13,
  author =	{Bauer, Ulrich and Rathod, Abhishek and Spreer, Jonathan},
  title =	{{Parametrized Complexity of Expansion Height}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{13:1--13:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.13},
  URN =		{urn:nbn:de:0030-drops-111346},
  doi =		{10.4230/LIPIcs.ESA.2019.13},
  annote =	{Keywords: Simple-homotopy theory, simple-homotopy type, parametrized complexity theory, simplicial complexes, (modified) dunce hat}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.44
3-Manifold Triangulations with Small Treewidth

Authors: Kristóf Huszár and Jonathan Spreer

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
Motivated by fixed-parameter tractable (FPT) problems in computational topology, we consider the treewidth tw(M) of a compact, connected 3-manifold M, defined to be the minimum treewidth of the face pairing graph of any triangulation T of M. In this setting the relationship between the topology of a 3-manifold and its treewidth is of particular interest. First, as a corollary of work of Jaco and Rubinstein, we prove that for any closed, orientable 3-manifold M the treewidth tw(M) is at most 4g(M)-2, where g(M) denotes Heegaard genus of M. In combination with our earlier work with Wagner, this yields that for non-Haken manifolds the Heegaard genus and the treewidth are within a constant factor. Second, we characterize all 3-manifolds of treewidth one: These are precisely the lens spaces and a single other Seifert fibered space. Furthermore, we show that all remaining orientable Seifert fibered spaces over the 2-sphere or a non-orientable surface have treewidth two. In particular, for every spherical 3-manifold we exhibit a triangulation of treewidth at most two. Our results further validate the parameter of treewidth (and other related parameters such as cutwidth or congestion) to be useful for topological computing, and also shed more light on the scope of existing FPT-algorithms in the field.
Cite as

Kristóf Huszár and Jonathan Spreer. 3-Manifold Triangulations with Small Treewidth. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 44:1-44:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{huszar_et_al:LIPIcs.SoCG.2019.44,
  author =	{Husz\'{a}r, Krist\'{o}f and Spreer, Jonathan},
  title =	{{3-Manifold Triangulations with Small Treewidth}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{44:1--44:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.44},
  URN =		{urn:nbn:de:0030-drops-104487},
  doi =		{10.4230/LIPIcs.SoCG.2019.44},
  annote =	{Keywords: computational 3-manifold topology, fixed-parameter tractability, layered triangulations, structural graph theory, treewidth, cutwidth, Heegaard genus, lens spaces, Seifert fibered spaces}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.46
On the Treewidth of Triangulated 3-Manifolds

Authors: Kristóf Huszár, Jonathan Spreer, and Uli Wagner

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
In graph theory, as well as in 3-manifold topology, there exist several width-type parameters to describe how "simple" or "thin" a given graph or 3-manifold is. These parameters, such as pathwidth or treewidth for graphs, or the concept of thin position for 3-manifolds, play an important role when studying algorithmic problems; in particular, there is a variety of problems in computational 3-manifold topology - some of them known to be computationally hard in general - that become solvable in polynomial time as soon as the dual graph of the input triangulation has bounded treewidth. In view of these algorithmic results, it is natural to ask whether every 3-manifold admits a triangulation of bounded treewidth. We show that this is not the case, i.e., that there exists an infinite family of closed 3-manifolds not admitting triangulations of bounded pathwidth or treewidth (the latter implies the former, but we present two separate proofs). We derive these results from work of Agol and of Scharlemann and Thompson, by exhibiting explicit connections between the topology of a 3-manifold M on the one hand and width-type parameters of the dual graphs of triangulations of M on the other hand, answering a question that had been raised repeatedly by researchers in computational 3-manifold topology. In particular, we show that if a closed, orientable, irreducible, non-Haken 3-manifold M has a triangulation of treewidth (resp. pathwidth) k then the Heegaard genus of M is at most 48(k+1) (resp. 4(3k+1)).
Cite as

Kristóf Huszár, Jonathan Spreer, and Uli Wagner. On the Treewidth of Triangulated 3-Manifolds. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 46:1-46:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{huszar_et_al:LIPIcs.SoCG.2018.46,
  author =	{Husz\'{a}r, Krist\'{o}f and Spreer, Jonathan and Wagner, Uli},
  title =	{{On the Treewidth of Triangulated 3-Manifolds}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{46:1--46:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.46},
  URN =		{urn:nbn:de:0030-drops-87591},
  doi =		{10.4230/LIPIcs.SoCG.2018.46},
  annote =	{Keywords: computational topology, triangulations of 3-manifolds, thin position, fixed-parameter tractability, congestion, treewidth}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.71
The Trisection Genus of Standard Simply Connected PL 4-Manifolds

Authors: Jonathan Spreer and Stephan Tillmann

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
Gay and Kirby recently introduced the concept of a trisection for arbitrary smooth, oriented closed 4-manifolds, and with it a new topological invariant, called the trisection genus. In this note we show that the K3 surface has trisection genus 22. This implies that the trisection genus of all standard simply connected PL 4-manifolds is known. We show that the trisection genus of each of these manifolds is realised by a trisection that is supported by a singular triangulation. Moreover, we explicitly give the building blocks to construct these triangulations.
Cite as

Jonathan Spreer and Stephan Tillmann. The Trisection Genus of Standard Simply Connected PL 4-Manifolds. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 71:1-71:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{spreer_et_al:LIPIcs.SoCG.2018.71,
  author =	{Spreer, Jonathan and Tillmann, Stephan},
  title =	{{The Trisection Genus of Standard Simply Connected PL 4-Manifolds}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{71:1--71:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.71},
  URN =		{urn:nbn:de:0030-drops-87847},
  doi =		{10.4230/LIPIcs.SoCG.2018.71},
  annote =	{Keywords: combinatorial topology, triangulated manifolds, simply connected 4-manifolds, K3 surface, trisections of 4-manifolds}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.64
Admissible Colourings of 3-Manifold Triangulations for Turaev-Viro Type Invariants

Authors: Clément Maria and Jonathan Spreer

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
Turaev-Viro invariants are amongst the most powerful tools to distinguish 3-manifolds. They are invaluable for mathematical software, but current algorithms to compute them rely on the enumeration of an extremely large set of combinatorial data defined on the triangulation, regardless of the underlying topology of the manifold. In the article, we propose a finer study of these combinatorial data, called admissible colourings, in relation with the cohomology of the manifold. We prove that the set of admissible colourings to be considered is substantially smaller than previously known, by furnishing new upper bounds on its size that are aware of the topology of the manifold. Moreover, we deduce new topology-sensitive enumeration algorithms based on these bounds. The paper provides a theoretical analysis, as well as a detailed experimental study of the approach. We give strong experimental evidence on large manifold censuses that our upper bounds are tighter than the previously known ones, and that our algorithms outperform significantly state of the art implementations to compute Turaev-Viro invariants.
Cite as

Clément Maria and Jonathan Spreer. Admissible Colourings of 3-Manifold Triangulations for Turaev-Viro Type Invariants. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 64:1-64:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{maria_et_al:LIPIcs.ESA.2016.64,
  author =	{Maria, Cl\'{e}ment and Spreer, Jonathan},
  title =	{{Admissible Colourings of 3-Manifold Triangulations for Turaev-Viro Type Invariants}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{64:1--64:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.64},
  URN =		{urn:nbn:de:0030-drops-64050},
  doi =		{10.4230/LIPIcs.ESA.2016.64},
  annote =	{Keywords: low-dimensional topology, triangulations of 3-manifolds, cohomology theory, Turaev-Viro invariants, combinatorial algorithms}
}
  • Refine by Type
  • 14 Document/PDF
  • 6 Document/HTML
  • 2 Artifact

  • Refine by Publication Year
  • 8 2025
  • 1 2024
  • 1 2023
  • 2 2019
  • 2 2018
  • Show More...

  • Refine by Author
  • 12 Spreer, Jonathan
  • 3 Burton, Benjamin A.
  • 3 Huszár, Kristóf
  • 3 Maria, Clément
  • 2 Burke, Rhuaidi Antonio
  • Show More...

  • Refine by Series/Journal
  • 13 LIPIcs
  • 1 DagRep

  • Refine by Classification
  • 8 Mathematics of computing → Geometric topology
  • 5 Theory of computation → Computational geometry
  • 4 Theory of computation → Problems, reductions and completeness
  • 3 Theory of computation → Fixed parameter tractability
  • 1 Human-centered computing → Graph drawings
  • Show More...

  • Refine by Keyword
  • 3 fixed-parameter tractability
  • 3 treewidth
  • 3 triangulations
  • 2 3-manifold
  • 2 computational 3-manifold topology
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact