Approximation Algorithms for Treewidth |
| |
Authors: | Eyal Amir |
| |
Affiliation: | (2) Institute of Information and Computing Sciences Algorithms and Complexity Group, Center for Algorithmic Systems, University of Utrecht, Utrecht, The Netherlands |
| |
Abstract: | This paper presents algorithms whose input is an undirected graph, and whose output is a tree decomposition of width that
approximates the optimal, the treewidth of that graph. The algorithms differ in their computation time and their approximation guarantees. The first algorithm works
in polynomial-time and finds a factor-O(log OPT) approximation, where OPT is the treewidth of the graph. This is the first polynomial-time algorithm that approximates the optimal by a factor that
does not depend on n, the number of nodes in the input graph. As a result, we get an algorithm for finding pathwidth within a factor of O(log OPT⋅log n) from the optimal. We also present algorithms that approximate the treewidth of a graph by constant factors of 3.66, 4, and
4.5, respectively and take time that is exponential in the treewidth. These are more efficient than previously known algorithms
by an exponential factor, and are of practical interest. Finding triangulations of minimum treewidth for graphs is central
to many problems in computer science. Real-world problems in artificial intelligence, VLSI design and databases are efficiently
solvable if we have an efficient approximation algorithm for them. Many of those applications rely on weighted graphs. We
extend our results to weighted graphs and weighted treewidth, showing similar approximation results for this more general notion. We report on experimental results confirming the effectiveness
of our algorithms for large graphs associated with real-world problems. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|