Publications of Dániel Marx

Detailed list (with abstracts)

10 most important publications

List of research talks

DBLP

Journal papers:
To appear 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004
Conference papers without journal versions:
To appear 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000
Papers appearing in edited volumes:
2012
Volume editing:
2012
Manuscripts

Journal papers

To appear
50. Constraint solving via fractional edge covers.
    To appear in ACM Transactions on Algorithms.
    (with: Martin Grohe)
    [pdf] [BibTeX] [Google search]
    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)
    [pdf] [BibTeX] [Google search]

49. Finding small separators in linear time via treewidth reduction.
    To appear in ACM Transactions on Algorithms.
    (with: Barry O'Sullivan, Igor Razgon)
    [pdf] [BibTeX] [Google search]
    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)
    [pdf] [BibTeX] [Google search]

48. Exponential time complexity of the permanent and the Tutte polynomial.
    To appear in ACM Transactions on Algorithms.
    (with: Holger Dell, Thore Husfeldt, Nina Taslaman, Martin Wahlén)
    [pdf] [BibTeX] [Google search]

47. Minimizing Movement: Fixed-Parameter Tractability.
    To appear in ACM Transactions on Algorithms.
    (with: Erik Demaine, MohammadTaghi Hajiaghayi)
    [pdf] [BibTeX] [Google search]
    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)
    [pdf] [BibTeX] [Google search] [Publisher's version]

46. Cleaning interval graphs.
    To appear in Algorithmica.
    (with: Ildikó Schlotter)
    [pdf] [BibTeX] [Google search]

45. Parameterized complexity of Eulerian deletion problems.
    To appear in Algorithmica.
    (with: Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter)
    [pdf] [BibTeX] [Google search]
    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)
    [pdf] [BibTeX] [Google search] [Publisher's version]

    2013

44. Clustering with local restrictions.
    Information and Computation, 222:278-292, 2013.
    (with: Daniel Lokshtanov)
    [pdf] [BibTeX] [Google search] [Publisher's version]
    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)
    [pdf] [BibTeX] [Google search] [Publisher's version]

43. Completely inapproximable monotone and antimonotone parameterized problems.
    Journal of Computer and System Sciences, 79(1):144-151, 2013.
    [pdf] [BibTeX] [Google search]
    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.
    [pdf] [BibTeX] [Google search]

42. 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)
    [pdf] [BibTeX] [Google search]
    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)
    [pdf] [BibTeX] [Google search]

    2012

41. 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)
    [pdf] [BibTeX] [Google search]

40. On the hardness of losing weight.
    ACM Transactions on Algorithms, 8(2):19, 2012.
    (with: Andrei Krokhin)
    [pdf] [BibTeX] [Google search] [Publisher's version]
    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)
    [pdf] [BibTeX] [Google search] [Publisher's version]

39. Enumerating homomorphisms.
    Journal of Computer and System Sciences, 78(2):638-650, 2012.
    (with: Andrei Bulatov, Víctor Dalmau, Martin Grohe)
    [pdf] [BibTeX] [Google search] [Publisher's version]
    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)
    [pdf] [BibTeX] [Google search] [Publisher's version]

38. Obtaining a planar graph by vertex deletion.
    Algorithmica, 62(3-4):807-822, 2012.
    (with: Ildikó Schlotter)
    [pdf] [BibTeX] [Google search]
    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)
    [pdf] [BibTeX] [Google search] [Publisher's version]
    2011

37. 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)
    [pdf] [BibTeX] [Google search]
    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)
    [pdf] [BibTeX] [Google search]

36. Lower bounds based on the Exponential Time Hypothesis.
    Bulletin of the EATCS, 84, 41-71, 2011.
    (with: Daniel Lokshtanov and Saket Saurabh)
    [pdf] [BibTeX] [Google search] [Publisher's version]

35. 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)
    [pdf] [BibTeX] [Google search] [Publisher's version]

34. Sparse balanced partitions and the complexity of subgraph problems.
    SIAM J. Discrete Math., 25(2): 631-644, 2011
    (with: Noga Alon)
    [pdf] [BibTeX] [Google search] [Publisher's version]

33. Complexity of clique coloring and related problems.
    Theor. Comput. Sci., 412(29): 3487-3500, 2011.
    [pdf] [BibTeX] [Google search] [Publisher's version]

32. Soft Constraints of Difference and Equality.
    J. Artif. Intell. Res. (JAIR),, 41:97-130, 2011
    (with: Emmanuel Hebrard, Barry O'Sullivan, Igor Razgon)
    [pdf] [BibTeX] [Google search] [Publisher's version]
    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)
    [pdf] [BibTeX] [Google search] [Publisher's version]

31. Packing cycles through prescribed vertices.
    J. Comb. Theory, Ser. B 101(5): 378-381, 2011
    (with: Naonori Kakimura and Ken-ichi Kawarabayashi)
    [pdf] [BibTeX] [Google search] [Publisher's version]

30. Stable assignment with couples: parameterized complexity and local search.
    Discrete Optimization, 8(1):25-40, 2011.
    (with: Ildikó Schlotter)
    [pdf] [BibTeX] [Google search] [Publisher's version]
    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)
    [pdf] [BibTeX] [Google search] [Publisher's version]

29. Tractable structures for constraint satisfaction with truth tables.
    Theory of Computing Systems, 48:444-464, 2011.
    [pdf] [BibTeX] [Google search] [Publisher's version]
    Conference version:

    Tractable structures for constraint satisfaction with truth tables.

    26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), 649-660, 2009.
    [pdf] [BibTeX] [Google search] [Publisher's version]
    2010

28. Can you beat treewidth?
    Theory of Computing, 6(1):85-112, 2010.
    [pdf] [BibTeX] [Google search] [Publisher's version]
    Conference version:

    Can you beat treewidth?

    In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 169-179, 2007.
    [pdf] [BibTeX] [Google search] [Publisher's version]

27. Constraint Satisfaction Problems and Global Cardinality Constraints.
    Communications of the ACM, 53(9):99-106, 2010.
    (with: Andrei Bulatov)
    [pdf] [BibTeX] [Google search] [Publisher's version]

26. The complexity of global cardinality constraints.
    Logical Methods in Computer Science, Vol. 6 (4:4):1-27, 2010.
    (with: Andrei Bulatov)
    [pdf] [BibTeX] [Google search] [Publisher's version]
    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)
    [pdf] [BibTeX] [Google search] [Publisher's version]

25. Approximating fractional hypertree width.
    ACM Transactions on Algorithms, 6(2), Article 29, 2010.
    [pdf] [BibTeX] [Google search] [Publisher's version]
    Conference version:

    Approximating fractional hypertree width.

    In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), 902-911, 2009.
    [pdf] [BibTeX] [Google search] [Publisher's version]

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

23. 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)
    [pdf] [BibTeX] [Google search] [Publisher's version]

22. Chordal deletion is fixed-parameter tractable.
    Algorithmica, 57(4), 747-768, 2010.
    [pdf] [BibTeX] [Google search] [Publisher's version]
    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.
    [pdf] [BibTeX] [Google search] [Publisher's version]
    2009

21. Parameterized graph cleaning problems.
    Discrete Applied Mathematics, 157(15):3258-3267, 2009.
    (with: Ildikó Schlotter)
    [pdf] [BibTeX] [Google search] [Publisher's version]
    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)
    [pdf] [BibTeX] [Google search] [Publisher's version]

20. Constant ratio fixed-parameter approximation of the edge multicut problem.
    Information Processing Letters, 109(20):1161-1166, 2009.
    (with: Igor Razgon)
    [pdf] [BibTeX] [Google search] [Publisher's version]
    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)
    [pdf] [BibTeX] [Google search] [Publisher's version]

19. A parameterized view on matroid optimization problems.
    Theoretical Computer Science, 410(44):4471-4479, 2009.
    [pdf] [BibTeX] [Google search] [Publisher's version]
    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.
    [pdf] [BibTeX] [Google search]

18. Complexity results for minimum sum edge coloring.
    Discrete Applied Mathematics, 157(5):1034-1045, 2009.
    [pdf] [BibTeX] [Google search] [Publisher's version]

17. On tree width, bramble size, and expansion.
    Journal of Combinatorial Theory Ser. B, 99(1):218-228, 2009
    (with: Martin Grohe)
    [pdf] [BibTeX] [Google search] [Publisher's version]

16. The complexity of nonrepetitive coloring.
    Discrete Applied Mathematics, 157(1):13-18, 2009
    (with: Marcus Schaefer)
    [pdf] [BibTeX] [Google search] [Publisher's version]
    2008

15. Closest substring problems with small distances.
    SIAM Journal on Computing, 38(4):1382-1410, 2008.
    [pdf] [BibTeX] [Google search] [Publisher's version]
    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.
    [pdf] [BibTeX] [Google search] [Publisher's version]

14. Complexity of unique list colorability.
    Theoretical Computer Science, 401:62-76, 2008.
    [pdf] [BibTeX] [Google search] [Publisher's version]

13. Searching the k-change neighborhood for TSP is W[1]-hard.
    Operations Research Letters, 36(1):31-36, 2008.
    [pdf] [BibTeX] [Google search] [Publisher's version]

12. Parameterized complexity and approximation algorithms.
    The Computer Journal, 51(1):60-78, 2008.
    [pdf] [BibTeX] [Google search] [Publisher's version]
    2006

11. Minimum sum multicoloring on the edges of trees.
    Theoretical Computer Science, 361(2-3):133-149, 2006
    [pdf] [BibTeX] [Google search]
    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.
    [pdf] [BibTeX] [Slides] [Google search] [Publisher's version]

10. Precoloring extension on unit interval graphs.
    Discrete Applied Mathematics, 154(6):995-1002, 2006
    [pdf] [BibTeX] [Google search] [Publisher's version]

9. The complexity of chromatic strength and chromatic edge strength.
   Computational Complexity, 14(4):308-340, 2006
   [pdf] [BibTeX] [Google search] [Publisher's version]

8. Parameterized coloring problems on chordal graphs.
   Theoretical Computer Science, 351(3):407-424, 2006
   [pdf] [BibTeX]
   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.
   [pdf] [BibTeX] [Slides] [Google search] [Publisher's version]

7. Parameterized graph separation problems.
   Theoretical Computer Science, 351(3):394-406, 2006
   [pdf] [BibTeX]
   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.
   [pdf] [BibTeX] [Slides] [Google search] [Publisher's version]
   2005

6. A short proof of the NP-completeness of minimum sum interval coloring.
   Operations Research Letters, 33(4):382-384, 2005
   [pdf] [BibTeX] [Google search] [Publisher's version]

5. NP-completeness of list coloring and precoloring extension on the edges of planar graphs.
   Journal of Graph Theory. 49(4):313-324, 2005
   [pdf] [BibTeX] [Google search] [Publisher's version]

4. Parameterized complexity of constraint satisfaction problems.
   Computational Complexity, 14(2):153-183, 2005
   [pdf] [BibTeX] [Google search] [Publisher's version]
   Conference version:

   Parameterized complexity of constraint satisfaction problems.

   In Proceedings of 19th Annual IEEE Conference on Computational Complexity, Amherst, Massachusetts, 139-149, 2004.
   [pdf] [BibTeX] [Slides] [Slides of a longer talk] [Google search] [Publisher's version]
   2004

3. Graph coloring problems and their applications in scheduling.
   Periodica Polytechnica Ser. El. Eng. 48(1-2):5-10, 2004.
   [pdf] [BibTeX] [Google search]

2. Eulerian disjoint paths problem in grid graphs is NP-complete.
   Discrete Applied Mathematics, 143(1-3):336-341, 2004
   [pdf] [BibTeX] [Google search] [Publisher's version]

1. List edge multicoloring in graphs with few cycles.
   Information Processing Letters, 89(2):85-90, 2004.
   [pdf] [BibTeX] [Google search] [Publisher's version]
   Conference version:

   List edge multicoloring in bounded cyclicity graphs.

   3rd Hungarian-Japanese Symposium on Discrete Mathematics and Its Application, Tokyo, 2002, 164-170
   [pdf] [BibTeX] [Slides] [Google search]

Conference papers without journal versions

2012
27. 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)
    [pdf] [BibTeX] [Google search]
    Full version:

    Technical Report, arXiv:1111.1109
    [Publisher's version]

26. 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)
    [pdf] [BibTeX] [Google search]
    Full version:

    Technical Report, arXiv:1110.0259
    [Publisher's version]

25. Kernelization of packing problems.
    In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), 68-81, 2012.
    (with: Holger Dell)
    [pdf] [BibTeX] [Google search]

24. Solving PLANAR k-TERMINAL CUT in O(n^c√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)
    [pdf] [BibTeX] [Google search]

23. 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.
    [pdf] [BibTeX] [Google search]

22. 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)
    [pdf] [BibTeX] [Google search]
    Full version:

    Technical Report, arXiv:1205.1271
    [Publisher's version]

21. 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)
    [pdf] [BibTeX] [Google search]
    Full version:

    Technical Report, arXiv:1112.2275
    [Publisher's version]

20. 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)
    [pdf] [BibTeX] [Google search]
    2011

19. 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)
    [pdf] [BibTeX] [Google search] [Publisher's version]
    Full version:

    Technical Report, arXiv:1206.4854
    [Publisher's version]

18. 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.
    [pdf] [BibTeX] [Google search]

17. 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)
    [pdf] [BibTeX] [Google search]

16. 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)
    [pdf] [BibTeX] [Google search] [Publisher's version]
    Full version:

    Technical Report, arXiv:1010.3633
    [Publisher's version]

15. 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)
    [pdf] [BibTeX] [Google search]
    Full version:

    Technical Report, arXiv:1011.1827
    [Publisher's version]

14. 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)
    [pdf] [BibTeX] [Google search]
    Full version:

    Technical Report, arXiv:1007.5450
    [Publisher's version]
13. 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)
    [pdf] [BibTeX] [Google search]

12. 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)
    [pdf] [BibTeX] [Google search]
    2010

11. 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)
    [pdf] [BibTeX] [Google search] [Publisher's version]

10. 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)
    [pdf] [BibTeX] [Google search]

9. Tractable hypergraph properties for constraint satisfaction and conjunctive queries.
   In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), 735-744.
   [pdf] [BibTeX] [Google search]
   Full version:

   Technical Report, arXiv:0911.0801
   [Publisher's version]
   2008

8. 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)
   [pdf] [BibTeX] [Google search]
   Full version:

   [pdf] [BibTeX] [Google search]
   2007

7. 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.
   [pdf] [BibTeX] [Google search]

6. 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.
   [pdf] [BibTeX] [Google search] [Publisher's version]
   2006

5. 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.
   [pdf] [BibTeX] [Google search]
   2005

4. 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.
   [pdf] [BibTeX] [Slides] [Google search] [Publisher's version]
   2004

3. 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.
   [pdf] [BibTeX] [Slides] [Google search] [Publisher's version]
   
   2002

2. The complexity of tree multicolorings.
   Mathematical foundations of computer science (MFCS 2002), 532-542, Lecture Notes in Comput. Sci., 2420, Springer, Berlin, 2002.
   [pdf] [BibTeX] [Slides] [Google search] [Publisher's version]
   2000

1. Heuristic algorithms for joint configuration of the optical and electrical layer in multi-hop wavelength routing networks.
   IEEE INFOCOM 2000, 1000-1009.
   (with: Tibor Cinkler, Claus Popp Larsen, Dániel Fogaras)
   [pdf] [BibTeX] [Google search] [Publisher's version]

Papers appearing in edited volumes

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)
   [pdf] [BibTeX] [Google search] [Publisher's version]

1. 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.
   [pdf] [BibTeX] [Google search] [Publisher's version]

Volume editing

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

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

2. A short proof of the NP-completeness of circular arc coloring.
   Manuscript, 2003.
   [pdf] [BibTeX] [Google search]

1. Local Search.
   Parameterized Complexity Newletter, pages 7-8, Vol. 3, 2007.
   [pdf] [BibTeX] [Publisher's version]

Thesis

1. Graph coloring with local and global constraints.
   PhD thesis, 2004.
   [pdf] [BibTeX] [Google search]