| Course Code: CS5084 Course Name: Parameterized algorithms Prerequisites: None Syllabus: Introduction to Parameterized Algorithms, Kernelization: Formal definitions; kernels for vertex cover, edge clique cover; crown decomposition: vertex cover, maximum satisfiability; expansion lemma; kernels based on Linear programming; sunflower lemma: d-hitting set. Bounded Search trees: illustration of technique; vertex cover; feedback vertex set; vertex cover above LP; closest string. Iterative compression: illustration of technique; feedback vertex set in tournaments; feedback vertex set (FVS); odd cycle transversal. Randomization methods in parameterized algorithms: randomized algorithm for FVS; color coding technique: longest path; random separation; chromatic coding. Tree-width: Formal definition of path-width, path-decomposition, tree-width, tree-decomposition; dynamic programming on graphs of bounded tree-width; weighted independent set; dominating set; graph coloring. Advanced Kernelization algorithms: connected vertex cover on planar graphs; a quadratic kernel for FVS. Parameterized Intractability: Formal definition of parameterized reductions; examples of parameterized reductions; W-hierarchy. Lower bounds based on ETH and Kernelization: ETH: motivation and basic results; consequences of ETH for parameterized complexity. Texts: 1. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh. Parameterized Algorithms, Springer-Verlag, 2015. 2. Daniel Lokshtanov, Meirav Zehavi, Saket Saurabh, Fedor V. Fomin. Kernelization: Theory of Parameterized Preprocessing, Cambridge University Press, 2019 References: 1. R.G. Downey, M. R. Fellows: Parameterized Complexity Springer-Verlag, 1999. 2. Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C., Introduction to Algorithms, MIT Press, 2009. 3. Kleinberg, J. and Tardos, E., Algorithm Design, Addison Wesley, 2006. |