Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Engineering and Applications Track of the 12th Annual European Symposium on Algorithms (ESA 2004)
DOI: 10.7155/jgaa.00117
Contraction and Treewidth Lower Bounds
Vol. 10, no. 1, pp. 5-49, 2006. Regular paper.
Abstract Edge contraction is shown to be a useful mechanism to improve lower
bound heuristics for treewidth. A successful lower bound for
treewidth is the degeneracy: the maximum over all subgraphs of the
minimum degree. The degeneracy is polynomial time computable. We
introduce the notion of contraction degeneracy: the maximum over all
minors of the minimum degree. We show that the contraction
degeneracy problem is NP-complete, even for bipartite graphs, but
for fixed k, it is polynomial time decidable if a given graph G
has contraction degeneracy at least k. Heuristics for computing
the contraction degeneracy are proposed and evaluated. It is shown
that these can lead in practice to considerable improvements of the
lower bound for treewidth, but can perform arbitrarily bad on some
examples. A study is also made for the combination of contraction
with Lucena's lower bound based on Maximum Cardinality
Search []. Finally, heuristics for the treewidth are
proposed and evaluated that combine contraction with a treewidth
lower bound technique by Clautiaux et al. [].
|
Journal Supporters
|