Parameterized Complexity Theory and its Applications to Social Choice
Parameterized complexity offers a fine-grained analysis when studying computational complexity (the amount of resources required to solve a problem). It allows to classify computational problems based on how hard they are to solve with respect to some parameters. In that sense, it leads to a better understanding of what makes certain problems hard to solve. At the same time, it opens new perspectives on how to efficiently solve hard problems in real-life settings (when some parameters are small, for instance). The aim of this project is to study the theory of parameterized complexity and how it can be applied. For the applications we will mainly discuss problems arising in the study of computational social choice.
Instructors
Simon Rey: PhD candidate at the ILLC under the supervision of Ulle Endriss and Ronald de Haan, I work in the area of computational social choice, taking a computational perspective on some collective decision-making problems.
Ronald de Haan: assistant professor at the ILLC, my research interests include the application of methods from theoretical computer science—in particular methods from (parameterized) complexity theory—to problems in artificial intelligence (AI), knowledge representation & reasoning (KRR), and computational logic.
Useful resources
The following three books are nice references for parameterized complexity and will serve as official references for the content of the lectures:
- Parameterized Complexity Theory, J. Flum and M. Grohe, Springer-Verlag Berlin Heidelberg, 2006
- Parameterized Algorithms, M. Cygan et al., Springer-Verlag Berlin Heidelberg, 2015
- Fundamentals of Parameterized Complexity, R. Downey and M. R. Fellows, 2013
The following chapter offers a quick presentation of parameterized complexity in the context of computational social choice:
- Having a Hard Time? Explore Parameterized Complexity!, B. Dorn and I. Schlotter, Chapter 11 in Trends in Computational Social Choice, Editor: Ulle Endriss, 2017
Schedule
Below you will find the schedule week per week, keep in mind that time slots may vary a bit (not for the first week though).
Week 1
During the first week, we will give four lectures to give everyone the tools to understand and play with parameterized complexity
- Monday May 31, 13:00–15:00: This lecture will introduce the notion of parameterized complexity and review some techniques to design fixed-parameter tractable algorithms. This lecture is covered by the following references:
- Cygan et al. (2015): Chapters 1, 2, and 3, and Section 6.2;
- Flum and Grohe (2006): Chapters 1 and 9;
- Downey and Fellows (2013): Chapters 1, 2, 3 and 4, and Section 7.3
- Tuesday June 1, 11:00–13:00: The second lecture on tractable parameterized algorithms will focus on the treewidth and its applications. This lecture is covered by the following references:
- Cygan et al. (2015): Chapter 7;
- Flum and Grohe (2006): Chapter 11;
- Downey and Fellows (2013): Chapter 10;
- Kleinberg and Tardos, Algorithm Design (2014): Section 10.5.
- Thursday June 3, 9:00–11:00: After reviewing some positive results, we will turn to the hardness theory of parameterized complexity during the third lecture. This lecture is covered by the following references:
- Cygan et al. (2015): Chapter 13;
- Flum and Grohe (2006): Chapters 2, 3, and 7, and Section 5.1;
- Downey and Fellows (2013): Chapters 20, 21, 25 and 27.
- Friday June 4, 13:00–15:00: The last lecture, given by Ronald de Haan, will delve into lower bound techniques for kernelization. This lecture is covered by the following references:
- Cygan et al. (2015): Chapter 15;
- Downey and Fellows (2013): Chapter 30.
There will not be any homework or exercises to do between two lectures. You are however asked to review the lectures to make sure you assimilated everything and to go through the proofs to ensure you understand how to use the tools.
Week 2
The idea for the second week is to continue the lectures but this time with the students as presenters. Below you will find a list of the topics that can be discussed together with some references for them. Each topic is about a theoretical aspect of parameterized complexity that has not been discussed (or very lightly) in the lectures we gave. In the references you will typically find one book chapter that describes the theory of the concept and a paper showing applications of the technique in the context of computational social choice.
The steps that you have to complete are the following ones.
- Pair up with another student to form a team of two persons.
- Select a topic you want to work on, let's see if several teams want the same subjects.
- Once teams and topics have been arranged, prepare your presentation with your partner.
- Select a time slot for your presentation.
- Finally, give the presentation (what a surprise!).
The presentation should be around 30 minutes long, 15 extra minutes will be scheduled afterwards for questions. The format is not fixed, but, you are asked to present two things (each of them taking roughly half of the presentation): the theoretical aspect of your topic (definitions, interesting results, etc...) and an example of a nice application from the computational social choice literature. As you can see, the two parts of the presentation correspond to the two type of references we provided you with.
Below you can find a list of the topics, together with their references.
- Iterative compression techniques for FPT algorithms:
- Theoretical aspects:
- Sections 4.1 and 4.2 of Cygan et al., 2015
- Applications: Feedback Vertex Set in Tournaments, and its relation to Banks winners in elections
- Section 3.3.2 of the Handbook of Computational Social Choice, Brandt et al., 2015
- First paragraph from Feedback Vertex Sets in Tournaments, Gaspers and Mnich, 2010
- Theoretical aspects:
- Color coding technique for FPT algorithms
- Theoretical aspects:
- Sections 5.1, 5.2 and 5.6 of Cygan et al., 2015
- Application:
- Suggestion:
- Present Theorem 5 and its proof
- Theoretical aspects:
- W[t]-complete problems
- Theoretical aspects:
- Application:
- Suggestion:
- Select one W[1]-h and one W[2]-h problem, and present them (plus proof sketches)
- Backdoors
- Theoretical aspects:
- Chapter "Backdoors to Satisfaction" of The Multivariate Algorithmic Revolution and Beyond, Bodleander, Fomin and Marx, 2012
- Application:
- Suggestion:
- Focus on one FPT problem and present it plus a proof sketch (e.g., CA_{com} for parameter dist_{acyc}); the definitions of abstract argumentation with one type of semantics already takes quite a bit of time
- Theoretical aspects:
- Courcelle's theorem and Monadic Second Order Logic
- Theoretical aspects:
- Sections 7.1 and 7.4 of Cygan et al., 2015
- Application:
- Theoretical aspects:
- More kernelization techniques and examples
- Theoretical aspects:
- Chapter 2 of Cygan et al., 2015
- Application:
- Theoretical aspects:
To decide who will do which topic, we will use some kinds of algorithms supposed to generate a fair outcome. For this to work we need to know your preferences. By the third of June at 19:00, we ask you to write us an email detailing your preferences. Here is what we need: You are allocated 60 indivisible points. For each of the six topics above, indicate us how many points you give to the topic (that represents somehow your happiness for dealing with the topic). You can choose to give 0 point to a topic, but you must give non-0 score to at least 3 topics. All the points must be allocated.
The schedule for the presentations is as follows:
- Thursday June 10, 10:00–12:00: W[t]-complete problems and Courcelle's theorem;
- Friday June 11, 13:00–16:00: Kernelization, color coding and iterative compression techniques for FPT algorithms.
At the end of the last presentation on Friday, we will take a bit of time to discuss the papers you will have to submit.
Week 3
During the third week, we will have meetings with all the students to discuss their ideas and progress for their papers. Each meeting will be 30 minutes long and will be scheduled during one of the following time slot:
- Thursday June 17, 10:00–12:00;
- Friday June 18, 13:00–16:00.
Other details will be arranged later.
By the end of Tuesday the 15th, we ask you to send us an email containing the name of the persons you will be writing the paper with (if you are a team) or your own name (if you are alone) and the idea that you want to follow. We want to approve your ideas before you explore them in depth.
Week 4
Last week is dedicated to the writing up of the paper. We will not plan anything during that week but if you need anything, please contact us.
The deadline to submit the paper is by the end of this week, to be exact on the 25th at 19:00.
Recap on the deadlines
Here is a list of the deadlines for the projects:
- Thursday June 3, before 19:00: submit your preferences for the topics of the presentations (see above for how to do that) and the name of your partner;
- Tuesday June 15, before 19:00: submit the topic you want to work on for the final paper and, potentially, the name of your partner;
- Tuesday June 15, before 19:00: select a time slot for the 30 minutes meeting about the final paper;
- Friday June 25, before 19:00: submit your final paper by email.
The final paper
The final delivery for this project is a short paper that you will write on a topic of your choice. The content of the paper can be twofold. It can be a thorough analysis of an existing work that you explain in your own words. You can also choose to develop an original idea you had on the topic and present your findings. The second option might look scary but keep in mind that we do not expect you to have ground-breaking results after such a short project. Presenting the direction you followed as well as few findings is the kind of outcome we expect.
Any topic related to parameterized complexity will be ok. We do still ask you to submit your topic for approval in the middle of the third week.
You are free to write the final paper alone or as a team of two. The rules are the same, although our expectations will be higher if two persons are involved.
The paper should be typeset in LaTeX, using the IJCAI guidleines. It should look like a research article and thus should include an introduction with the motivation of the study, a (brief) review of the literature, some preliminaries explaining all the notations you will be using, the main findings and a conclusion. The paper should not exceed 6 pages including the references. Note that it is more than fine if you submit less than 6 pages, we value precision and conciseness more than anything! We strongly encourage you to read and follow the advice on writing a paper put together by Ulle Endriss.
The deadline for submitting your paper is on the 25th of June at 19:00. To submit it, email both of us with an appropriate header and the PDF file of your paper attached.
Assessment
At the end of the project, each student will receive a fail or pass grade. Two deliveries are expected for this project: the presentation and the final paper. Each of them will be graded with a fail or pass grade. The final grade of the project is the conjunction of these two grades.