Ten most important publications of D醤iel Marx

Note: the copyright of the published papers is with the respective publishers. The papers are made available here to ensure the timely dissemination of scholarly information. The published versions of the papers may have gone through additional rounds of copyediting and proofreading.

Detailed list (with abstracts)

2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004

Conference papers without journal versions:
2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000

Papers appearing in edited volumes:
2020 2012

Volume editing:
2012

Manuscripts -->

Books
2021 – 2020 – 2019 – 2018 – 2017 – 2016 – 2015 – 2014 – 2013 – 2012 – 2011 – 2010 – 2009 – 2008 – 2007 – 2006 – 2005 – 2004 -->
    -->
  1. Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs.
    SIAM Journal on Computing, 44(1):114-159, 2015.
    (with: Martin Grohe)

  2. Interval deletion is fixed-parameter tractable.
    ACM Transaction on Algorithms, 11(3):21, 2015.
    (with: Yixin Cao)

    Conference version:
    Interval deletion is fixed-parameter tractable.
    In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), 122-141, 2014.
    (with: Yixin Cao)

  3. Tractable hypergraph properties for constraint satisfaction and conjunctive queries.
    Journal of the ACM, 60(6):42, 2013. (Preliminary version in STOC 2010.)

  4. Approximation schemes for Steiner Forest on planar graphs and graphs of bounded treewidth.
    Journal of the ACM, 58(5):21, 2011. (Preliminary version in STOC 2010.)
    (with: MohammadHossein Bateni, MohammadTaghi Hajiaghayi)

  5. Can you beat treewidth?
    Theory of Computing, 6(1):85-112, 2010. (Preliminary version in FOCS 2007.)

  6. Closest substring problems with small distances.
    SIAM Journal on Computing, 38(4):1382-1410, 2008. (Preliminary version in FOCS 2005.)

    2021 – 2020 – 2019 – 2018 – 2017 – 2016 – 2015 – 2014 – 2013 – 2012 – 2011 – 2010 – 2009 – 2008 – 2007 – 2006 – 2005 – 2004 – 2003 – 2002 – 2001 – 2000

      2021

    1. Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction.
      In Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2021), 19-29, 2021.

    2. Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth.
      In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), 95:1-95:20, 2021.
      (with: Govind S. Sankar, Philipp Schepper)

    3. On the Computational Tractability of a Geographic Clustering Problem Arising in Redistricting.
      In 2nd Symposium on Foundations of Responsible Computing (FORC 2021), 3:1-3:18, 2021.
      (with: Vincent Cohen-Addad, Philip N. Klein, Archer Wheeler, Christopher Wolfram)

      2020

    4. Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-Grained Perspective into Boolean Constraint Satisfaction.
      In Proceedings of Computational Complexity Conference (CCC 2020), 27:1-27:28, 2020.
      (with: Marvin K眉nneman)

    5. Chordless Cycle Packing Is Fixed-Parameter Tractable.
      In Proceedings of 28th Annual European Symposium on Algorithms (ESA 2020), 71:1-71:19, 2020.

    6. Incompressibility of H-Free Edge Modification Problems: Towards a Dichotomy.
      In Proceedings of 28th Annual European Symposium on Algorithms (ESA 2020), 72:1-72:25, 2020.
      (with: R. B. Sandeep)

    7. Hitting Long Directed Cycles Is Fixed-Parameter Tractable.
      In Proceedings of 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 59:1-59:18, 2020. (with: Alexander G枚k and Matthias Mnich)

      2019

    8. Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs (Best Paper Award).
      In Proceedings of the 35th International Symposium on Computational Geometry (SoCG 2019), 27:1-27:16, 2019.
      (with: Vincent Cohen-Addad, Éric Colin de Verdière , and Arnaud de Mesmay)

    9. Parameterized Algorithms for Generalizations of Directed Feedback Vertex Set.
      In International Conference on Algorithms and Complexity (CIAC 2019), Lecture Notes in Computer Science 11485, 249-261, 2019.
      (with: Alexander Göke and Mathias Mnich)

    10. Parameterized Streaming Algorithms for Min-Ones d-SAT.
      In Proceedings of Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019), 8:1-8:20, 2019.
      (with: Akanksha Agrawal, Arindam Biswas, Édouard Bonnet, Nick Brettell, Radu Curticapean, Tillmann Miltzow, Venkatesh Raman, Saket Saurabh)

    11. How Does Object Fatness Impact the Complexity of Packing in d Dimensions?
      In Proceedings of 30th International Symposium on Algorithms and Computation (ISAAC 2019), 36:1-36:18, 2019.
      (with: S谩ndor Kisfaludi-Ba andTom C. van der Zanden)

      2018

    12. On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs.
      In proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2018), 474-484, 2018.
      (with: Marcin Pilipczuk and Michal Pilipczuk)

    13. Covering a tree with rooted subtrees - parameterized and approximation algorithms.
      In proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), 2801-2820, 2018.
      (with: Lin Chen)

    14. Finding List Homomorphisms from Bounded-treewidth Graphs to Reflexive Graphs: a Complete Complexity Characterization.
      In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), 27:1-27:15, 2018.
      (with: L谩szl贸 Egri and Pawel Rzazewski)

      2017

    15. Homomorphisms are a good basis for counting small subgraphs.
      In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), 210-223, 2017.
      (with:Radu Curticapean, Holger Dell)

    16. Subexponential Parameterized Algorithms for Graphs of Polynomial Growth.
      In 25th Annual European Symposium on Algorithms (ESA 2017), 59:1-59:15, 2017.
      (with: Marcin Pilipczuk)

    17. Parameterized and Approximation Results for Scheduling with a Low Rank Processing Time Matrix.
      34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), 22:1-22:14, 2017.
      (with: Lin Chen, Deshi Ye, and Guochuan Zhang)

      2016

    18. Constant-factor approximations for asymmetric TSP on nearly-embeddable graphs.
      Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016), 16:1-16:54, 2016.
      (with: Ario Salmasi and Anastasios Sidiropoulos)

    19. Fixed-parameter approximability of Boolean MinCSPs.
      4th Annual European Symposium on Algorithms (ESA 2016), 18:1-18:18, 2016.
      (with: Édouard Bonnet and L谩szl贸 Egri)

    20. Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering.
      In Proceedings of the 57th Annual Symposium on Foundations of Computer Science (FOCS 2016), 515-524, 2016.
      (with: Fedor Fomin, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh)

    21. The complexity landscape of fixed-parameter directed Steiner network problems.
      43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), 27:1-27:14, 2016.
      (with: Andreas Feldmann)

    22. Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth.
      43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), 28:1-28:15, 2016.
      (with: Valia Mitsou)

    23. Parameterized vertex deletion problems for hereditary graph classes with a block property.
      42nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2016), 233-244, 2016.
      (with: Édouard Bonnet, Nick Brettell, and O-joung Kwon)

    24. A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting.
      In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016), 570-583, 2016.
      (with: MohammadHossein Bateni, Erik Demaine, and MohammadTaghi Hajiaghayi)

    25. Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus.
      In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), 1650-1669, 2016.
      (with: Radu Curticapean)

    26. Peeling and nibbling the cactus: subexponential-time algorithms for counting triangulations and related problems.
      In Proceedings of the 32nd International Symposium on Computational Geometry (SoCG 2016), 52:1-52:16, 2016.
      (with: Tillmann Miltzow)

      2015

    27. An exact characterization of tractable demand patterns for maximum disjoint path problems.
      In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), 642-661,2015.
      (with: Paul Wollan)

    28. Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels.
      In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), 616-629, 2015.
      (with: Bart M. P. Jansen)

    29. Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams.
      In Proceedings of the 23rd European Symposium on Algorithms (ESA 2015), Lecture Notes in Computer Science Volume 9294, Springer, 865-877, 2015.
      (with: Michal Pilipczuk)

      -->

    30. The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable.
      In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), 197-206, 2013.
      (with:Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk)

    31. Block-Sorted Quantified Conjunctive Queries
      40th International Colloquium on Automata, Languages and Programming (ICALP 2013), Volume 2, 125-136, Lecture Notes in Comput. Sci., 7965, Springer, 2013.
      (with: Hubie Chen)

      2012

      -->

    32. Finding topological subgraphs is fixed-parameter tractable.
      In Proceedings of the 43rd annual ACM symposium on Theory of computing (STOC 2011), 479-488, 2011.
      (with: Martin Grohe, Ken-ichi Kawarabayashi, and Paul Wollan)

    33. On the optimality of planar and geometric approximation schemes.
      In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 338-348, 2007.

    BackBack to homepage