Fixed parameter tractable algorithms in combinatorial topology

Burton, Benjamin A. and Pettersson, William (2014). Fixed parameter tractable algorithms in combinatorial topology. In: Zhipeng Cai, Alex Zelikovsky and Anu Bourgeois, Computing and Combinatorics - 20th International Conference, COCOON 2014, Proceedings. 20th International Computing and Combinatorics Conference, COCOON 2014, Atlanta, GA United States, (300-311). 2 - 6 August 2014. doi:10.1007/978-3-319-08783-2_26


Author Burton, Benjamin A.
Pettersson, William
Title of paper Fixed parameter tractable algorithms in combinatorial topology
Conference name 20th International Computing and Combinatorics Conference, COCOON 2014
Conference location Atlanta, GA United States
Conference dates 2 - 6 August 2014
Proceedings title Computing and Combinatorics - 20th International Conference, COCOON 2014, Proceedings   Check publisher's open access policy
Journal name Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   Check publisher's open access policy
Series Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Place of Publication Heidelberg, Germany
Publisher Springer
Publication Year 2014
Year available 2014
Sub-type Fully published paper
DOI 10.1007/978-3-319-08783-2_26
Open Access Status
ISBN 9783319087825
9783319087832
ISSN 0302-9743
1611-3349
Editor Zhipeng Cai
Alex Zelikovsky
Anu Bourgeois
Volume 8591 LNCS
Start page 300
End page 311
Total pages 12
Chapter number 26
Total chapters 61
Collection year 2015
Abstract/Summary 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.
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ

Document type: Conference Paper
Collections: School of Mathematics and Physics
Official 2015 Collection
 
Versions
Version Filter Type
Citation counts: Scopus Citation Count Cited 1 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 12 Aug 2014, 02:42:29 EST by System User on behalf of School of Mathematics & Physics