Document Open Access Logo

The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex

Authors Benjamin Burton, Sergio Cabello, Stefan Kratsch, William Pettersson

PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.18.pdf
  • Filesize: 0.61 MB
  • 14 pages

Document Identifiers

Author Details

Benjamin Burton
Sergio Cabello
Stefan Kratsch
William Pettersson

Cite As Get BibTex

Benjamin Burton, Sergio Cabello, Stefan Kratsch, and William Pettersson. The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.STACS.2017.18

Abstract

We consider the problem of finding a subcomplex K' of a simplicial complex K such that K' is homeomorphic to the 2-dimensional sphere, S^2. We study two variants of this problem. The first asks if there exists such a K' with at most k triangles, and we show that this variant is W[1]-hard and, assuming ETH, admits no O(n^(o(sqrt(k)))) time algorithm. We also give an algorithm that is tight with regards to this lower bound. The second problem is the dual of the first, and asks if K' can be found by removing at most k triangles from K. This variant has an immediate O(3^k poly(|K|)) time algorithm, and we show that it admits a polynomial kernelization to O(k^2) triangles, as well as a polynomial compression to a weighted version with bit-size O(k log k).

Subject Classification

Keywords
  • computational topology
  • parameterized complexity
  • simplicial complex

Metrics

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

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. URL: http://dx.doi.org/10.1145/210332.210337.
  2. Bhaskar Bagchi, Benjamin A. Burton, Basudeb Datta, Nitin Singh, and Jonathan Spreer. Efficient algorithms to decide tightness. In Sándor Fekete and Anna Lubiw, editors, 32nd International Symposium on Computational Geometry (SoCG 2016), volume 51 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1-12:15, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  3. Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Dominique Poulalhon, and Gilles Schaeffer. Planar graphs, via well-orderly maps and trees. Graphs and Combinatorics, 22(2):185-202, 2006. URL: http://dx.doi.org/10.1007/s00373-006-0647-2.
  4. Benjamin A. Burton and Rodney G. Downey. Courcelle’s theorem for triangulations. URL: http://arxiv.org/abs/1403.2926.
  5. Benjamin A. Burton, Clément Maria, and Jonathan 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 1, pages 281-293. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_23.
  6. Benjamin A. Burton and William Pettersson. Fixed parameter tractable algorithms in combinatorial topology. In Zhipengand Cai, Alexand Zelikovsky, and Anu Bourgeois, editors, Computing and Combinatorics: 20th International Conference, COCOON 2014, Atlanta, GA, USA, August 4-6, 2014. Proceedings, pages 300-311, Cham, 2014. Springer International Publishing. URL: http://dx.doi.org/10.1007/978-3-319-08783-2_26.
  7. Oleksiy Busaryev, Sergio Cabello, Chao Chen, Tamal K. Dey, and Yusu Wang. Annotating simplices with a homology basis and its applications. In Fedor V. Fomin and Petteri Kaski, editors, Algorithm Theory - SWAT 2012 - 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings, volume 7357 of Lecture Notes in Computer Science, pages 189-200. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31155-0_17.
  8. Chao Chen and Daniel Freedman. Hardness results for homology localization. Discrete & Computational Geometry, 45(3):425-448, 2011. URL: http://dx.doi.org/10.1007/s00454-010-9322-8.
  9. Jeff Erickson and Amir Nayyeri. Minimum cuts and shortest non-separating cycles via homology covers. In Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 1166-1176. SIAM, 2011. URL: http://dx.doi.org/10.1137/1.9781611973082.88.
  10. Michael Hartley Freedman. The topology of four-dimensional manifolds. J. Differential Geom., 17(3):357-453, 1982. URL: http://projecteuclid.org/euclid.jdg/1214437136.
  11. Sergei Ivanov. computational complexity (answer). MathOverflow. URL: http://mathoverflow.net/questions/118357/computational-complexity.
  12. Ken-ichi Kawarabayashi, Bojan Mohar, and Bruce A. Reed. A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 771-780. IEEE Computer Society, 2008. URL: http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=4690923, URL: http://dx.doi.org/10.1109/FOCS.2008.53.
  13. Clément Maria and Jonathan Spreer. A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number. http://arxiv.org/abs/1607.02218 [cs.CG], 2016. 15 pages, 3 figures. Google Scholar
  14. Dániel Marx. A tight lower bound for planar multiway cut with fixed number of terminals. In Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer, editors, Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, volume 7391 of Lecture Notes in Computer Science, pages 677-688. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31594-7_57.
  15. Jiří Matoušek. Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry. Universitext. Springer, 2007. Google Scholar
  16. Bojan Mohar. A linear time algorithm for embedding graphs in an arbitrary surface. SIAM J. Discrete Math., 12(1):6-26, 1999. URL: http://dx.doi.org/10.1137/S089548019529248X.
  17. James R. Munkres. Elements of Algebraic Topology. Addison-Wesley, 1993. Google Scholar
  18. A. Nabutovsky. Einstein structures: Existence versus uniqueness. Geometric & Functional Analysis GAFA, 5(1):76-91, 1995. URL: http://dx.doi.org/10.1007/BF01928216.
  19. Saul Schleimer. Sphere recognition lies in NP. In Michael Usher, editor, Low-Dimensional and Symplectic Topology, volume 82 of Proceedings of Symposia in Pure Mathematics, pages 183-213. AMS, 2011. Google Scholar
  20. W. T. Tutte. A census of planar triangulations. Canad. J. Math., 14:21-38, 1962. URL: http://dx.doi.org/10.4153/CJM-1962-002-9.
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