List of research talks by Dániel Marx
List of publications

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

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

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

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

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

  6. 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

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

  8. 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

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

  10. 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

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

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

  13. Fine-Grained Complexity and Algorithm Design Boot Camp
    Simons Institute for the Theory of Computing, Berkeley, CA, September 1-4, 2015.
    Talk 1Talk 2Talk 3Talk 4
    Videos

  14. 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

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

  16. Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels (invited talk)
    WorKer 2015: Workshop on Kernelization, Nordfjordeid, Norway, June 1, 2015.
    Slides

  17. Minicourse on parameterized algorithms and complexity
    Jagiellonian University in Krakow, Poland, April 21-23, 2015.
    Slides Slides Slides Slides Slides Slides Slides Slides

  18. 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

  19. 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

  20. 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

  21. 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

  22. Important separators and parameterized algorithms
    School on Parameterized Algorithms and Complexity, Będlewo, Poland, August 19-22, 2014.
    Slides Slides Slides

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

  24. 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

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

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

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

  28. 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

  29. Interval deletion is fixed-parameter tractable
    Symposium on Discrete Algorithms (SODA 2014), Portland, OR, January 5, 2014.
    Slides

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

  31. 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

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

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

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

  35. 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

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

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

  38. 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

  39. Fixed-parameter algorithms for minimum cost edge-connectivity augmentation
    40th International Colloquium on Automata, Languages and Programming (ICALP 2013), Riga, Latvia, July 8, 2013.
    Slides

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

  41. The square root phenomenon in planar graphs
    FAW-AAIM 2013, Dalian, China, June 27, 2013.
    Slides

  42. CSPs and fixed-parameter tractability
    Algorithms Seminar, University of Bergen, Norway, June 7, 2013.
    Slides

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

  44. 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

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

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

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

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

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

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

  51. Solving PLANAR k-TERMINAL CUT in O(nck) time
    39th International Colloquium on Automata, Languages and Programming (ICALP 2012), Warwick, UK, July 13, 2012.
    Slides

  52. 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

  53. 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

  54. 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

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

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

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

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

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

  60. Important separators and parameterized algorithms (invited talk)
    37th International Workshop on Graph-Theoretic Methods in Computer Science Teplá Monastery, Czech Republic, June 23, 2011.
    Slides

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

  62. Finding topological subgraphs is fixed-parameter tractable
    Treewidth Workshop 2011, Bergen, Norway, May 19, 2011.
    Slides

  63. 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

  64. Important separators and parameterized algorithms
    Methods for Discrete Structures, Humboldt-Universität zu Berlin, Germany, February 7, 2011.
    Slides

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

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

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

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

  69. Fixed-parameter tractability of multicut parameterized by the size of the cutset
    Dagstuhl Seminar 10441: Exact Complexity of NP-hard Problems, Schloss Dagstuhl, Germany, November 1, 2010.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  84. 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

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

  86. Constant ratio fixed-parameter approximation of the edge multicut problem
    6th Japanese-Hungarian Symposiumon Discrete Mathematics and Its Applications, Budapest, Hungary, May 16, 2009.

  87. Movement problems
    Max-Planck-Institut fĂĽr Informatik, SaarbrĂĽcken, Germany, April 28, 2009.

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

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

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

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

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

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

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

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

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

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

  98. Movement problems
    ``Logik in der Informatik'' Seminar, Institut für Informatik, Humboldt-Universität zu Berlin, Germany, June 11, 2008.

  99. Movement problems
    Friedrich-Schiller-Universität Jena, Germany, June 9, 2008.

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

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

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

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

  104. On tree width, bramble size, and expansion
    Graduirtenkolleg: Methods for Discrete Structures, Humboldt-Universität zu Berlin, Germany, February 5, 2007.

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

  106. 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.

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

  108. Chordal deletion is fixed-parameter tractable.
    Workshop on Graph-Theoretic Concepts in Computer Science (WG) 2006, Bergen, Norway, June 22, 2006.
    Slides

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

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

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

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

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

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

  115. Trees, tree width, hypertree width, fractional hypertree width.
    33. Berliner Algorithmen-Tag, Freie Universität Berlin, July 15, 2005.
    Slides

  116. The Closest Substring problem with small distances.
    ``Logik in der Informatik'' Seminar, Institut für Informatik, Humboldt-Universität zu Berlin, June 10, 2005.
    Slides

  117. Parameterized complexity of constraint satisfaction problems.
    ``Logik in der Informatik'' Seminar, Institut für Informatik, Humboldt-Universität zu Berlin, December 10, 2004.
    Slides

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

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

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

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

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

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

  124. 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.

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

  126. 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

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

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

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

  130. The complexity of tree multicolorings.
    Mathematical foundations of computer science (MFCS) 2002. Warsaw-Otwock, August 28, 2002.
    Slides

  131. Graph-theoretic problems in configuring WDM optical networks.
    University of Modena & Reggio Emilia, Italy, June, 2000,


Back to homepage