Parameterized Algorithms and Lower Bounds (매개변수 고정 알고리즘과 하한)

CS700 and MAS583

Spring Semester 2017

Course summary

Deciding whether a graph on \(n\) vertices has a clique of size \(k\) is NP-hard. When \(k = 1000\), on the other hand, there clearly is a polynomial-time algorithm: Just test all 1000-tuples of vertices. But this takes time \(\Theta(n^{1000})\), and is clearly completely useless in practice!

Can the problem be solved in practice for small values of \(k\)? After all, it's not NP-hard for fixed \(k\). Can we find an algorithm whose running time depends not on \(n^{k}\), but is of the form \(f(k) n^{c}\), for a fixed constant \(c\) (that does not depend on \(n\)).

This question belongs to the area of parameterized algorithms. We consider NP-hard problems and look for algorithms that can solve them efficiently as long as some parameter of the problem instance is small.

We will study some techniques to develop parameterized algorithms:

  • Kernelization,
  • Bounded search trees
  • Randomized methods

We will meet many problems that have efficient parameterized algorithms, but for the clique problem above, no such algorithm has been found—and in fact we have evidence that none exists.

What kind of evidence would this be? Ideally, we would like to prove a lower bound on the complexity of a problem. But this is generally very hard, and most students never meet any lower bound in their studies except for the \(\Omega(n \log n)\) lower bound for comparison-based sorting.

We will generalize the sorting lower bound and prove \(\Omega(n \log n)\) lower bounds for a few interesting problems. Then we look at some recent approaches for arguing about lower bounds when one cannot prove such a bound. In particular, we will study lower bounds based on several assumptions:

  • 3SUM-hardness,
  • the strong exponential time hypothesis (SETH),
  • the unique games conjecture

Prerequisites: An algorithm course (CS300 or CS500 or equivalent), and some basic familiarity with NP-hardness. This course does not require any programming skills.

Course information

Lecturer:
Helmut Alt (Office: E3-1 1424, Phone: 3591) and Otfried Cheong (Office: E3-1 3434, Phone: 3542).
Lectures

The class meets Wednesday from 16:00 to 17:15 and Fridays from 10:30 to 11:45 in room 3445 in the EECS building (E3-1). Lectures are given in English.

Grading policy

The grade will be composed as follows (small changes reserved): Participation (20%), Homework (40%), Exam (40%).

Exams

We will have a final exam on Wednesday, June 14, from 16:00 to 19:00, in classroom #1 (room 1101) in building E3-1 (not our usual classroom).

Piazza

This term we will be using Piazza for class announcements, discussion, and asking questions.

Here is our Piazza class page.

You are responsible for checking the announcements on our Piazza class page regularly (if you make a Piazza account and enroll for the course, announcements will be mailed to you automatically.)

If you do not understand something, it is important that you ask questions. Piazza allows you to ask questions and get answers from the instructor, the teaching assistants, and your classmates. You can ask questions anonymously, so don't be shy and ask!

To ask questions, you need to register on Piazza and enroll as a student for CS700/MAS583. To do so, go to the enrollment page. Select "Join as student". You will then need to use your KAIST email address (ending with @kaist.ac.kr) to create an account.

Literature

Most of the material taught in this course stems from the last decade, so we will have to use some original papers as reference.

We will make use of the book Parameterized Algorithms, by Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. It is available on-line through the KAIST library.

We will also use lecture notes by Jeff Erickson. The originals are on his webpage (or on older versions of this page).

We will use slides made by Karl Bringmann and Sebastian Krinninger for their class.

The last topic of the course uses material from Introduction to the Theory of Computation, Michael Sipser, Second International Edition, Course Technology 2006. Check out its errata page, which contains a few substantive (as opposed to stylistic) errors.

The course will be taught on the blackboard, so do not expect slides or other such lecture materials. If you miss a class, you'll have to ask a friend for their notes.

Course progress

The material covered in the lectures so far:

03-03 Introduction Chapter 1
03-08 Formal definitions of FPT and XP, Introduction to Kernelization Sections 1.1, 2.1, 2.2.1
03-10 Simple kernels Sections 2.2.2, 2.2.3
03-15 Crown decomposition Section 2.3
03-17 Kernels based on linear programming Section 2.5
03-22 Vertex cover search tree Section 3.1
03-24 Solving recursions, Feedback Vertex Set Section 3.2, 3.3
03-29 Vertex Cover above LP Section 3.4
03-31 VC above Matching, Variable-Deletion-Almost-2-SAT, Closest String Section 3.5
04-05 Lower bounds, decision trees, linear decision trees decision tree notes, Section 7.1 and 7.2 in notes
04-07 Algebraic decision trees Section 7.3 in the notes
04-12 Diameter, Maxgap, 3SUM-Hardness 3SUM notes
04-14 3SUM
Midterm week (no class, no exam)
04-26 Parameterized reductions Section 13.1
04-28 Problems at least as hard as Clique Section 13.2
05-03 Holiday
05-05 Holiday
05-10 The W-hierarchy Sections 13.3, 13.5
05-12 ETH and SETH, SETH implies ETH Sections 14.1, 14.2
05-17 ETH bounds for FPT problems Section 14.3
05-19 ETH bound for CLIQUE, Orthogonal vectors hypothesis Section 14.4, slides (from here)
05-24 SETH implies OVH, lower bound for LCS slides (from here)
05-26 Cubic-time equivalence to APSP slides (from here)
05-31 3SUM revisited slides (from here)
06-02 Lower bounds for decidability of arithmetic Sipser
06-07 Lower bounds for decidability of arithmetic Sipser
06-09 Lower bounds for decidability of arithmetic Sipser
Final exam on Wednesday, June 14, 16:00~19:00 in classroom 1 (1101)

Homework

There will be several homework assignments in this course. Homeworks must be turned in in English, and must be submitted on paper at the beginning of the lecture in the classroom.