Markov models on graphs represent a model class widely applied in many areas of computer science, such as computer networks, data security, robotics, pattern recognition and computer vision. The first part of the course covers inference and learning for Markov models on chains and trees. Almost all these tasks including structure learning can be solved by efficient algorithms with polynomial time complexity. The second part of the course addresses graphical models on general graphs. Here on the contrary, practically all inference and learning tasks are NP-complete. The focus is therefore on efficient approximation algorithms.