
Towards a Tight Understanding of the Complexity of Algorithmic
Problems
Saarland Informatics Campus Lecture Series, Saarbrücken, Germany,
January 8, 2020.
Slides

Parameterized Complexity of Even Set (and others)
Dagstuhl Seminar 19041:
New Horizons in Parameterized Complexity,
January 25, 2019.
Slides

FPT suspects and tough customers: Open problems
of Downey and Fellows
Dagstuhl Seminar 19041:
New Horizons in Parameterized Complexity,
January 25, 2019.
Slides

Recent Advances on the Complexity of Parameterized Counting
Problems (invited talk)
30th ACMSIAM Symposium on Discrete Algorithms (SODA 2019), San Diego, CA,
January 7, 2019.
Slides

On subexponential parameterized algorithms for Steiner Tree and Directed Subset TSP on planar graphs
59th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018),
Paris, France,
October 9, 2018.
Slides

Counting in parameterized complexity
Recent Advances in Parameterized Complexity, Tel Aviv, Israel,
December 7, 2017.
Slides

Strong ExponentialTime Hypothesis (SETH)
Recent Advances in Parameterized Complexity, Tel Aviv, Israel,
December 5, 2017.
Slides

Treewidth
Recent Advances in Parameterized Complexity, Tel Aviv, Israel,
December 4, 2017.
Slides

W[1]hardness
Recent Advances in Parameterized Complexity, Tel Aviv, Israel,
December 3, 2017.
Slides

The optimality program in parameterized algorithms
(invited talk)
23rd Annual International Computing and Combinatorics Conference (COCOON
2017), Hong Kong, China,
August 3, 2017.
Slides

Graphs, Hypergraphs, and the Complexity of
Conjunctive Database Queries
ICDT Invited Lecture 2017, Venice, Italy,
March 23, 2017.
Slides

Subexponential parameterized algorithms on
planar graphs via lowtreewidth pattern covering
Dagstuhl Seminar 17041, Schloss Dagstuhl, Germany,
January 26, 2017.
Slides

Some open problems in parameterized complexity
Dagstuhl Seminar 17041, Schloss Dagstuhl, Germany,
January 23, 2017.
Slides

The optimality program in parameterized algorithms
University of Warsaw, Poland,
October 20, 2016.
Slides

The Complexity Landscape of FixedParameter
Directed Steiner Network Problems
Southern Italian Workshop on Algorithms and Graphs 2016 (SIWAG),
Polignano a Mare, Italy,
September 26, 2016.
Slides

The optimality program in parameterized algorithms
(invited talk)
The 10th Jubilee Conference of PhD Students in Computer Science (CSCS),
Szeged, Hungary,
June 27, 2016.
Slides

The Complexity Landscape of FixedParameter
Directed Steiner Network Problems (invited talk)
15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016),
Reykjavik, Iceland,
June 23, 2016.
Slides

A PTAS for Planar Group Steiner Tree via
Spanner Bootstrapping and Prize Collecting
48th ACM Symposium on Theory of Computing (STOC 2016), Boston, MA,
June 20, 2016.
Slides

The optimality program in parameterized algorithms
Highlights of Algorithms, Paris, France,
June 6, 2016.
Slides

The Square Root Phenomenon in Planar Graphs —
Survey and New Results
Dagstuhl Seminar 16221: Algorithms for Optimization Problems in Planar
Graph, Schloss Dagstuhl, Germany,
June 1, 2016.
Slides

Subexponential parameterized algorithms on
planar graphs via lowtreewidth covering families
Oberwolfach Seminar 1602: Graph Theory, Oberwolfach, Germany,
January 15, 2015.
Slides

The Square Root Phenomenon in Planar Graphs —
Survey and New Results
Satisfiability Lower Bounds and Tight Results for Parameterized and
ExponentialTime Algorithms Workshop, Simons Institute for the Theory of Computing, Berkeley, CA,
November 6, 2015.
Slides Video

FineGrained Complexity and Algorithm Design Boot
Camp
Simons Institute for the Theory of Computing, Berkeley, CA,
September 14, 2015.
Talk 1
— Talk 2
— Talk 3
— Talk 4
Videos

Modern irĂˇnyzatok a bonyolultsĂˇgelmĂ©letben: Ă©les korlĂˇtok Ă©s dichotĂłmiatĂ©telek [In Hungarian]
Institute for Computer Science and Control,
Hungarian Academy of Sciences (MTA SZTAKI), Budapest, Hungary,
June 15, 2015.
Slides

Every graph is easy or hard:
dichotomy theorems for graph problems
Carnegie Mellon University, Pittsburgh, PA,
June 10, 2015.
Slides

Characterizing the easytofind subgraphs from the
viewpoint of polynomialtime algorithms, kernels, and Turing kernels
(invited talk)
WorKer 2015: Workshop on Kernelization, Nordfjordeid, Norway,
June 1, 2015.
Slides

Minicourse on parameterized algorithms and
complexity
Jagiellonian University in Krakow, Poland,
April 2123, 2015.
Slides Slides Slides Slides Slides Slides Slides Slides

Optimal parameterized algorithms for planar
facility location problems using
Voronoi diagrams and sphere cut decompositions (invited talk)
International Workshop on Graph Decomposition, CIRM, Marseille, France,
January 19, 2015.
Slides

An exact characterization of tractable demand
patterns for maximum disjoint path problems
Symposium on Discrete Algorithms (SODA 2015), San Diego, CA,
January 4, 2015.
Slides

Every graph is easy or hard:
dichotomy theorems for graph problems
Dagstuhl Seminar 14451:
Optimality and tight results in parameterized complexity, Schloss Dagstuhl,
Germany, November 7, 2014.
Slides

Every graph is easy or hard:
dichotomy theorems for graph problems (invited talk)
39th International Symposium on
Mathematical Foundations of Computer Science (MFCS 2014),
Budapest, Hungary, August 29, 2014.
Slides

Important separators and parameterized
algorithms
School on Parameterized Algorithms and Complexity, BÄ™dlewo, Poland,
August 1922, 2014.
Slides Slides Slides

W[1]hardness
School on Parameterized Algorithms and Complexity, BÄ™dlewo, Poland,
August 18, 2014.
Slides

Every graph is easy or hard:
dichotomy theorems for graph problems (invited talk)
9th International colloquium on graph theory and combinatorics (ICGT 2014),
Grenoble, France,
July 3, 2014.
Slides

Important separators and parameterized
algorithms
ICERM, Brown University, Providence, RI,
April 27, 2014.
Slides

Lower bounds for parameterized problems
ICERM, Brown University, Providence, RI,
April 26, 2014.
Slides

A subexponential parameterized algorithm for
Subset TSP on planar graphs
Symposium on Discrete Algorithms (SODA 2014), Portland, OR,
January 7, 2014.
Slides

Tight bounds for planar strongly connected Steiner
subgraph with fixed number of terminals (and extensions)
Symposium on Discrete Algorithms (SODA 2014), Portland, OR,
January 7, 2014.
Slides

Interval deletion is fixedparameter tractable
Symposium on Discrete Algorithms (SODA 2014), Portland, OR,
January 5, 2014.
Slides

Finding small patterns in permutations in linear
time
Symposium on Discrete Algorithms (SODA 2014), Portland, OR,
January 5, 2014.
Slides

Everything you always wanted to know about the parameterized complexity of
Subgraph Isomorphism (but were afraid to ask) (invited talk)
3nd Bertinoro Workshop on Algorithms and Graphs, Bertinoro, Italy,
December 16, 2013.
Slides

The square root phenomenon in planar graphs
Bidimensional Structures: Algorithms and Combinatorics (FOCS 2013 Worksop
Day), Berkeley, CA,
October 26, 2013.
Slides

The square root phenomenon in planar graphs
Dagstuhl Seminar 13421:
Algorithms for Optimization Problems in Planar Graphs,
Schloss Dagstuhl, Germany,
October 14, 2013.
Slides

Decomposition theorems for graphs excluding
structures (invited talk)
EuroComb 2013, Pisa, Italy, 13, 2013.
Slides

A subexponential parameterized algorithm for
Subset TSP on planar graphs
Dagstuhl Seminar 13331: Exponential Algorithms: Algorithms and Complexity
Beyond Polynomial Time, Schloss Dagstuhl, Germany,
August 15, 2013.
Slides

Algorithmic graph structure theory
14th Max Planck Advanced Course
on the Foundations of Computer Science (ADFOCS 2013),
SaarbrĂĽcken, Germany, August 59, 2013.
Slides

BlockSorted Quantified Conjunctive Queries
40th International Colloquium on Automata, Languages and
Programming (ICALP 2013),
Riga, Latvia,
July 10, 2013.
Slides

The square root phenomenon in planar graphs
(invited talk)
40th International Colloquium on Automata, Languages and
Programming (ICALP 2013),
Riga, Latvia,
July 9, 2013.
Slides

Fixedparameter algorithms for minimum cost
edgeconnectivity augmentation
40th International Colloquium on Automata, Languages and
Programming (ICALP 2013),
Riga, Latvia,
July 8, 2013.
Slides

CSPs and fixedparameter tractability (invited
talk)
International Workshop on Approximation, Parameterized and
EXact algorithms,
Riga, Latvia,
July 7, 2013.
Slides

The square root phenomenon in planar graphs
FAWAAIM 2013, Dalian, China,
June 27, 2013.
Slides

CSPs and fixedparameter tractability
Algorithms Seminar,
University of Bergen, Norway,
June 7, 2013.
Slides

The square root phenomenon in planar graphs
CS Theory Seminar, The Hebrew University of Jerusalem, Israel,
May 22, 2013.
Slides

Randomized techniques for parameterized
algorithms (invited talk)
13th Haifa Workshop on Interdisciplinary Applications of Graph
Theory, Combinatorics, and Algorithms, Haifa, Israel,
May 19, 2013.
Slides

Important separators and parameterized algorithms
Update Meeting on Graph Cuts, University of Warsaw, Poland,
April 9, 2013.
Slides

The kdisjoint paths problem in directed planar
graphs
Dagstuhl Seminar 13121: Bidimensional Structures: Algorithms, Combinatorics
and Logic, Schloss Dagstuhl,
Germany, March 21, 2013.
Slides

Algorithmic graph structure theory (tutorial)
30th International Symposium on Theoretical Aspects of Computer Science,
Kiel, Germany, February 27, 2013.
Slides

The kdisjoint paths problem in directed planar
graphs
Oberwolfach Workshop 1303: Graph Theory,
Oberwolfach, Germany, January 17, 2013.
Slides

CSPs and fixedparameter tractability
Dagstuhl Seminar 12451:
The Constraint Satisfaction Problem: Complexity and Approximability, Schloss Dagstuhl, Germany,
November 5, 2012.
Slides

Randomized techniques for parameterized
algorithms (invited talk)
7th International Symposium on Parameterized and Exact Computation (IPEC
2012), Ljubljana, Slovenia,
September 13, 2012.
Slides

Solving PLANAR kTERMINAL CUT in
O(n^{c√k}) time
39th International Colloquium on Automata, Languages and
Programming (ICALP 2012), Warwick, UK,
July 13, 2012.
Slides

A Tight Lower Bound for Planar Multiway Cut with
Fixed Number of Terminals
39th International Colloquium on Automata, Languages and
Programming (ICALP 2012), Warwick, UK,
July 13, 2012.
Slides

FPT suspects and tough customers: Open problems
of Downey and Fellows
Dagstuhl Seminar 12241:
Data Reduction and Problem Kernels, Schloss Dagstuhl, Germany,
June 14, 2012.
Slides

Structure Theorem and Isomorphism Test for Graphs
with Excluded
Topological Subgraphs
44th ACM Symposium on Theory of Computing (STOC 2012), New York, NY,
May 20, 2012.
Slides

Structure Theorem and Isomorphism Test for Graphs
with Excluded
Topological Subgraphs
Graph Theory @ Georgia Tech, Atlanta, GA,
May 8, 2012.
Slides

Structure Theorem and Isomorphism Test for Graphs
with Excluded
Topological Subgraphs
2nd Bertinoro Workshop on Algorithms and Graphs, Bertinoro, Italy,
December 15, 2011.
Slides

Kernelization of Packing Problems
WorKer 2011: Workshop on Kernelization, Vienna, Austria,
September 4, 2011.

Clustering with local restrictions
38th International Colloquium on Automata, Languages and Programming
(ICALP 2011), ZĂĽrich, Switzerland,
July 8, 2011.

Constraint satisfaction parameterized by
solution size
38th International Colloquium on Automata, Languages and Programming
(ICALP 2011), ZĂĽrich, Switzerland,
July 6, 2011.

Important separators and parameterized algorithms
(invited talk)
37th International Workshop on GraphTheoretic Methods in Computer Science
TeplĂˇ Monastery, Czech Republic,
June 23, 2011.
Slides

Finding topological subgraphs is fixedparameter
tractable
43th ACM Symposium on Theory of Computing (STOC 2011), San Jose, CA,
June 7, 2011.
Slides

Finding topological subgraphs is fixedparameter
tractable
Treewidth Workshop 2011, Bergen, Norway, May 19, 2011.
Slides

Survey of connections between approximation
algorithms and parameterized complexity
Dagstuhl Seminar 11091: Packing and Scheduling Algorithms for Information
and Communication Services, Schloss Dagstuhl, Germany, February 28, 2011.
Slides

Important separators and parameterized algorithms
Methods for Discrete Structures, HumboldtUniversitĂ¤t zu Berlin,
Germany,
February 7, 2011.
Slides

Known algorithms on graphs of bounded treewidth
are probably optimal
Symposium on Discrete Algorithms (SODA 2011), San Francisco, CA,
January 24, 2011.
Slides

Fixedparameter tractability of multicut
parameterized by the size of the cutset
Department of Computer Science, University of Maryland, College Park, MD,
January 18, 2011.
Slides

Fixedparameter tractability of multicut
parameterized by the size of the cutset
WorKer 2010: Workshop on Kernelization, Leiden, The Netherlands,
November 12, 2010.
Slides

What's next? Reductions other than kernelization
WorKer 2010: Workshop on Kernelization, Leiden, The Netherlands,
November 9, 2010.
Slides

Fixedparameter tractability of multicut
parameterized by the size of the cutset
Dagstuhl Seminar 10441: Exact Complexity of NPhard Problems, Schloss
Dagstuhl, Germany, November 1, 2010.

Fixed Parameter Algorithms
International Workshop on Tractability, Microsoft Research, Cambridge, UK,
July 5, 2010.
Slides

Completely inapproximable monotone and
antimonotone parameterized problems
25th IEEE Conference on Computational Complexity (CCC 2010), Cambridge, MA,
June 10, 2010.

Tractable hypergraph properties for constraint
satisfaction and conjunctive queries
42th ACM Symposium on Theory of Computing (STOC 2010), Cambridge, MA,
June 8, 2010.

Tractable hypergraph properties for constraint
satisfaction and conjunctive queries
Foundations of Computer Science Seminar, Weizmann Institute, Israel,
May 16, 2010.
Slides

Important separators and parameterized algorithms
Combinatorics Seminar, University of Haifa, Israel,
May 5, 2010.

Movement problems
Computer Science Colloquium, Technion, Haifa, Israel,
April 13, 2010.

Treewidth reduction for constrained separation and
bipartization problems
Oberwolfach Workshop 1008: Graph Theory, Oberwolfach, Germany,
February 23, 2010.

Survey of connections between approximation
algorithms and parameterized complexity
Operations Research Seminar, Technion, Haifa, Israel,
January 18, 2010.
Slides

Fixed parameter algorithms
Open lectures for PhD students in computer science, University of Warsaw,
Poland, January 89, 2010.
Part 2: Treewidth
Part 3: Complexity

Survey of connections between approximation
algorithms and parameterized complexity
Dagstuhl Seminar 09511: Parameterized complexity and approximation
algorithms, Schloss Dagstuhl, Germany, December 14, 2009.
Slides

Fixed parameter algorithms
Open lectures for PhD students in computer science, University of Warsaw,
Poland, December 12, 2009.
Part 1: Algorithmic techniques

Important separators and spiders
Bertinoro Workshop on Algorithms and Graphs, Italy,
December 8, 2009.
Slides

Combinatorial problems related to treewidth and
its generalizations to hypergraphs
Combinatorics Seminar, Tel Aviv University, Israel, November 8, 2009.

Beyond fractional hypertree width
Dagstuhl Seminar 09441: The Constraint Satisfaction Problem: Complexity and
Approximability, Schloss Dagstuhl, Germany,
October 26, 2009.
Slides

Structural complexity of CSPs: the role of
treewidth and its
generalizations
Dagstuhl Seminar 09441: The Constraint Satisfaction Problem: Complexity and
Approximability, Schloss Dagstuhl, Germany,
October 26, 2009.
Slides

FPT algorithmic techniques
AGAPE'09 Spring School on Fixed Parameter and Exact Algorithms, Lozari,
Corsica, France,
May 2526, 2009.
Slides Slides (printable)

Constant ratio fixedparameter approximation of
the edge multicut problem
6th JapaneseHungarian Symposiumon Discrete Mathematics and Its
Applications, Budapest, Hungary,
May 16, 2009.

Movement problems
MaxPlanckInstitut fĂĽr Informatik, SaarbrĂĽcken, Germany,
April 28, 2009.

Improving local search using parameterized
complexity
Dagstuhl Seminar 09171: Adaptive, Output Sensitive, Online and
Parameterized Algorithms, Schloss Dagstuhl, Germany,
April 20, 2009.

Tractable Structures for Constraint Satisfaction
with Truth Tables
26th International Symposium on Theoretical Aspects of Computer
Science (STACS 2009), Freiburg, Germany,
February 26, 2009.

Enumerating homomorphisms
26th International Symposium on Theoretical Aspects of Computer
Science (STACS 2009), Freiburg, Germany,
February 26, 2009.

Improving local search using parameterized
complexity
Departament de Llenguatges i Sistemes Informètics, Universitat
Politècnica de Catalunya, Barcelona, Spain,
February 25, 2009.

Fractional covers and constraint satisfaction.
RĂ©nyi Institute, Budapest, Hungary,
February 19, 2009.

Approximating fractional hypertree width.
Symposium on Discrete Algorithms (SODA) 2009, New York, NY,
January 6, 2009.

Improving local search using parameterized
complexity
Cork Constraint Computing Center, University College Cork, Ireland,
December 10, 2008.
Slides

Movement problems
CS Theory Seminar, Simon Fraser University, Vancouver, Canada BC,
October 17, 2008.

On tree width, bramble size, and expansion
Fete of Combinatorics and Computer Science, Keszthely, Hungary
August 13, 2008.

On the hardness of losing weight
International Colloquium on
Automata, Languages and Programming (ICALP) 2008, Reykjavik, Iceland,
July 10, 2008.

Movement problems
``Logik in der Informatik'' Seminar, Institut fĂĽr Informatik, HumboldtUniversitĂ¤t zu Berlin, Germany,
June 11, 2008.

Movement problems
FriedrichSchillerUniversitĂ¤t Jena, Germany,
June 9, 2008.

On the optimality of planar and geometric
approximation schemes
Foundations of Computer Science (FOCS) 2007, Providence, Rhode Island,
October 22, 2007.

Can you beat treewidth?
Foundations of Computer Science (FOCS) 2007, Providence, Rhode Island,
October 21, 2007.

On tree width, bramble size, and expansion
Charles University, Prague, Czech Republic,
May 3, 2007.

Parameterized complexity of constraint satisfaction problems.
CS Theory Seminar, Simon Fraser University, Vancouver, Canada BC,
April 19, 2007.

On tree width, bramble size, and expansion
Graduirtenkolleg: Methods for Discrete Structures, HumboldtUniversitĂ¤t zu Berlin,
Germany,
February 5, 2007.

A parameterized view on matroid optimization
problems.
Algorithms and Complexity in Durham (ACiD) 2006, Durham, United Kingdom,
September 19, 2006.

Parameterized Complexity of Independence and Domination
on Geometric Graphs.
2nd International Workshop on Parameterized and Exact Computation (IWPEC)
2006, ZĂĽrich, Switzerland,
September 14, 2006.

A parameterized view on matroid optimization
problems.
International Colloquium on
Automata, Languages and Programming (ICALP) 2006, Venice, Italy,
July 14, 2006.
Slides

Chordal deletion is fixedparameter tractable.
Workshop on GraphTheoretic Concepts in Computer Science (WG) 2006, Bergen,
Norway,
June 22, 2006.
Slides

Closest substring problems with small distances.
Department of Computer Science and Operations Research, UniversitĂ© de
MontrĂ©al, Canada,
April 20, 2006.
Slides

Constraint Solving via Fractional Edge Covers.
MathsCSP Workshop, St Anne's College, University of Oxford,
March 22, 2006.
Slides

Constraint Solving via Fractional Edge Covers.
Symposium on Discrete Algorithms (SODA) 2006, Miami, Florida,
January 22, 2006.
Slides

The Closest Substring problem with small distances.
Foundations of Computer Science (FOCS) 2005, Pittsburgh, Pennsylvania,
October 23, 2005.
Slides

Efficient approximation schemes for geometric problems?
European Symposium on Algorithms (ESA) 2005,
Palma de Mallorca, Spain, October 4, 2005.
Slides

The Closest Substring problem with small distances.
Dagstuhl Seminar 05301: Exact Algorithms and FixedParameter Tractability,
July 25, 2005.
Slides

Trees, tree width, hypertree width, fractional
hypertree width.
33. Berliner AlgorithmenTag, Freie UniversitĂ¤t Berlin,
July 15, 2005.
Slides

The Closest Substring problem with small distances.
``Logik in der Informatik'' Seminar, Institut fĂĽr Informatik, HumboldtUniversitĂ¤t zu Berlin,
June 10, 2005.
Slides

Parameterized complexity of constraint satisfaction problems.
``Logik in der Informatik'' Seminar, Institut fĂĽr Informatik, HumboldtUniversitĂ¤t zu Berlin,
December 10, 2004.
Slides

Parameterized coloring problems on chordal graphs
International Workshop on Parameterized and Exact Computation (IWPEC) 2004,
Bergen, Norway, September 15, 2004.
Slides

Parameterized graph separation problems
International Workshop on Parameterized and Exact Computation (IWPEC) 2004
Bergen, Norway, September 14, 2004.
Slides

Minimum sum multicoloring on the edges of planar graphs and partial ktrees.
2nd Workshop on Approximation and Online Algorithms (WAOA) 2004.
Bergen, Norway,
September 14, 2004.
Slides

Precoloring extension on chordal graphs.
Graph Theory 2004, Paris, France.
July 6, 2004.
Slides

Parameterized complexity of constraint satisfaction problems.
19th Annual IEEE Conference on Computational Complexity 2004.
Amherst, Massachusetts,
June 22, 2004.
Slides

Parameterized complexity of constraint satisfaction problems.
Seminar of the Mathematical Logic Group, Mathematical Institute of the University of Freiburg.
June 7, 2004.
Slides

How to get n out of the exponent? Introduction to parameterized complexity. [In Hungarian]
EgervĂˇry Research Group Combinatorial Optimization Seminar, EĂ¶tvĂ¶s LorĂˇnd University.
May 17, 2004.

Parameterized complexity of constraint satisfaction problems.
Seminar of the School of Electrical Engineering and Computer Science, University of Newcastle, Australia,
March 15, 2004.
Slides

Graph coloring problems and their applications in scheduling. [In Hungarian]
John von Neumann PhD stundents Conference, Budapest University of Technology
and Economics. Budapest, Hungary, October 2, 2003.
Slides

Minimum sum multicoloring on the edges of trees.
1st Workshop on Approximation and Online Algorithms (WAOA) 2003.
Budapest, Hungary, September 17, 2003.
Slides

List edge multicoloring in bounded cyclicity
graphs.
3rd HungarianJapanese Symposium on Discrete Mathematics and
Its Application. Tokyo, Japan, January 22, 2003.
Slides

A generalized family of packing and covering problems.
Como workshop. Vila Olmo, Como, Italy,
September 3, 2002.

The complexity of tree multicolorings.
Mathematical foundations of computer science (MFCS) 2002. WarsawOtwock,
August 28, 2002.
Slides

Graphtheoretic problems in configuring WDM optical networks.
University of Modena & Reggio Emilia, Italy,
June, 2000,