Algorithms on Tree Decompositions and Time Improvements

Hans L. Bodlaender

Institute of Information and Computing Sciences, Utrecht University, The Netherlands

Institute of Information and Computing Sciences, Utrecht University, The Netherlands

2011/10/31 Mon 4PM-5PM

Many problems that are intractable on general graphs become linear time solvable on graphs of bounded treewidth. The constant factor however of such algorithms is exponential or worse in the treewidth of the tree decomposition that is used. In this talk, a number of known and some new results are surveyed. In particular, it is shown how speed improvements can be obtained using convolutions, and how a recent technique called “cut-and-count” can be used to obtain fast probabilistic algorithms for problems like Hamiltonian Circuit.