On the Treewidth of Triangulated 3-Manifolds

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



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.46.pdf
  • Filesize: 0.61 MB
  • 15 pages

Document Identifiers

Author Details

Kristóf Huszár
Jonathan Spreer
Uli Wagner

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.SoCG.2018.46

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)).
Keywords
  • computational topology
  • triangulations of 3-manifolds
  • thin position
  • fixed-parameter tractability
  • congestion
  • treewidth

Metrics

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

References

  1. I. Agol. Small 3-manifolds of large genus. Geom. Dedicata, 102:53-64, 2003. URL: http://dx.doi.org/10.1023/B:GEOM.0000006584.85248.c5.
  2. L. Bessières, G. Besson, S. Maillot, M. Boileau, and J. Porti. Geometrisation of 3-manifolds, volume 13 of EMS Tracts in Mathematics. European Mathematical Society (EMS), Zürich, 2010. URL: http://dx.doi.org/10.4171/082.
  3. D. Bienstock. On embedding graphs in trees. J. Comb. Theory, Ser. B, 49(1):103-136, 1990. URL: http://dx.doi.org/10.1016/0095-8956(90)90066-9.
  4. D. Bienstock. Graph searching, path-width, tree-width and related problems (A survey). In Reliability Of Computer And Communication Networks, volume 5 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 33-50. Amer. Math. Soc., Providence, RI, 1991. URL: http://dx.doi.org/10.1090/dimacs/005/02.
  5. H. L. Bodlaender. A tourist guide through treewidth. Acta Cybern., 11(1-2):1-21, 1993. URL: http://www.inf.u-szeged.hu/actacybernetica/edb/vol11n1_2/starten.xml.
  6. H. L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci., 209(1-2):1-45, 1998. URL: http://dx.doi.org/10.1016/S0304-3975(97)00228-4.
  7. H. L. Bodlaender. Discovering treewidth. In SOFSEM 2005: Theory and Practice of Computer Science, 31st Conference on Current Trends in Theory and Practice of Computer Science, Liptovský Ján, Slovakia, January 22-28, 2005, Proceedings, pages 1-16, 2005. URL: http://dx.doi.org/10.1007/978-3-540-30577-4_1.
  8. H. L. Bodlaender and A. M. C. A. Koster. Combinatorial optimization on graphs of bounded treewidth. Comput. J., 51(3):255-269, 2008. URL: http://dx.doi.org/10.1093/comjnl/bxm037.
  9. B. A. Burton, R. Budney, W. Pettersson, et al. Regina: Software for 3-manifold topology and normal surface theory, 1999-2017. URL: http://regina-normal.github.io.
  10. B. A. Burton and R. G. Downey. Courcelle’s theorem for triangulations. J. Comb. Theory, Ser. A, 146:264-294, 2017. URL: http://dx.doi.org/10.1016/j.jcta.2016.10.001.
  11. B. A. Burton, H. Edelsbrunner, J. Erickson, and S. Tillmann, editors. Computational Geometric and Algebraic Topology, volume 12 of Oberwolfach Reports. EMS Publishing House, 2015. URL: http://dx.doi.org/10.4171/OWR/2015/45.
  12. B. A. Burton, T. Lewiner, J. Paixão, and J. Spreer. Parameterized complexity of discrete Morse theory. ACM Trans. Math. Softw., 42(1):6:1-6:24, 2016. URL: http://dx.doi.org/10.1145/2738034.
  13. B. A. Burton, C. Maria, and J. Spreer. Algorithms and complexity for Turaev-Viro invariants. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 281-293, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_23.
  14. B. A. Burton and J. Spreer. The complexity of detecting taut angle structures on triangulations. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 168-183, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.13.
  15. F. R. K. Chung and P. D. Seymour. Graphs with small bandwidth and cutwidth. Discrete Mathematics, 75(1-3):113-119, 1989. URL: http://dx.doi.org/10.1016/0012-365X(89)90083-6.
  16. B. Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. URL: http://dx.doi.org/10.1016/0890-5401(90)90043-H.
  17. R. Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer, Berlin, fifth edition, 2017. URL: http://dx.doi.org/10.1007/978-3-662-53622-3.
  18. R. G. Downey and M. R. Fellows. Parameterized complexity. Monographs in Computer Science. Springer-Verlag, New York, 1999. URL: http://dx.doi.org/10.1007/978-1-4612-0515-9.
  19. R. G. Downey and M. R. Fellows. Fundamentals of parameterized complexity. Texts in Computer Science. Springer, London, 2013. URL: http://dx.doi.org/10.1007/978-1-4471-5559-1.
  20. D. Gabai. Foliations and the topology of 3-manifolds. III. J. Differential Geom., 26(3):479-536, 1987. URL: http://dx.doi.org/10.4310/jdg/1214441488.
  21. W. Haken. Theorie der Normalflächen. Acta Math., 105:245-375, 1961. URL: http://dx.doi.org/10.1007/BF02559591.
  22. J. Hass, J. C. Lagarias, and N. Pippenger. The computational complexity of knot and link problems. J. ACM, 46(2):185-211, 1999. URL: http://dx.doi.org/10.1145/301970.301971.
  23. A. E. Hatcher. On the boundary curves of incompressible surfaces. Pacific J. Math., 99(2):373-377, 1982. URL: http://dx.doi.org/10.2140/pjm.1982.99.373.
  24. P. Hlinený, S. Oum, D. Seese, and G. Gottlob. Width parameters beyond tree-width and their applications. Comput. J., 51(3):326-362, 2008. URL: http://dx.doi.org/10.1093/comjnl/bxm052.
  25. H. Howards, Y. Rieck, and J. Schultens. Thin position for knots and 3-manifolds: a unified approach. In Workshop on Heegaard Splittings, volume 12 of Geom. Topol. Monogr., pages 89-120. Geom. Topol. Publ., Coventry, 2007. URL: http://dx.doi.org/10.2140/gtm.2007.12.89.
  26. K. Huszár, J. Spreer, and U. Wagner. On the treewidth of triangulated 3-manifolds, 2017. URL: http://arxiv.org/abs/1712.00434.
  27. S. V. Ivanov. The computational complexity of basic decision problems in 3-dimensional topology. Geom. Dedicata, 131:1-26, 2008. URL: http://dx.doi.org/10.1007/s10711-007-9210-4.
  28. R. Kirby and P. Melvin. Local surgery formulas for quantum invariants and the Arf invariant. In Proceedings of the Casson Fest, volume 7 of Geom. Topol. Monogr., pages 213-233. Geom. Topol. Publ., Coventry, 2004. URL: http://dx.doi.org/10.2140/gtm.2004.7.213.
  29. B. Kleiner and J. Lott. Notes on Perelman’s papers. Geom. Topol., 12(5):2587-2855, 2008. URL: http://dx.doi.org/10.2140/gt.2008.12.2587.
  30. G. Kuperberg. Knottedness is in NP, modulo GRH. Adv. Math., 256:493-506, 2014. URL: http://dx.doi.org/10.1016/j.aim.2014.01.007.
  31. G. Kuperberg. Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization, 2015. URL: http://arxiv.org/abs/1508.06720.
  32. M. Lackenby. The efficient certification of knottedness and Thurston norm, 2016. URL: http://arxiv.org/abs/1604.00290.
  33. M. Lackenby. Some conditionally hard problems on links and 3-manifolds. Discrete & Computational Geometry, 58(3):580-595, 2017. URL: http://dx.doi.org/10.1007/s00454-017-9905-8.
  34. C. Maria and J. Spreer. A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2721-2732, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.180.
  35. E. E. Moise. Affine structures in 3-manifolds. V. The triangulation theorem and Hauptvermutung. Ann. of Math. (2), 56:96-114, 1952. URL: http://dx.doi.org/10.2307/1969769.
  36. Y. Moriah and H. Rubinstein. Heegaard structures of negatively curved 3-manifolds. Comm. Anal. Geom., 5(3):375-412, 1997. URL: http://dx.doi.org/10.4310/CAG.1997.v5.n3.a1.
  37. M. I. Ostrovskii. Minimal congestion trees. Discrete Mathematics, 285(1-3):219-226, 2004. URL: http://dx.doi.org/10.1016/j.disc.2004.02.009.
  38. N. Robertson and P. D. Seymour. Graph minors. I. Excluding a forest. J. Comb. Theory, Ser. B, 35(1):39-61, 1983. URL: http://dx.doi.org/10.1016/0095-8956(83)90079-5.
  39. N. Robertson and P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms, 7(3):309-322, 1986. URL: http://dx.doi.org/10.1016/0196-6774(86)90023-4.
  40. J. H. Rubinstein. An algorithm to recognize the 3-sphere. In S. D. Chatterji, editor, Proceedings of the International Congress of Mathematicians: August 3-11, 1994, Zürich, Switzerland, volume 1, pages 601-611. Birkhäuser Verlag, 1995. Google Scholar
  41. M. Scharlemann, J. Schultens, and T. Saito. Lecture notes on generalized Heegaard splittings. World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2016. Three lectures on low-dimensional topology in Kyoto. URL: http://dx.doi.org/10.1142/10019.
  42. M. Scharlemann and A. Thompson. Thin position for 3-manifolds. In Geometric topology (Haifa, 1992), volume 164 of Contemp. Math., pages 231-238. Amer. Math. Soc., Providence, RI, 1994. URL: http://dx.doi.org/10.1090/conm/164/01596.
  43. S. Schleimer. Sphere recognition lies in NP. In Low-dimensional and symplectic topology, volume 82 of Proc. Sympos. Pure Math., pages 183-213. Amer. Math. Soc., Providence, RI, 2011. URL: http://dx.doi.org/10.1090/pspum/082/2768660.
  44. J. Schultens. Introduction to 3-manifolds, volume 151 of Graduate Studies in Mathematics. Amer. Math. Soc., Providence, RI, 2014. URL: http://dx.doi.org/10.1090/gsm/151.
  45. P. Scott and H. Short. The homeomorphism problem for closed 3-manifolds. Algebr. Geom. Topol., 14(4):2431-2444, 2014. URL: http://dx.doi.org/10.2140/agt.2014.14.2431.
  46. P. D. Seymour and R. Thomas. Call routing and the ratcatcher. Combinatorica, 14(2):217-241, 1994. URL: http://dx.doi.org/10.1007/BF01215352.
  47. A. Thompson. Thin position and the recognition problem for S³. Math. Res. Lett., 1(5):613-630, 1994. URL: http://dx.doi.org/10.4310/MRL.1994.v1.n5.a9.
  48. W. P. Thurston. Three-dimensional geometry and topology. Vol. 1, volume 35 of Princeton Mathematical Series. Princeton University Press, Princeton, NJ, 1997. Edited by Silvio Levy. URL: http://dx.doi.org/10.1515/9781400865321.
  49. R. Zentner. Integer homology 3-spheres admit irreducible representations in SL(2,ℂ), 2016. URL: http://arxiv.org/abs/1605.08530.
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