KAIST Discrete Math Seminar

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.