Given a nice tree decomposition of width w of graph with n vertices, HAMILTONIAN CYCLE can be solved in time w^O(w ).n. Could anyone send me the papers related to finding Hamiltonian Cycle on nice tree decomposition in time w^O(w ) · n ?
Please find out attached two papers related to Hamiltonian cycle.
Regards
Dear Muneer,
Thank you for reply but I am asking Dynamic programming on graph G of bounded tree
width to check whether G contains Hamiltonian cycle or not.
Have a look at this lecture note. You will see how you can get such a dynamic programming algorithm running at $O(tw^(O(tw)).n^(O(1)))$. It is because in forget node, you face several branching. In 2011, Cygan et. al introduce Cut&Count approach which will convert this algorithm to an algorithm running at $O(c^(O(tw)).n^(O(1)))$ which can be found here: https://arxiv.org/pdf/1103.0534.pdf
Remember using dynamic programming approach based on tree decomposition will result in using exponential space.
A good reference for this approach can be found in this book: https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf
This book is amazing. There is chapter for tree decomposition. By reading that chapter you will get lots of ideas.
- Badges
- Science topic