Fixed parameter tractable algorithms in combinatorial topology

DOI10.1007/978-3-319-08783-2_26MaRDI QIDQ2920468zbMATH OpenOpenAlexFDO

Authors William Pettersson, Benjamin A. Burton

Publication date 26 September 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Relations of low-dimensional topology with graph theory (57M15) Triangulating manifolds (57Q15) Analysis of algorithms and problem complexity (68Q25)

Abstract: To enumerate 3-manifold triangulations with a given property, one typically begins with a set of potential face pairing graphs (also known as dual 1-skeletons), and then attempts to flesh each graph out into full triangulations using an exponential-time enumeration. However, asymptotically most graphs do not result in any 3-manifold triangulation, which leads to significant "wasted time" in topological enumeration algorithms. Here we give a new algorithm to determine whether a given face pairing graph supports any 3-manifold triangulation, and show this to be fixed parameter tractable in the treewidth of the graph. We extend this result to a "meta-theorem" by defining a broad class of properties of triangulations, each with a corresponding fixed parameter tractable existence algorithm. We explicitly implement this algorithm in the most generic setting, and we identify heuristics that in practice are seen to mitigate the large constants that so often occur in parameterised complexity, highlighting the practicality of our techniques.

Recommendations

• An edge-based framework for enumerating 3-manifold triangulations
• Detecting genus in vertex links for the fast enumeration of 3-manifold triangulations
• Isomorphism-free lexicographic enumeration of triangulated surfaces and 3-manifolds
• scientific article; zbMATH DE number 7236450
• Enumeration of non-orientable 3-manifolds using face-pairing graphs and union-find

Cited in

(14)

• A new combinatorial class of \(3\)-manifold triangulations
• Topology of cycles in pseudolinear programs
• Treewidth, crushing and hyperbolic volume
• Courcelle's theorem for triangulations
• A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number
• FACE PAIRING GRAPHS AND 3-MANIFOLD ENUMERATION
• 3-manifold triangulations with small treewidth
• The parameterized complexity of finding a 2-sphere in a simplicial complex
• Detecting genus in vertex links for the fast enumeration of 3-manifold triangulations
• An edge-based framework for enumerating 3-manifold triangulations
• The complexity of detecting taut angle structures on triangulations
• On the pathwidth of hyperbolic 3-manifolds
• On the width of complicated JSJ decompositions
• On the twin-width of smooth manifolds

This page was built for publication: Fixed parameter tractable algorithms in combinatorial topology

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