Parameterized Algorithms (CS6190)
An Introductory Note and Overview of the Topics Covered
This course will focus on some of the recent research in the field of Parameterized Complexity. Since many of you may not know the basic tools and techniques used in designing parameterized algorithms and in proving their non-existence, we will also cover some of the basic topics that are necessary to understand the more advanced topics of the course. In the following I give a very brief introduction to Parameterized Complexity and after that I list some of the topics that I plan to cover. (Other practical information regarding the course can be found at the end.)
Parameterized Complexity: You may recall from your Algorithms 101 course that certain difficult (NP-hard) problems like Independent Set and Dominating Set can be solved very fast (in linear time, for instance) on special graph like trees, whereas these problems are notoriously hard on general graphs. The above suggests that input size does not completely govern the inherent challenges involved in solving these problems; certain structurally useful features of the input/output may dramatically simplify the job for us. Parameterized Complexity is precisely the study of how a secondary measure, called as the parameter , affects the complexity of the problem. These secondary measures capture certain properties of the input/output (or their combination). Some of the central objectives in this field are the following:
Next I give a brief summary of the topics that we covered in this course.
Relevant References for Lectures
For the basics of Parameterized Complexity we will be using the book, Parameterized Algorithms, by Cygan et al. The relevant chapter/section numbers are from the above book, unless another reference is stated explicitly.
Practical Information
Timings: Monday 12:00-12:50, Wednesday 17:00-17:50, Thursday 10:00-10:50, and Friday 09:00-09:50.
Evaluation (tentative): The students crediting this course will be required to give two presentations, one for 20 mins (25% in the evaluation) and another one for 45 mins (40% in the evaluation). The shorter presentation will be on topics which can be found on books and/or repositories, and the longer presentation will be based on research articles. Students are expected to understand the topics/articles assigned to them thoroughly, to be able to present them clearly (with mathematical correctness), and answers questions related to them. I will provide a list of topics/articles for the presentations and the students are required to give their preferences over them. The allotment of topics/articles will be based on first come, first (available) assignment policy.
Apart from the above there will be a few home-works/reading exercises during the course and scribing responsibility for (at most) one topic that is covered in the course. This above part will contribute 20% in the evaluation.
It is highly encouraged that attendees ask questions in order to understand the contents of this course clearly. To further promote this, the above shall contribute 15% in the evaluation. I do understand that online participation may get difficult due to internet related issues, thus we will additionally maintain an informal group where participants can discuss about the contents of the course and seek each others help in understanding the topics.
This course will focus on some of the recent research in the field of Parameterized Complexity. Since many of you may not know the basic tools and techniques used in designing parameterized algorithms and in proving their non-existence, we will also cover some of the basic topics that are necessary to understand the more advanced topics of the course. In the following I give a very brief introduction to Parameterized Complexity and after that I list some of the topics that I plan to cover. (Other practical information regarding the course can be found at the end.)
Parameterized Complexity: You may recall from your Algorithms 101 course that certain difficult (NP-hard) problems like Independent Set and Dominating Set can be solved very fast (in linear time, for instance) on special graph like trees, whereas these problems are notoriously hard on general graphs. The above suggests that input size does not completely govern the inherent challenges involved in solving these problems; certain structurally useful features of the input/output may dramatically simplify the job for us. Parameterized Complexity is precisely the study of how a secondary measure, called as the parameter , affects the complexity of the problem. These secondary measures capture certain properties of the input/output (or their combination). Some of the central objectives in this field are the following:
- Design efficient algorithms for the problems, where we are allowed to be slow in the parameter but we need to be very fast with respect to the input size.
- Preprocess the input to reduce its size drastically (eliminate the dependence on the input size completely).
- Rule out existence of (faster) parameterized algorithms.
Next I give a brief summary of the topics that we covered in this course.
- Branching
- Very Basic Kernelization algorithms
- Iterative Compression
- Randomized Techniques
- Derandomization Tools
- Parameterized reductions and fixed-parameter intractability
- W-hierarchy
- Exponential Time Hypothesis and its application in obtaining FPT lower bounds
- Strong Exponential Time Hypothesis and its application on refuting certain FPT and XP algorithms.
- Faster exact algorithms using their FPT counterparts
- Introduction to tree decomposition and examples of FPT algorithms parameterized by treewidth.
- Basics of matroids and its applications in obtaining FPT algorithms.
Relevant References for Lectures
For the basics of Parameterized Complexity we will be using the book, Parameterized Algorithms, by Cygan et al. The relevant chapter/section numbers are from the above book, unless another reference is stated explicitly.
- Lecture 1: Section 2.2.1, Chapter 2.
- Lecture 2: Chapter 1, and Section 3.1 and 3.2 of Chapter 3.
- Lecture 3: Chapter 1.
- Lecture 4: Section 3.5, Chapter 3, and Section 2.1, Chapter 2. For self-reducibility property see, for example, link 1 or link 2.
- Lecture 5: An introduction to the Crown Decomposition (see Section 2.3, Chapter 2). Discussions and (failed) attempts to prove Konig's Theorem. In such an attempt, we got close to the statement of Hall's Theorem.
- Lecture 6: Proof of Konig's Theorem (see the constructive proof in the link). Statements of Hall's Theorem and Konig's Theorem can be found in Section 2.3, Chapter 2.
- Lecture 7: Crown Decomposition Lemma and its constructive proof, see Section 2.3. An application of Crown Decomposition in obtaining a linear vertex kernel for Vertex Cover, see Section 2.3.1. An introduction to the problem Maximum Satisfiability, see Section 2.3.2.
- Lecture 8: An application of Crown Decomposition in obtaining a polynomial kernel for Maximum Satisfiability, see Section 2.3.2. Understanding a q-star, a q-expansion, an introduction of a generalization of Hall's Theorem (and part of its proof), see Section 4.
- Lecture 9: Generalization of Hall's Theorem and its proof using (constructive proof of) Hall's Theorem. Expansion Lemma and its (constructive) proof. See Lemma 2.17 and 2.18, Section 2.4.
- Lecture 10: Introduction to Cluster Vertex Deletion, equivalent characterisations of cluster graphs, some easy reduction rules towards obtaining a kernel for the problem (param. by the solution size), see Section 2.6, Chapter 2.
- Lecture 11: (Contd.) Application of Expansion Lemma in obtaining a kernel for Cluster Vertex Deletion, see the book "Kernelization" of Fomin et al., Section 5.2, Chapter 5. An introduction to sunflowers, and understanding the statement of Sunflower Lemma (also called Erdos-Rado Theorem), see Section 2.6, Chapter 2.
- Lecture 12: Sunflower Lemma and its application in obtaining a polynomial kernel for d-Hitting Set, see Section 2.6 and Section 2.6.1, Chapter 2.
- Lecture 13: An introduction to the technique of iterative compression, and then to understand this technique, we looked a simple application of it in designing an FPT algorithm for Vertex Cover using the compressions and the disjoint versions of the problem. After this we defined the problem Feedback Vertex Set in Tournaments and showed how it is enough to solve the disjoint version of the problem. See Section 4.1 and 4.2 of the book.
- Lecture 14: FPT Algorithm for Feedback Vertex Set in Tournaments using iterative compression (see Section 4.2).
- Lecture 15: FPT Algorithm for Feedback Vertex Set in Tournaments using iterative compression, contd. (see Section 4.2). We defined the problem Odd Cycle Transversal, introduced an annotated version of the problem (in bipartite graphs), towards designing an FPT algorithm for the problem in the disjoint version of the problem (see Section 4.4).
- Lecture 16: Polynomial time algorithm for annotated version (also called Annotated Bipartite Coloring) of Odd Cycle Transversal in bipartite graphs (see Section 4.4).
- Lecture 17: We continued with the remainder of proof from the last lecture. After this, we had a brief introduction to randomized FPT algorithms (see Chapter 5), and then we designed a randomized FPT algorithm for Feedback Vertex Set (see Section 5.1).
- Lecture 18-22: Randomized methods in designing FPT algorithms, see Section 5.1-5.3.
- Lecture 23-25: Derandomization Techniques, see Section 5.6.
- Lecture 26: Introduction to fixed-parameter intractability, see Chapter 13, Section 13.1.
- Lecture 27-32: Parameterized reduction and W[t]-hardness of problems, see Section 13.1-13.3.
- Lecture 33: Weighted Circuit Satisfiability and the W-hierarchy, see Section 13.3.
- Lecture 34: Tree decomposition, see Section 7.1 and 7.2.
- Lecture 35: Obtaining FPT algorithms parameterized by treewidth, see Section 7.3.
- Lecture 36: Introduction to matroids, see Section 12.1.
- Lecture 37: Applications of matroids and representative sets in obtaining FPT algorithms, see Section 12.3.
- Lecture 38: Designing better exact-algorithms using their FPT counterparts. For references, see the paper, Exact Algorithms via Monotone Local Search by Fomin et al.
- Lecture 39: Designing better exact-algorithms using their FPT counterparts continued.
- Lecture 40-42: Exponential Time Hypothesis and its application in showing algorithmic lower bound results, see Section 14.1-14.3
- Lecture 43-44: Application of ETH in refuting algorithms for W[1]-hard problems, see Section 14.4.
- Lecture 45: We looked at Strong Exponential Time Hypothesis and its application in obtaining algorithmic lower bound result, see Section 14.5 and 14.5.1.
Practical Information
Timings: Monday 12:00-12:50, Wednesday 17:00-17:50, Thursday 10:00-10:50, and Friday 09:00-09:50.
Evaluation (tentative): The students crediting this course will be required to give two presentations, one for 20 mins (25% in the evaluation) and another one for 45 mins (40% in the evaluation). The shorter presentation will be on topics which can be found on books and/or repositories, and the longer presentation will be based on research articles. Students are expected to understand the topics/articles assigned to them thoroughly, to be able to present them clearly (with mathematical correctness), and answers questions related to them. I will provide a list of topics/articles for the presentations and the students are required to give their preferences over them. The allotment of topics/articles will be based on first come, first (available) assignment policy.
Apart from the above there will be a few home-works/reading exercises during the course and scribing responsibility for (at most) one topic that is covered in the course. This above part will contribute 20% in the evaluation.
It is highly encouraged that attendees ask questions in order to understand the contents of this course clearly. To further promote this, the above shall contribute 15% in the evaluation. I do understand that online participation may get difficult due to internet related issues, thus we will additionally maintain an informal group where participants can discuss about the contents of the course and seek each others help in understanding the topics.