Efficient algorithms to decide tightness

DOI10.4230/LIPICS.SOCG.2016.12MaRDI QIDQ3132845zbMATH OpenFDO

Authors Bhaskar Bagchi, Nitin Singh, Jonathan Spreer, Basudeb Datta, Benjamin A. Burton

Publication date 30 January 2018

Full work available at URL https://arxiv.org/abs/1412.1547

zbMATH Keywords

simplicial complexesfixed-parameter tractabilitypolynomial-time algorithmstight triangulationsdiscrete geometry and topology

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Simplicial sets and complexes in algebraic topology (55U10) Variants of convex sets (star-shaped, ((m, n))-convex, etc.) (52A30)

Abstract: Tightness is a generalisation of the notion of convexity: a space is tight if and only if it is "as convex as possible", given its topological constraints. For a simplicial complex, deciding tightness has a straightforward exponential time algorithm, but efficient methods to decide tightness are only known in the trivial setting of triangulated surfaces. In this article, we present a new polynomial time procedure to decide tightness for triangulations of $3$-manifolds -- a problem which previously was thought to be hard. Furthermore, we describe an algorithm to decide general tightness in the case of $4$-dimensional combinatorial manifolds which is fixed parameter tractable in the treewidth of the $1$-skeletons of their vertex links, and we present an algorithm to decide $mathbb{F}_2$-tightness for weak pseudomanifolds $M$ of arbitrary but fixed dimension which is fixed parameter tractable in the treewidth of the dual graph of $M$.

Recommendations

• Efficient solutions and bounds on tradeoffs
• Efficient Algorithms for Functional Constraints
• scientific article; zbMATH DE number 4024619
• An optimal algorithm for finding compact sets
• Principles and Practice of Constraint Programming – CP 2004
• scientific article; zbMATH DE number 579387
• A tighter bound for FFd algorithm
• Efficient algorithms for the smallest enclosing ball problem
• An efficient algorithm to decide the knot problem

Cited in

(5)

• A construction principle for tight and minimal triangulations of manifolds
• A necessary condition for the tightness of odd-dimensional combinatorial manifolds
• The parameterized complexity of finding a 2-sphere in a simplicial complex
• Tight triangulations of closed 3-manifolds
• ETH-tight algorithms for finding surfaces in simplicial complexes of bounded treewidth

This page was built for publication: Efficient algorithms to decide tightness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3132845)