2ima00

Note that the first meeting for this course is on Tuesday 19th April 15:45 - 17:30 (MF15). Please register on OASE before the first meeting.

- Mark de Berg (MF 4.146, m.t.d.berg@tue.nl)
- Bart Jansen (MF 4.104A, b.m.p.jansen@tue.nl)

In this course we study a topic that is on the cutting edge of algorithms research. We will study recent literature on the topic through lectures, given by the students, and by solving problems.

Topics studied in this course vary and usually lie close to the algorithms group's research interests and to (some of) the topics of graduation projects that can be realized within the algorithms group. The focus for this year is on parameterized complexity. This branch of algorithm design aims to deal with NP-complete problems by providing exact algorithms whose running time consists of two parts: a polynomial term in the total size of the input, and a term that is exponential in a complexity parameter k that is assumed to be small in practically relevant inputs. A classic result in the field is that we can test whether an n-vertex graph has a vertex cover of size k in time O(2^k * n). Hence a small solution can provably be found efficiently in a large graph, even though vertex cover is an NP-complete problem. We will study several techniques for designing such fixed-parameter tractable (FPT) algorithms. In addition, we study proof techniques to show that certain problems are unlikely to admit FPT algorithms.

We will use the following literature:

- Parameterized Algorithms by Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk and Saket Saurabh. You can download a PDF version of the book from Springer's website when logged into the university network or VPN.

Instead of doing homework exercises to reinforce the theory, we will participate in Track B of the PACE Implementation challenge for parameterized algorithms. Groups of students develop and implement an algorithm to solve the Feedback Vertex Set problem based on the techniques that are covered in the lectures.

You can take this course if you have completed at least one of the courses Advanced Algorithms (2IL45), Geometric Algorithms (2IL55), Algorithms for massive data (2IL75) or Algorithms for geographic data (2IL76) successfully. However, if your study plan allows it, it is better to complete at least two of these courses before taking 2IMA00.

If you have not completed any of the aforementioned courses, but you have completed other Master's courses that are highly relevant to the topic of the seminar, then please contact the instructors to discuss if you can be admitted to the course.

The course involves literature search, lectures by students based on material provided by the instructors, and an extensive programming & algorithm engineering assignment. Grading will be based on the quality of the student lectures, on the quality of the developed program, and on the quality of a final report about the implementation project written by each group. There is no final exam.

Your final grade is computed as (L + P) / 2, rounded up to the nearest integer, where:

- L is the grade for your student lecture with a resolution of half-points. It is based on your performance during the presentation and on the thoroughness with which you prepared the lecture, as expressed through the quality of your slides and your understanding of the material.
- P is the grade for the final report of your group's implementation project, with a resolution of half-points. The grade evaluates both the efficiency of the software you developed, as the writing quality of the report.

The kick-off meeting and introductory lecture of the course is on Tuesday 19th April 15:45 - 17:30 in Metaforum 15.

After that we will, in principle, meet two times per week. **Attendance at all meetings is required.** In particular, any student who is absent at the kick-off meeting without prior notice, is assumed not to be taking the course. Afterwards we we will meet two times per week, with some exceptions.

- Tuesday hours 7+8 (15:45-17:30), MF 15
- Thursday hours 3+4 (10:45-12:30), MF 13

Please note that the detailed schedule below is tentative and may be adapted during the course.

Week nr. | Day | Date | Time | Place | Topic | Material |
---|---|---|---|---|---|---|

1 | Tue | 19-Apr | 15:45-17:30 | MF15 | Kick-off | slides |

1 | Thu | 21-Apr | 10:45-12:30 | MF13 | No meeting | |

2 | Tue | 26-Apr | 15:45-17:30 | MF15 | Literature study | |

2 | Thu | 28-Apr | 10:45-12:30 | MF13 | Orientation on implementation challenge | |

3 | Tue | 03-May | 15:45-17:30 | MF15 | Student lecture 1 (Bart) | |

3 | Thu | 05-May | 10:45-12:30 | MF13 | No meeting | |

4 | Tue | 10-May | 15:45-17:30 | MF15 | Student lecture 2 (Huib) | |

4 | Thu | 12-May | 10:45-12:30 | MF13 | Brainstorm | |

5 | Tue | 17-May | 15:45-17:30 | MF15 | Student lecture 3 (Henk) | |

5 | Thu | 19-May | 10:45-12:30 | MF13 | Student lecture 4 (Stefan) | |

6 | Tue | 24-May | 15:45-17:30 | MF15 | Student lecture 5 (Leo) | |

6 | Thu | 26-May | 10:45-12:30 | MF13 | Brainstorm | |

7 | Tue | 31-May | 15:45-17:30 | MF15 | No meeting | |

7 | Thu | 02-Jun | 10:45-12:30 | MF13 | No meeting | |

8 | Tue | 07-Jun | 15:45-17:30 | MF15 | Student lecture 6 (Xi) | |

8 | Thu | 09-Jun | 10:45-12:30 | MF13 | Student lecture 7 (Chris) | |

9 | Tue | 14-Jun | 15:45-17:30 | MF15 | Student lecture 8 | |

9 | Thu | 16-Jun | 10:45-12:30 | MF13 | Student lecture 9 | |

9 | Thu | 16-Jun | Afternoon | ?? | Competition round-up | |

10 | Tue | 21-Jun | 15:45-17:30 | No meeting | ||

10 | Thu | 23-Jun | 10:45-12:30 | No meeting | ||

11 | Tue | 28-Jun | 15:45-17:30 | No meeting | ||

11 | Thu | 30-Jun | 10:45-12:30 | No meeting |

One of the goals of the seminar is to expose students to research papers and the give insight into the inner workings of the publication process in academia. For this purpose, and to familiarize ourselves with the topic of parameterized algorithms, everyone is assigned a topic for literature study in the first meeting on Tuesday the 19th of April. The possible topics are:

- Phylogeny (constructing evolutionary trees that explain how species evolved based on biological data)
- Computational geometry (the parameterized analysis of NP-hard problems in computational geometry)
- Computational social choice (voting and ranking problems)
- Network design (Steiner tree, Maximum Leaf Spanning Tree, etc.)
- Route planning (the (Subset) Traveling Salesman problem, the Disjoint Paths problem, etc.)
- Clustering (cluster editing, (p,q)-clustering, etc.)
- Sequence alignment problems in biology (closest string, common substring, etc.)
- Graph modification problems (the study of how much edits are needed to ensure an input graph has a certain property)
- Problems in logic (the fixed-parameter tractability analysis of questions related to Satisfiability or similar problems originating in logic such as Constraint Satisfaction)
- Implementation and experiments with parameterized algorithms (try keyword: ``algorithm engineering'')
- The Feedback vertex set problem
- The Vertex Cover problem
- The Longest Path (or k-Path) problem
- Scheduling problems (graph coloring, scheduling tasks on machines, etc.)

The assignment is as follows. Search for research papers **in the field of parameterized algorithms** that deal with your topic. (Hint: you can also try keywords fixed-parameter tractability, parameterized complexity, multivariate algorithmics.) This can be done using Google (Scholar), the university library, or other tools that will be discussed in the opening lecture. Make a list of relevant papers and select 3 of them that are interesting to discuss with the rest of the class; for example, pick three papers on the same problem that contain improvements to each other; or pick three that deal with different problems and show the breadth of work on the topic; or pick two with theory and one with experiments. You are free to pick in any way you like, but make a conscious choice that leads to a nice story that you can tell your classmates. Try to read as much of these three papers as you can understand in the time that is available - it may be that this is only the abstract, introduction and conclusion. Then make some notes so that you can talk for roughly 10 minutes about the papers you chose, describing why you chose them, what they are about, and how they relate to each other. This is all done in an informal setting - no Powerpoint slides, but just make some notes on paper so we can have an informed discussion.

The general goal of the lectures is to transfer algorithmic ideas to your fellow students. Every lecture has a clearly defined theme. I will indicate on which material from the literature the lecture should be based, and which results have to be covered. Each lecture should be 45 minutes. It is your responsibility to ensure your lecture lasts roughly 45 minutes. 3 minutes more or less is acceptable, but deviating more than that will affect your grade. To this end, it may be useful to have a topic near the end of your lecture that you can skip if you are running out of time (or to cover if you have extra time). For some topics there is some freedom in choosing what to cover, because the literature has too much material for 45 minutes. Use your own best judgement to select material that supports the message of your lecture and transfers the maximum number of interesting algorithmic insights to your fellow students. If there are proofs in the book that are not very relevant to the big picture (for example, that a certain subproblem is polynomial-time solvable, while the crucial point is formed by an insight about an exponential-time procedure), then such proofs can be skipped if needed. However, your lecture should have technical depth and convince your fellow students of the correctness of the approach. The main part of your lecture should be based on PowerPoint / LaTeX beamer slides. However, since proofs are more easy to follow when presented on the whiteboard, your lecture has to contain at least 10 minutes of presenting a proof on the whiteboard.

Do not underestimate the importance of having insightful figures to illustrate the material you are presenting. While figures take a long time to prepare, they are very useful for the audience to understand what is going on.

For more advice, please check out Herman Haverkort's page on how to give a typical talk or lecture in an algorithms seminar.

If you have no idea how to transfer the core algorithmic ideas in a didactically sound way, you could try to use Google to find lectures on related topics for some inspiration. However, since the material is best absorbed by creating all slides yourself, you are not allowed to copy slides from other sources. You are allowed to use up to a handful of images from other sources, if it would be very time-consuming to produce them yourself. In these cases, always give credit to the sources of the imagery.

The grade for your presentation will determine 50% of the grade for this course. We grade two aspects of the presentation: 50% of the grade for the presentation is determined by your preparation and how well you understand the material. The remaining 50% is determined by how well the material is presented.

The assignment of lectures to students is:

Lecture number | Topic | Source material | Lecturer |
---|---|---|---|

1 | More kernelization algorithms | Cygan et al. Chapter 2, not 2.5 | |

2 | Iterative compression | Cygan et al. Chapter 4, not 4.3.2 | Huib |

3 | Treewidth | Cygan et al. 7.1-7.3.1 | Henk |

4 | Randomized algorithms | Cygan et al. Chapter 5, not 5.4&5.6 | Stefan |

5 | Advanced kernelization algorithms | Cygan et al. Section 9.1 | Leo |

6 | Improving dynamic programming on tree decompositions | Cygan et al. Chapter 11 | Xi |

7 | W[1]-hardness | Cygan et al. Chapter 13 | Chris |

8 | Using linear programming in parameterized algorithms | Cygan et al. 2.5 & 3.4 | ? |

9 | Important separators | Cygan et al. 8.1-8.3 | ? |

The literature linked to below can be accessed when logged into the TU/e network, either through VPN or by physically being present at TU/e.

**Kernels: Chris & Leo.**

The following paper gives a kernel that is not as small, but is easier to compute, than the one given in the book. In particular, read Section 4 of this paper:

Instead of requiring an algorithm to find maximum matchings, it just needs an approximation algorithm for (weighted) feedback vertex set. It was developed independently by 2 sets of authors. Pick the one you find the easiest to read:

Option 1:

Option 2:

**Treewidth: Henk & Xi.**

There are 2 approaches for solving the problem when you have a tree decomposition. The first one has a running time of 3^k * poly(n), harder to understand, but may be easier to implement:

Cygan et al.: Solving connectivity problems parameterized by treewidth in single exponential time

The next approach has a worse factor f(k), but a better polynomial term (linear), and is conceptually simpler:

Ton Kloks, C.M. Lee, Jiping Liu. New Algorithms for k-Face Cover, k-Feedback Vertex Set, and k-Disjoint Cycles on Plane and Planar Graphs (page 8 and further)

I don't know which of the 2 approaches will be faster on the inputs we have; one has a worse polynomial term, the other has a worse factor f(k). I don't think it is feasible to implement both, given the time. Pick one of the two and go for it. To **find** a tree decomposition, you can use one of the heuristics described in this paper:

Within the framework of iterative compression and you have *some* feedback vertex set X in your graph G, you can also make a tree decomposition by making a tree decomposition for the forest G - X (which is easy) and then adding all vertices of X to all bags. Afterwards, you can try to make it better by removing vertices from X from bags when the tree decomposition remains valid after removing a vertex from a bag.

**Parameterized by solution size (iterative compression & randomized): Huib & Stefan.**

For the iterative compression algorithm, I think the book gives sufficient details to build an implementation from. There is a theoretically faster algorithm, which is linked below. You could read it for inspiration, but it's not necessary and I do not think it is feasible to implement it fully because it needs a subroutine with matroid computations.

For the randomized algorithm, I don't know of any additional literature. You could search by yourself.

2ima00.txt · Last modified: 2016/05/26 12:27 by bmpjansen