Fixed parameter tractable algorithms in combinatorial topology
Benjamin A. Burton, William Pettersson · 2014
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 triangula-tions using an exponential-time enumeration. However, asymptotically most graphs do not result in any 3-manifold triangulation, which leads to signif-icant “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 prop-erties 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 mit-igate the large constants that so often occur in parameterised complexity, highlighting the practicality of our techniques. 1.