Efficient algorithms to decide tightness

DOI10.4230/LIPICS.SOCG.2016.12zbMATH Open1387.52008arXiv1412.1547MaRDI QIDQ3132845FDOQ3132845

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

Publication date: 30 January 2018

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$.

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

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

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)

Cited In (3)

• A Construction Principle for Tight and Minimal Triangulations of Manifolds
• Tight triangulations of closed 3-manifolds
• The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex

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)