zbMATH — the first resource for mathematics

New lower and upper bounds for graph treewidth. (English) Zbl 1023.68645
Jansen, Klaus (ed.) et al., Experimental and efficient algorithms. Second international workshop, WEA 2003, Ascona, Switzerland, May 26-28, 2003. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2647, 70-80 (2003).
Summary: The notion of tree-decomposition has very strong theoretical interest related to NP-hard problems. Indeed, several studies show that it can be used to solve many basic optimization problems in polynomial time when the treewidth is bounded. So, given an arbitrary graph, its decomposition and its treewidth have to be determined, but computing the treewidth of a graph is NP-hard. Hence, several papers present heuristics with computational experiments, but for many instances of graphs, the heuristic results are far from the best lower bounds.
The aim of this paper is to propose new lower and upper bounds for the treewidth. We tested them on the well known DIMACS benchmark for graph coloring, so we can compare our results to the best bounds of the literature. We improve the best lower bounds dramatically, and our heuristic method computes good bounds within a very small computing time.
For the entire collection see [Zbl 1019.00014].

68R10 Graph theory (including graph drawing) in computer science
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: Link