Approximating Treewidth, Pathwidth, and Minimum Elimination Tree Height

摘要

It is shown how the value of various parameters of graphs connected to sparse matrix factorization and other applications can be approximated using an algorithm that finds vertex separators of graphs. The approximate values of the parameters, which include minimum front size, treewidth, pathwidth, and minimum elimination tree height, are no more than O(log n) (minimum front size and treewidth) and O(squared logarithm of n) (pathwidth and minimum elimination tree height) times the optimal values. In addition, the existence of bounded approximation algorithms for the parameters are examined, and it is shown that unless P = NP, there are no absolute approximation algorithms for them.