2026-07-23T21:56:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16025 2024-03-06T10:56:46Z ddc:004 open_access

ETH-Tight Algorithms for Finding Surfaces in Simplicial Complexes of Bounded Treewidth Black, Mitchell Blaser, Nello Nayyeri, Amir Vågset, Erlend Raa Computational Geometry Surface Recognition Treewidth Hasse Diagram Simplicial Complexes Low-Dimensional Topology Parameterized Complexity Computational Complexity Given a simplicial complex with n simplices, we consider the Connected Subsurface Recognition (c-SR) problem of finding a subcomplex that is homeomorphic to a given connected surface with a fixed boundary. We also study the related Sum-of-Genus Subsurface Recognition (SoG) problem, where we instead search for a surface whose boundary, number of connected components, and total genus are given. For both of these problems, we give parameterized algorithms with respect to the treewidth k of the Hasse diagram that run in 2^{O(k log k)}n^{O(1)} time. For the SoG problem, we also prove that our algorithm is optimal assuming the exponential-time hypothesis. In fact, we prove the stronger result that our algorithm is ETH-tight even without restriction on the total genus. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mitchell Black and Nello Blaser and Amir Nayyeri and Erlend Raa Vågset 2022 Is Part Of LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2022.17 urn:nbn:de:0030-drops-160253 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.17 eng https://creativecommons.org/licenses/by/4.0/legalcode