tw-heuristic swMATH ID: 34759 Software Authors: Gaspers, Serge; Gudmundsson, Joachim; Jones, Mitchell; Mestre, Julián; Rümmele, Stefan Description: Turbocharging treewidth heuristics. A widely used class of algorithms for computing tree decompositions of graphs are heuristics that compute an elimination order, i.e., a permutation of the vertex set. In this paper, we propose to turbocharge these heuristics. For a target treewidth (k), suppose the heuristic has already computed a partial elimination order of width at most (k), but extending it by one more vertex exceeds the target width (k). At this moment of regret, we solve a subproblem which is to recompute the last (c) positions of the partial elimination order such that it can be extended without exceeding width (k). We show that this subproblem is fixed-parameter tractable when parameterized by (k) and (c), but it is para-NP-hard and W[1]-hard when parameterized by only (k) or (c), respectively. Our experimental evaluation of the FPT algorithm shows that we can trade a reasonable increase of the running time for quality of the solution. Homepage: https://drops.dagstuhl.de/opus/volltexte/2017/6932/ Source Code: https://github.com/mfjones/pace2016 Keywords: tree decomposition; heuristic; fixed-parameter tractability; local search Related Software: GitHub; ComputeTW Cited in: 3 Publications Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Turbocharging treewidth heuristics. Zbl 1398.68490Gaspers, Serge; Gudmundsson, Joachim; Jones, Mitchell; Mestre, Julián; Rümmele, Stefan 2017 all top 5 Cited by 8 Authors 2 Gaspers, Serge 2 Gudmundsson, Joachim 2 Jones, Mitchell 2 Mestre, Julián 2 Rümmele, Stefan 1 Krithika, R. 1 Sahu, Abhishek 1 Tale, Prafullkumar Cited in 1 Serial 2 Algorithmica Cited in 2 Fields 3 Computer science (68-XX) 2 Combinatorics (05-XX) Citations by Year