Seminar on Tractability

Algorithms and machine learning
Advanced studies
Year Semester Date Period Language In charge
2015 autumn 02.09-09.12. 1-2 English Johannes Wallner


Time Room Lecturer Date
Wed 10-12 C220 Johannes Wallner 02.09.2015-14.10.2015
Wed 10-12 C220 Johannes Wallner 28.10.2015-09.12.2015



Many important problems in computer science are proven to be "intractable", that is, hard to solve computationally. Many areas ranging, for instance, from machine learning, Boolean satisfiability (SAT) checking, and theorem proving to software verification, have nevertheless found methods and tools to tackle such involved problems in an efficient manner. 

The aim of this seminar is to give an overview over fundamental concepts and state-of-the-art techniques to tame intractability. Possible topics include the study of graphical structure of the underlying problem, language restrictions, approximation algorithms, and kernelization methods, as well as utilizing heuristics in modern SAT-solvers. 

The seminar is intended for MSc students especially in the Algorithms, Data Analytics, and Machine Learning (ALKO) subprogramme, and also PhD students. A certain level of theoretical/mathematical maturity is expected from the participants.

Teachers: Matti Järvisalo and Johannes Wallner


  • Introductory lecture and selection of seminar topics: Wednesday September 9, 10-12
  • Weekly seminar meetings during study period II (two presentations per week)
  • Date

    topic presenter opponent
    October 28


    Chapter 1





    November 4

    Chapter 2

    Chapter 3





    November 11

    Chapter 4

    Chapter 7





    November 18


    Chapter 8





    November 25

    Chapter 10

    Chapter 12





    December 2









  • Final deadline for seminar reports: December 9

Completing the course

The course work consists of

  • giving a 40 min presentation,
  • writing a 10-15 page report, and
  • acting as an opponent and giving feedback to another student

on a selected topic based on a scientific article from the seminar textbook. You may also propose your own topic based on a recently published research article that falls within the topic of the seminar. In this case, please email the teacher with more details on the topic you are interested in.

Latex Template

The report should be formatted according to the general format (cover etc.) used on the Scientific Writing course, example layout

Using LaTeX is recommended. LaTeX-templates are available from (See "Tools to work with").

Literature and material

The individual topics for each student are chosen from chapters in the book

Tractability: Practical Approaches to Hard Problems, Cambridge University Press 2014.

The invidual chapters of the book can be accessed eletronically within the domain via the link above; there is no need to purchase the book.

Table of contents:

Part I. Graphical Structure:
1. Treewidth and hypertree width [reserved / Paavilainen]
2. Perfect graphs and graphical modeling [reserved / Efremov]

Part II. Language Restrictions:
3. Submodular function maximization [reserved / Berg]
4. Tractable valued constraints [reserved / Niskanen]
5. Tractable knowledge representation formalisms

Part III. Algorithms and their Analysis:
6. Tree-reweighted message passing
7. Tractable optimization in machine learning [reserved / Tuomainen]
8. Approximation algorithms [reserved / Rantanen]
9. Kernelization methods for fixed-parameter tractability

Part IV. Tractability in Some Specific Areas:
10. Efficient submodular function minimization for computer vision [reserved / Chinnasamy]
11. Towards practical graph-based, iteratively decoded channel codes: insights through absorbing sets

Part V. Heuristics:
12. SAT solvers [reserved / Wallenius]
13. Tractability and modern satisfiability modulo theories solvers [reserved / Laurinharju]


Further topics:

[BergmanCvHN] D. Bergman, A. A. Cire, W.-J. van Hoeve, and J. N. Hooker. Discrete Optimization with Decision Diagrams. INFORMS Journal on Computing, to appear. [reserved / Saikko]

: A deterministic (2-2/(k+1))n algorithm for k-SAT based on local search.  Theoretical Computer Science 289(1):69-83 ([reserved / Huttunen]