Back to Search
Start Over
An Improvement of Reed’s Treewidth Approximation
- Source :
- WALCOM: Algorithms and Computation ISBN: 9783030682101, WALCOM
- Publication Year :
- 2021
- Publisher :
- Springer International Publishing, 2021.
-
Abstract
- We present a new approximation algorithm for the treewidth problem which constructs a corresponding tree decomposition as well. Our algorithm is a faster variation of Reed’s classical algorithm. For the benefit of the reader, and to be able to compare these two algorithms, we start with a detailed time analysis for Reed’s algorithm. We fill in many details that have been omitted in Reed’s paper. Computing tree decompositions parameterized by the treewidth k is fixed parameter tractable (FPT), meaning that there are algorithms running in time O(f(k)g(n)) where f is a computable function, g(n) is polynomial in n, and n is the number of vertices. An analysis of Reed’s algorithm shows \(f(k) = 2^{O(k \log k)}\) and \(g(n) = n \log n\) for a 5-approximation. Reed simply claims time \(O(n \log n)\) for bounded k for his constant factor approximation algorithm, but the bound of \(2^{\varOmega (k \log k)} n \log n\) is well known. From a practical point of view, we notice that the time of Reed’s algorithm also contains a term of \(O(k^2 2^{24k} n \log n)\), which for small k is much worse than the asymptotically leading term of \(2^{O(k \log k)} n \log n\). We analyze f(k) more precisely, because the purpose of this paper is to improve the running times for all reasonably small values of k.
- Subjects :
- Polynomial (hyperelastic model)
Parameterized complexity
Approximation algorithm
0102 computer and information sciences
02 engineering and technology
Binary logarithm
01 natural sciences
Tree decomposition
Treewidth
Combinatorics
Tree (descriptive set theory)
Computable function
010201 computation theory & mathematics
0202 electrical engineering, electronic engineering, information engineering
020201 artificial intelligence & image processing
Mathematics
Subjects
Details
- ISBN :
- 978-3-030-68210-1
- ISBNs :
- 9783030682101
- Database :
- OpenAIRE
- Journal :
- WALCOM: Algorithms and Computation ISBN: 9783030682101, WALCOM
- Accession number :
- edsair.doi...........0b32619540d4c74203956e4be6d48cff