Back to Search
Start Over
Turbocharging Treewidth Heuristics.
- Source :
-
Algorithmica . Feb2019, Vol. 81 Issue 2, p439-475. 37p. - Publication Year :
- 2019
-
Abstract
- 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 treewidthk, 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 the quality of the solution. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 81
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 134622977
- Full Text :
- https://doi.org/10.1007/s00453-018-0499-1