Introduction to Parameterized Algorithms: Tutorial

Obtaining credit

You will get credit (zápočet) for solving homework, which you can submit via the Postal Owl or offline on paper. If you haven't received the enroll link into Owl by mail after the first tutorial session, please let me know.

To obtain the credit, you will need 66 or more points for HW. At least 100 points worth of homework will be assigned.

Tutorial content

8. 10.: Introductory exercises. Exercise sheet (PDF)

Links

Webpage of the lecture

PACE Challenge: Yearly challenge to design and implement algorithms for hard problems.

Parameterized algorithms in practice:
The course is a theoretical one. Most practical problems don't have a clean definition, plus the problem definition changes over time, making our approaches all but useless (our running times will often be tractable only in theory, too). In such places MILP (and other) solvers are used in practice. Throughout the course, we will explore nice algorithmic ideas, and try to see what makes hard problems hard.
This doesn't mean that FPT algorithms don't have their place in practice:

• Genome scaffolding is a clean NP-hard problem with a low natural parameter, leading to the Opera parameterized algorithm. Scarpa combines FPT and linear programming for the same problem.
• Several other NP-hard string problems coming from genetics have seen such parameterized solutions, see Parameterized Algorithms in Bioinformatics.
• SCIP-Jack is a fast Steiner tree solver which beats generic MILP and SAT solvers at ST (and started as a contestant at PACE 2018). Besides the FPT approach, this uses linear programming and custom heuristics.
• Other such solvers: k-terminal-cut, sparse allocation (motivated by VLSI manufacturing), FPT approximation of scheduling. Actual practicality is debatable here, as again, these problems have very clean definitions, and I haven't been able to find places where these have been deployed practically.