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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


Back to homepage