Embed Size (px)
Citation preview
www.cs.ui.ac.idFASILKOM UI_Official
@FASILKOM_UI
@fasilkomuiofficial
fakultas ilmu komputer UI
Registration:bit.ly/shortcoursePC
Session 1: Monday - Thursday, 6 - 9 May 2019Session 2: Monday – Thursday, 13 - 16 May 2019
1.00 – 3.00 PM
R. A206 & R. A209Faculty of Computer Science (New Building)UI Campus, Depok
(Technische Universität Dresden, funded by EU Erasmus+ Programme)
Speaker:
PARAMETERIZED Short Course
COMPLEXITY
Dr. Johannes Fichte
UNIVERSITASINDONESIA
FAculty of
computerscience
Abstract:Many fundamental problems in the area of graph theory, logic, knowledge representation and reasoning, as well as arti�cial intelligence in gen-eral are known to be NP-hard. Hence, under standard complexity theoretical assumptions, it is quite unlikely that e�cient algorithms exist for these problems on arbitrary input instances. However, problem instances that originate in practical applications are often structured in a way that facilitates obtaining a solution relatively fast. Such instances seem to be harder in theory than they are in practice (SAT solving). In particu-lar, since classical complexity theory mainly considers worst-case bounds as a function of the size of the input instance. In order to avoid a one-dimensional view on the computational complexity of a problem and to take structural properties of problem instances in form of a parameter into account, Downey and Fellows [2] introduced in a series of papers the theory of parameterized complexity.
Parameterized complexity o�ers a framework for a more detailed theoretical analysis that can be closer to the practical hardness of problems. In particular, it seeks for a better understanding of NP-hard problems. Since there are many ways of de�ning and capturing structure in a prob-lem instance, there are also various ways to parameterize a problem.
This course is an introduction to parameterized complexity and its fundamentals with a focus on basic problems in graph theory, SAT, and model counting. We mainly focus on two parameters, namely, backdoors and treewidth. Beyond standard theoretical ideas to the topic, which usually focus on simple tractability or intractability results for a certain restriction on the input, we are interested in the actualalgorithms and their implementations. Therefore, we will also take a closer look at solvers, including sequential and parallel implementations.
Lectures will be given in English.
Prerequisites
Basic understanding of propositional logic. Preferably completed a Bachelor in Mathematics or computer science or being close to doing so. Standard Bache-lor lectures about algorithm design/analysis, discrete structures, logic, complexity are bene�cial.
References:The recent book by Cygan et al. (see below) covers essentially all the material of the lecture and is highly recommended.[1] M. Cygan et al., Parameterized algorithms, Springer, 2015[2] R.G. Downey and M.R. Fellows. Fundamentals of parameterized complexity,Springer, 2013[3] R. Niedermeier, Invitation to �xed-parameter algorithms, Oxford University Press, 2006[4] J. Flum and R. Grohe, Parameterized complexity theory, Springer, 2006
DESIGN AND ANALYSIS OF ALGORITHMS
Guest Lectures
