Publications of Dániel 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. Most of the papers here list the authors in strict alphabetic ordering, which is the standard convention in mathematics and theoretical computer science.

List of research talks – DBLP

Journal papers:
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
  1. Parameterized Algorithms.

    by Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov,
    Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh

    Springer 2015, ISBN 978-3-319-21274-6, pp. 3-555.
Journal papers
2021 – 2020 – 2019 – 2018 – 2017 – 2016 – 2015 – 2014 – 2013 – 2012 – 2011 – 2010 – 2009 – 2008 – 2007 – 2006 – 2005 – 2004
    2021

  1. Parameterized Intractability of Even Set and Shortest Vector Problem.
    Journal of the ACM. 68(3): 16:1-16:40, 2021.
    (with: Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi)

  2. Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs.
    Journal of the ACM, 68(4): 30:1-30:26, 2021
    (with: Vincent Cohen-Addad, Éric Colin de Verdière, and Arnaud de Mesmay)

    Conference version:
    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)

  3. Finding and Counting Permutations via CSPs
    Algorithmica, 83(8): 2552-2577 (2021)
    (with: Benjamin Aram Berendsohn and László Kozma)

    Conference version:
    Finding and Counting Permutations via CSPs
    In Proceedings of 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), 1:1-1:16
    (with: Benjamin Aram Berendsohn and László Kozma)

    2020

  4. Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions).
    SIAM J. Comput. 49(2): 318-364, 2020.
    (with: Rajesh Chitnis, Andreas Feldmann and MohammadTaghi Hajiaghayi)

    Conference version:
    Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions).
    In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), 1782-1801, 2014.
    (with: Rajesh Chitnis and MohammadTaghi Hajiaghayi)

  5. A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs.
    SIAM J. Comput. 49(6): 1291-1331, 2020.
    (with:Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, and Tom C. van der Zanden)

    Conference version:
    A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs.
    In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), 574-586, 2018.
    (with: Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, and Tom C. van der Zanden)

  6. Multi-Budgeted Directed Cuts
    Algorithmica 82(8): 2135-2155, 2020.
    (with: Stefan Kratsch, Shaohua Li, Marcin Pilipczuk, and Magnus Wahlström)

    Conference version:
    Multi-Budgeted Directed Cuts
    In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), 18:1-18:14, 2018.
    (with: Stefan Kratsch, Shaohua Li, Marcin Pilipczuk, and Magnus Wahlström)

  7. The Parameterized Hardness of the k-Center Problem in Transportation Networks.
    Algorithmica 82(7): 1989-2005, 2020.
    (with: Andreas Feldmann)

    Conference version:
    The Parameterized Hardness of the k-Center Problem in Transportation Networks.
    In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), 19:1-19:13, 2018.
    (with: Andreas Feldmann)

    2019

  8. Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality Is the Key to Single-Exponential Parameterized Algorithms.
    Algorithmica 81(10): 3890-3935, 2019.
    (with: Édouard Bonnet, Nick Brettell, and O-joung Kwon)

    Conference version:
    Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality Is the Key to Single-Exponential Parameterized Algorithms.
    42nd In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), 7:1-7:13, 2017.
    (with: Édouard Bonnet, Nick Brettell, and O-joung Kwon)

  9. Routing with congestion in acyclic digraphs.
    Inf. Process. Lett. 151, 7:1-7:11, 2019.
    (with: Saeed Akhoondian Amiri, Stephan Kreutzer, and Roman Rabinovich)

    Conference version:
    Routing with congestion in acyclic digraphs.
    41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), 7:1-7:11, 2016.
    (with: Saeed Akhoondian Amiri, Stephan Kreutzer, and Roman Rabinovich)

  10. Subexponential-Time Algorithms for Maximum Independent Set in Pt-Free and Broom-Free Graphs.
    Algorithmica,81(2):421-438, 2019.
    (with: Gábor Bacsó, Daniel Lokshtanov, Marcin Pilipczuk, Zsolt Tuza, and Erik Jan van Leeuwen)

    Conference version:
    H-free graphs, independent sets, and subexponential-time algorithms.
    11th International Symposium on Parameterized and Exact Computation (IPEC 2016),3:1-3:12, 2016.
    (with: Gábor Bacsó and Zsolt Tuza)

    2018

  11. Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal.
    ACM Transactions on Algorithms, 14(2):13:1-13:30, 2018.
    (with: Daniel Lokshtanov and Saket Saurabh)

    Conference version:
    Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal.
    In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), 777-789, 2011.
    (with: Daniel Lokshtanov and Saket Saurabh)

  12. Slightly Superexponential Parameterized Problems.
    SIAM Journal on Computing, 47(3):675-702, 2018..
    (with: Daniel Lokshtanov and Saket Saurabh)

    Conference version:
    Slightly Superexponential Parameterized Problems.
    In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), 760-776, 2011.
    (with: Daniel Lokshtanov and Saket Saurabh)

  13. Fine-grained complexity of coloring unit disks and balls.
    Journal of Computational Geometry, 9(2):47-80, 2018.
    (with: Csaba Bíró, Édouard Bonnet, Till Miltzow, and Pawel Rzazewski)

    Conference version:
    Fine-grained complexity of coloring unit disks and balls.
    In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG 2017), 18:1-18:16, 2017.
    (with: Csaba Bíró, Édouard Bonnet, Till Miltzow, and Pawel Rzazewski)

    2017

  14. Rooted grid minors.
    J. Combinatorial Theory Ser. B, 122:428-437, 2017.
    (with: Paul Seymour and Paul Wollan)

  15. List H-Coloring a Graph by Removing Few Vertices.
    Algorithmica, 78(1):110-146, 2017.
    (with: Rajesh Chitnis, László Egri)

    Conference version:
    List H-Coloring a Graph by Removing Few Vertices.
    In Proceedings of the 21st European Symposium on Algorithms (ESA 2013), Lecture Notes in Computer Science Volume 8125, Springer, 313-324, 2013.
    (with: Rajesh Chitnis, László Egri)

  16. Hitting forbidden subgraphs in graphs of bounded treewidth.
    Information and Computation, 256:62-82, 2017.
    (with:Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk)

    Conference version:
    Hitting forbidden subgraphs in graphs of bounded treewidth.
    Mathematical foundations of computer science (MFCS 2014), (2)489-500, Lecture Notes in Comput. Sci., 8635, Springer, 2014.
    (with:Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk)

  17. Coloring graphs with constraints on connectivity.
    Journal of Graph Theory, 85(4):814-838, 2017.
    (with:Pierre Aboulker, Nick Brettel, Fréderic Havét, Nicolas Trotignon)

    2016

  18. Parameterized complexity and kernelizability of Max Ones and Exact Ones problems.
    ACM Transactions on Computation Theory, 8(1):1:1-1:28, 2016.
    (with: Stefan Kratsch, Magnus Wahlström)

    Conference version:
    Parameterized complexity and kernelizability of Max Ones and Exact Ones problems.
    Mathematical foundations of computer science (MFCS 2010), 489-500, Lecture Notes in Comput. Sci., 6281, Springer, 2010.
    (with: Stefan Kratsch, Magnus Wahlström)

  19. On problems as hard as CNF-SAT.
    ACM Transactions on Algorithms, 12(3):41:1-41:24, 2016.
    (with:Marek Cygan, Holger Dell, Daniel Lokshtanov, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström)

    Conference version:
    On problems as hard as CNF-SAT.
    Proceedings of the 27th Annual IEEE Conference on Computational Complexity (CCC 2012), 74-84, 2012.
    (with:Marek Cygan, Holger Dell, Daniel Lokshtanov, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström)

  20. Chordal editing is fixed-parameter tractable.
    Algorithmica, 75(1):118-137, 2016.
    (with: Yixin Cao)

    Conference version:
    Chordal editing is fixed-parameter tractable.
    In Proceedings of 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 214-225, 2014.
    (with: Yixin Cao)

    2015

  21. Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs.
    SIAM Journal on Computing, 44(1):114-159, 2015.
    (with: Martin Grohe)

    Conference version:
    Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs.
    In Proceedings of the 44th annual ACM symposium on Theory of computing (STOC 2012), 173-192, 2012.
    (with: Martin Grohe)

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

  23. Fixed-parameter algorithms for minimum cost edge-connectivity augmentation
    ACM Transaction on Algorithms, 11(4):27m 2015.
    (with: László A. Végh)

    Conference version:
    Fixed-parameter algorithms for minimum cost edge-connectivity augmentation
    40th International Colloquium on Automata, Languages and Programming (ICALP 2013), 721-732, Lecture Notes in Comput. Sci., 7965, Springer, 2013.
    (with: László A. Végh)

  24. Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable.
    ACM Transaction on Algorithms, 11(4):28, 2015.
    (with: Rajesh Chitnis, Marek Cygan, and MohammadTaghi Hajiaghayi)

    Conference version:
    Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable.
    39th International Colloquium on Automata, Languages and Programming (ICALP 2012), 230-241, Lecture Notes in Comput. Sci., 7391, Springer, 2012..
    (with: Rajesh Chitnis, Marek Cygan, and MohammadTaghi Hajiaghayi)

  25. On the parameterized complexity of finding separators with non-hereditary properties.
    Algorithmica, 72(3):687-713, 2015.
    (with: Pinar Heggernes, Pim van 't Hof, Neeldhara Misra, and Yngve Villanger)

    Conference version:
    On the parameterized complexity of finding separators with non-hereditary properties.
    38th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2012), 332-343, Lecture Notes in Comput. Sci., 7551, Springer, 2012.
    (with: Pinar Heggernes, Pim van 't Hof, Neeldhara Misra, and Yngve Villanger)

    2014

  26. Constraint satisfaction parameterized by solution size.
    SIAM Journal on Computing, 43(2):355-388, 2014.
    (with: Andrei Bulatov)

    Conference version:
    Constraint satisfaction parameterized by solution size.
    38th International Colloquium on Automata, Languages and Programming (ICALP 2011), 424-436, Lecture Notes in Comput. Sci., 6755, Springer, 2011.
    (with: Andrei Bulatov)

  27. Fixed-parameter tractability of multicut parameterized by the size of the cutset.
    SIAM Journal on Computing, 43(2):355-388, 2014.
    (with: Igor Razgon)

    Conference version:
    Fixed-parameter tractability of multicut parameterized by the size of the cutset.
    In Proceedings of the 43rd annual ACM symposium on Theory of computing (STOC 2011), 469-478, 2011.
    (with: Igor Razgon)

  28. Exponential time complexity of the permanent and the Tutte polynomial.
    ACM Transactions on Algorithms, 10(4):21, 2014
    (with: Holger Dell, Thore Husfeldt, Nina Taslaman, Martin Wahlén)

  29. Constraint solving via fractional edge covers.
    ACM Transactions on Algorithms, 11(1):4, 2014.
    (with: Martin Grohe)

    Conference version:
    Constraint solving via fractional edge covers.
    In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), 289-298, 2006.
    (with: Martin Grohe)

  30. Minimizing Movement: Fixed-Parameter Tractability.
    ACM Transactions on Algorithms, 11(2):14, 2014.
    (with: Erik Demaine, MohammadTaghi Hajiaghayi)

    Conference version:
    Minimizing Movement: Fixed-Parameter Tractability.
    In Proceedings of the 17th European Symposium on Algorithms (ESA 2009), Lecture Notes in Comput. Sci., 5757, Springer, Berlin, 718-729, 2009.
    (with: Erik Demaine, MohammadTaghi Hajiaghayi)

  31. Immersions in highly edge connected graphs.
    SIAM Journal on Discrete Mathematics, 28(1):503-520, 2014
    (with: Paul Wollan)

  32. Parameterized complexity of Eulerian deletion problems.
    Algorithmica, 68(1):41-61, 2014
    (with: Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter)

    Conference version:
    Parameterized complexity of Eulerian deletion problems.
    37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2011), 131-142, Lecture Notes in Comput. Sci., 6986, Springer, Berlin, 2011.
    (with: Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter)

    2013

  33. Tractable hypergraph properties for constraint satisfaction and conjunctive queries.
    Journal of the ACM, 60(6):42, 2013.

    Conference version:
    Tractable hypergraph properties for constraint satisfaction and conjunctive queries.
    In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), 735-744.

  34. Size bounds and query plans for relational joins.
    SIAM Journal on Computing, 42(4):1737-1767, 2013.
    (with: Albert Atserias, Martin Grohe)

    Conference version:
    Size bounds and query plans for relational joins.
    In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), 739-748, 2008.
    (with: Albert Atserias, Martin Grohe)

  35. Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
    SIAM Journal on Computing, 42(4):1674-1696, 2013.
    (with: Rajesh Chitnis and MohammadTaghi Hajiaghayi)

    Conference version:
    Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
    In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), 1713-1725, 2012.
    (with: Rajesh Chitnis and MohammadTaghi Hajiaghayi)

  36. Finding small separators in linear time via treewidth reduction.
    ACM Transactions on Algorithms, 9(4):30, 2013.
    (with: Barry O'Sullivan, Igor Razgon)

    Conference version:
    Treewidth reduction for constrained separation and bipartization problems.
    27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010), 561-572, 2010.
    (with: Barry O'Sullivan, Igor Razgon)

  37. Cleaning interval graphs.
    Algorithmica, 65(2):275-316, 2013.
    (with: Ildikó Schlotter)

  38. Clustering with local restrictions.
    Information and Computation, 222:278-292, 2013.
    (with: Daniel Lokshtanov)

    Conference version:
    Clustering with local restrictions.
    38th International Colloquium on Automata, Languages and Programming (ICALP 2011), 785-797, Lecture Notes in Comput. Sci., 6755, Springer, 2011.
    (with: Daniel Lokshtanov)

  39. Completely inapproximable monotone and antimonotone parameterized problems.
    Journal of Computer and System Sciences, 79(1):144-151, 2013.

    Conference version:
    Completely inapproximable monotone and antimonotone parameterized problems.
    In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, Cambridge, Massachusetts, 181-187, 2010.

  40. Bin packing with fixed number of bins revisited.
    Journal of Computer and System Sciences, 79(1):39-49, 2013.
    (with: Klaus Jansen, Stefan Kratsch, Ildikó Schlotter)

    Conference version:
    Bin packing with fixed number of bins revisited.
    12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010), 260-271, Lecture Notes in Comput. Sci., 6139, Springer, Berlin, 2010.
    (with: Klaus Jansen, Stefan Kratsch, Ildikó Schlotter)

  41. A faster FPT algorithm for Bipartite Contraction.
    Information Processing Letters, 113(22-24):906-912, 2013.
    (with: Sylvain Guillemot)

    Conference version:
    A faster FPT algorithm for Bipartite Contraction.
    8th International Symposium on Parameterized and Exact Computation (IPEC 2013), 177-188, Lecture Notes in Comput. Sci., vol. 8246, Springer, 2013.
    (with: Sylvain Guillemot)

    2012

  42. The tractability of CSP classes defined by forbidden patterns.
    Journal of Artificial Intelligence Research, 45:47-78, 2012.
    (with: David Cohen, Martin Cooper, Páidí Creed, András Z. Salamon)

  43. On the hardness of losing weight.
    ACM Transactions on Algorithms, 8(2):19, 2012.
    (with: Andrei Krokhin)

    Conference version:
    On the hardness of losing weight.
    35rd International Colloquium on Automata, Languages and Programming (ICALP 2008), 662-673, Lecture Notes in Comput. Sci., 5125, Springer, Berlin, 2008.
    (with: Andrei Krokhin)

  44. Enumerating homomorphisms.
    Journal of Computer and System Sciences, 78(2):638-650, 2012.
    (with: Andrei Bulatov, Víctor Dalmau, Martin Grohe)

    Conference version:
    Enumerating homomorphisms.
    26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), 231-242, 2009.
    (with: Andrei Bulatov, Víctor Dalmau, Martin Grohe)

  45. Obtaining a planar graph by vertex deletion.
    Algorithmica, 62(3-4):807-822, 2012.
    (with: Ildikó Schlotter)

    Conference version:
    Obtaining a planar graph by vertex deletion.
    33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007), 292-303, Lecture Notes in Comput. Sci., 4769, Springer, Berlin, 2007.
    (with: Ildikó Schlotter)

    2011

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

    Conference version:
    Approximation schemes for Steiner Forest on planar graphs and graphs of bounded treewidth.
    In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), 211-220.
    (with: MohammadHossein Bateni, MohammadTaghi Hajiaghayi)

  47. Lower bounds based on the Exponential Time Hypothesis.
    Bulletin of the EATCS, 84, 41-71, 2011.
    (with: Daniel Lokshtanov and Saket Saurabh)

  48. Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension.
    ACM Transactions on Algorithms, 7(4):43 (2011)
    (with: Sergio Cabello, Panos Giannopoulos, Christian Knauer, Günter Rote)

  49. Sparse balanced partitions and the complexity of subgraph problems.
    SIAM J. Discrete Math., 25(2): 631-644, 2011
    (with: Noga Alon)

  50. Complexity of clique coloring and related problems.
    Theor. Comput. Sci., 412(29): 3487-3500, 2011.

  51. Soft Constraints of Difference and Equality.
    J. Artif. Intell. Res. (JAIR),, 41:97-130, 2011
    (with: Emmanuel Hebrard, Barry O'Sullivan, Igor Razgon)

    Conference version:
    Constraints of Difference and Equality: A Complete Taxonomic Characterisation.
    15th International Conference on Principles and Practice of Constraint Programming (CP 2009), 424-438, Lecture Notes in Comput. Sci., 5732, Springer, Berlin, 2009.
    (with: Emmanuel Hebrard, Barry O'Sullivan, Igor Razgon)

  52. Packing cycles through prescribed vertices.
    J. Comb. Theory, Ser. B 101(5): 378-381, 2011
    (with: Naonori Kakimura and Ken-ichi Kawarabayashi)

  53. Stable assignment with couples: parameterized complexity and local search.
    Discrete Optimization, 8(1):25-40, 2011.
    (with: Ildikó Schlotter)

    Conference version:
    Stable assignment with couples: parameterized complexity and local search.
    4nd International Workshop on Parameterized and Exact Computation (IWPEC 2009), 300-311, Lecture Notes in Comput. Sci., 5917, Springer, Berlin, 2009.
    (with: Ildikó Schlotter)

  54. Tractable structures for constraint satisfaction with truth tables.
    Theory of Computing Systems, 48:444-464, 2011.

    Conference version:
    Tractable structures for constraint satisfaction with truth tables.
    26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), 649-660, 2009.

    2010

  55. Can you beat treewidth?
    Theory of Computing, 6(1):85-112, 2010.

    Conference version:
    Can you beat treewidth?
    In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 169-179, 2007.

  56. Constraint Satisfaction Problems and Global Cardinality Constraints.
    Communications of the ACM, 53(9):99-106, 2010.
    (with: Andrei Bulatov)

  57. The complexity of global cardinality constraints.
    Logical Methods in Computer Science, Vol. 6 (4:4):1-27, 2010.
    (with: Andrei Bulatov)

    Conference version:
    The complexity of global cardinality constraints.
    In Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science (LICS 2009), 419-428, 2009.
    (with: Andrei Bulatov)

  58. Approximating fractional hypertree width.
    ACM Transactions on Algorithms, 6(2), Article 29, 2010.

    Conference version:
    Approximating fractional hypertree width.
    In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), 902-911, 2009.

  59. Parameterized complexity and local search approaches for the stable marriage problem with ties.
    Algorithmica, 58(1), 170-187, 2010.
    (with: Ildikó Schlotter)

  60. Computing Geometric Minimum-Dilation Graphs is NP-Hard.
    International Journal of Computational Geometry and Applications, 20(2), 147-173, 2010.
    (with: Panos Giannopoulos, Rolf Klein, Christian Knauer, Martin Kutz)

  61. Chordal deletion is fixed-parameter tractable.
    Algorithmica, 57(4), 747-768, 2010.

    Conference version:
    Chordal deletion is fixed-parameter tractable.
    32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2006), 37-48, Lecture Notes in Comput. Sci., 4271, Springer, Berlin, 2006.

    2009

  62. Parameterized graph cleaning problems.
    Discrete Applied Mathematics, 157(15):3258-3267, 2009.
    (with: Ildikó Schlotter)

    Conference version:
    Parameterized graph cleaning problems.
    34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2008), 287-289, Lecture Notes in Comput. Sci., 5344, Springer, Berlin, 2008.
    (with: Ildikó Schlotter)

  63. Constant ratio fixed-parameter approximation of the edge multicut problem.
    Information Processing Letters, 109(20):1161-1166, 2009.
    (with: Igor Razgon)

    Conference version:
    Constant ratio fixed-parameter approximation of the edge multicut problem.
    In Proceedings of the 17th European Symposium on Algorithms (ESA 2009), Lecture Notes in Comput. Sci., 5757, Springer, Berlin, 647-658, 2009.
    (with: Igor Razgon)

  64. A parameterized view on matroid optimization problems.
    Theoretical Computer Science, 410(44):4471-4479, 2009.

    Conference version:
    A parameterized view on matroid optimization problems.
    33rd International Colloquium on Automata, Languages and Programming (ICALP 2006), 656-667, Lecture Notes in Comput. Sci., 4051, Springer, Berlin, 2006.

  65. Complexity results for minimum sum edge coloring.
    Discrete Applied Mathematics, 157(5):1034-1045, 2009.

  66. On tree width, bramble size, and expansion.
    Journal of Combinatorial Theory Ser. B, 99(1):218-228, 2009
    (with: Martin Grohe)

  67. The complexity of nonrepetitive coloring.
    Discrete Applied Mathematics, 157(1):13-18, 2009
    (with: Marcus Schaefer)

    2008

  68. Closest substring problems with small distances.
    SIAM Journal on Computing, 38(4):1382-1410, 2008.

    Conference version:
    The Closest Substring problem with small distances.
    In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 63-72, 2005.

  69. Complexity of unique list colorability.
    Theoretical Computer Science, 401:62-76, 2008.

  70. Searching the k-change neighborhood for TSP is W[1]-hard.
    Operations Research Letters, 36(1):31-36, 2008.

  71. Parameterized complexity and approximation algorithms.
    The Computer Journal, 51(1):60-78, 2008.

    2006

  72. Minimum sum multicoloring on the edges of trees.
    Theoretical Computer Science, 361(2-3):133-149, 2006

    Conference version:
    Minimum sum multicoloring on the edges of trees.
    1st Workshop on Approximation and Online Algorithms (WAOA 2003), 214-226, Lecture Notes in Comput. Sci., 2909, Springer, Berlin, 2004.
    [Slides]

  73. Precoloring extension on unit interval graphs.
    Discrete Applied Mathematics, 154(6):995-1002, 2006

  74. The complexity of chromatic strength and chromatic edge strength.
    Computational Complexity, 14(4):308-340, 2006

  75. Parameterized coloring problems on chordal graphs.
    Theoretical Computer Science, 351(3):407-424, 2006

    Conference version:
    Parameterized coloring problems on chordal graphs.
    1st International Workshop on Parameterized and Exact Computation (IWPEC 2004), 83-95, Lecture Notes in Comput. Sci., 3162, Springer, Berlin, 2004.
    [Slides]

  76. Parameterized graph separation problems.
    Theoretical Computer Science, 351(3):394-406, 2006

    Conference version:
    Parameterized graph separation problems.
    1st International Workshop on Parameterized and Exact Computation (IWPEC 2004), 71-82, Lecture Notes in Comput. Sci., 3162, Springer, Berlin, 2004.
    [Slides]

    2005

  77. A short proof of the NP-completeness of minimum sum interval coloring.
    Operations Research Letters, 33(4):382-384, 2005

  78. NP-completeness of list coloring and precoloring extension on the edges of planar graphs.
    Journal of Graph Theory. 49(4):313-324, 2005

  79. Parameterized complexity of constraint satisfaction problems.
    Computational Complexity, 14(2):153-183, 2005

    Conference version:
    Parameterized complexity of constraint satisfaction problems.
    In Proceedings of 19th Annual IEEE Conference on Computational Complexity, Amherst, Massachusetts, 139-149, 2004.
    [Slides] [Slides of a longer talk]

    2004

  80. Graph coloring problems and their applications in scheduling.
    Periodica Polytechnica Ser. El. Eng. 48(1-2):5-10, 2004.

  81. Eulerian disjoint paths problem in grid graphs is NP-complete.
    Discrete Applied Mathematics, 143(1-3):336-341, 2004

  82. List edge multicoloring in graphs with few cycles.
    Information Processing Letters, 89(2):85-90, 2004.

    Conference version:
    List edge multicoloring in bounded cyclicity graphs.
    3rd Hungarian-Japanese Symposium on Discrete Mathematics and Its Application, Tokyo, 2002, 164-170
    [Slides]

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

    2014

  30. Complexity of counting subgraphs: Only the boundedness of the vertex-cover number counts.
    In Proceedings of the 55th Annual Symposium on Foundations of Computer Science (FOCS 2014), 130-139, 2014.
    (with: Radu Curticapean)

  31. Finding small patterns in permutations in linear time.
    In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), 82-101, 2014.
    (with: Sylvain Guillemot)

  32. A subexponential parameterized algorithm for Subset TSP on planar graphs.
    In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), 1812-1830, 2014.
    (with: Philip N. Klein)

  33. The limited blessing of low dimensionality: when 1-1/d is the best possible exponent for d-dimensional geometric problems.
    Proceedings of the 30th Annual Symposium on Computational Geometry (SoCG 2014), 67, 2014.
    (with: Anastasios Sidiropoulos)

  34. Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask).
    In Proceedings of 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 542-553, 2014.
    (with: Michal Pilipczuk)

    2013

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

    Full version:
    Technical Report, arXiv:1111.1109

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

  37. Kernelization of packing problems.
    In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), 68-81, 2012.
    (with: Holger Dell)

  38. Solving PLANAR k-TERMINAL CUT in O(nc√k) time.
    39th International Colloquium on Automata, Languages and Programming (ICALP 2012), 569-580, Lecture Notes in Comput. Sci., 7391, Springer, 2012.
    (with: Philip N. Klein)

  39. A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals.
    39th International Colloquium on Automata, Languages and Programming (ICALP 2012), 677-688, Lecture Notes in Comput. Sci., 7391, Springer, 2012.

    2011

  40. Important separators and parameterized algorithms (invited talk).
    37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2011), 5-10, Lecture Notes in Comput. Sci., 6986, Springer, Berlin, 2011.

  41. On guaranteeing polynomially bounded search tree size.
    17th International Conference on Principles and Practice of Constraint Programming (CP 2011), 160-171, Lecture Notes in Comput. Sci., 6876, Springer, Berlin, 2011.
    (with: David Cohen, Martin Cooper, Martin Green)

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

    Full version:
    Technical Report, arXiv:1011.1827

  43. Prize-collecting Steiner problems on planar graphs.
    In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), 1028-1049, 2011.
    (with: MohammadHossein Bateni, Chandra Checkuri, Alina R. Ene, MohammadTaghi Hajiaghayi, Nitish Korula)

    2010

  44. Parameterized complexity of the Arc-Preserving Subsequence problem
    36th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2010), 244-255, Lecture Notes in Comput. Sci., 6410, Springer, Berlin, 2010.
    (with: Ildikó Schlotter)

    2007

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

  46. Precoloring extension on chordal graphs.
    In A. Bondy, J. Fonlupt, J.-L. Fouquet, J.-C. Fournier, and J. Ramirez Alfonsin, editors, Graph Theory in Paris. Proceedings of a Conference in Memory of Claude Berge, Trends in Mathematics, pages 255--270. Birkhäuser, 2007.

    2006

  47. Parameterized complexity of independence and domination on geometric graphs.
    2nd International Workshop on Parameterized and Exact Computation (IWPEC 2006), 154-165, Lecture Notes in Comput. Sci., 4169, Springer, Berlin, 2006.

    2005

  48. Efficient approximation schemes for geometric problems?
    In Proceedings of 13th Annual European Symposium on Algorithms (ESA 2005), Lecture Notes in Comput. Sci., 3669, Springer, Berlin, 448-459, 2005.
    [Slides]

    2004

  49. Minimum sum multicoloring on the edges of planar graphs and partial k-trees.
    2nd Workshop on Approximation and Online Algorithms (WAOA 2004), 9-22, Lecture Notes in Comput. Sci., 3351, Springer, Berlin, 2005.
    [Slides]

    2002

  50. The complexity of tree multicolorings.
    Mathematical foundations of computer science (MFCS 2002), 532-542, Lecture Notes in Comput. Sci., 2420, Springer, Berlin, 2002.
    [Slides]

    2000

  51. Heuristic algorithms for joint configuration of the optical and electrical layer in multi-hop wavelength routing networks.
    IEEE INFOCOM 2000, 1000-1009.
    (with: Dániel Fogaras)

Papers appearing in edited volumes
    2020

  1. Four shorts stories on surprising algorithmic uses of treewidth.
    In Fomin, F.V., et al. (eds.) Treewidth, Kernels, and Algorithms. Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday. Lecture Notes in Comput. Sci., vol 12160, pp. 129-144, Springer, 2020.

    2012

  2. FPT suspects and tough customers: Open problems of Downey and Fellows.
    In Bodlaender, H.L., et al. (eds.) Fellows Festschrift. Lecture Notes in Comput. Sci., vol. 7370, pp. 457-468, Springer, 2012.
    (with:Fedor V. Fomin)

  3. What's Next? Future Directions in Parameterized Complexity.
    In Bodlaender, H.L., et al. (eds.) Fellows Festschrift. Lecture Notes in Comput. Sci., vol. 7370, pp. 469-496, Springer, 2012.

Volume editing
    2012

  1. The Multivariate Algorithmic Revolution and Beyond -- Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday.
    Hans L. Bodlaender, Rod Downey, Fedor V. Fomin, and Dániel Marx (eds.) Lecture Notes in Comput. Sci., vol. 7370, Springer, 2012.

  2. 6th International Symposium on Parameterized and Exact Computation (IPEC 2011)
    Dániel Marx and Peter Rossmanith (eds.) Lecture Notes in Comput. Sci., vol. 7112, Springer, 2012.

Manuscripts
  1. A short proof of the NP-completeness of circular arc coloring.
    Manuscript, 2003.

  2. Local Search.
    Parameterized Complexity Newletter, pages 7-8, Vol. 3, 2007.
Thesis
  1. Graph coloring with local and global constraints.
    PhD thesis, 2004.