twheuristic
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 fixedparameter tractable when parameterized by (k) and (c), but it is paraNPhard 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; fixedparameter 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.68490 Gaspers, 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 (68XX) 
2  Combinatorics (05XX) 