Contraction and Treewidth Lower Bounds - Bodlaender, Hans; Wolle, Thomas; Koster, Arie (Journal of Graph Algorithms and Applications, 2006)
Edge contraction is shown to be a useful mechanism to improve lowerbound heuristics for treewidth. A successful lower bound fortreewidth is the degeneracy: the maximum over all subgraphs of theminimum degree. The degeneracy is polynomial time computable. Weintroduce the notion of contraction degeneracy: the maximum over allminors of the minimum degree. We show that the contractiondegeneracy problem is NP-complete, even for bipartite graphs, butfor fixed k, it is polynomial time decidable if a given graph Ghas contraction degeneracy at least k. Heuristics for computingthe contraction degeneracy are proposed and evaluated. It is shownthat these can lead in practice to considerable improvements of thelower bound for treewidth, but can perform arbitrarily bad on someexamples. A study is also made for the combination of contractionwith Lucena's lower bound based on Maximum CardinalitySearch []. Finally, heuristics for the treewidth areproposed and evaluated that combine contraction with a treewidthlower bound technique by Clautiaux et al. []. <!---->