# Dániel Marx

According to our database1, Dániel Marx authored at least 155 papers between 2000 and 2019.

Collaborative distances:
• Dijkstra number2 of four.
• Erdős number3 of two.

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2019
Introduction to the Special Issue on SODA 2017.
ACM Trans. Algorithms, 2019

Routing with congestion in acyclic digraphs.
Inf. Process. Lett., 2019

Parameterized Intractability of Even Set and Shortest Vector Problem.
Electronic Colloquium on Computational Complexity (ECCC), 2019

New Horizons in Parameterized Complexity (Dagstuhl Seminar 19041).
Dagstuhl Reports, 2019

Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions).
CoRR, 2019

Covering a tree with rooted subtrees.
CoRR, 2019

Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality is the Key to Single-Exponential Parameterized Algorithms.
Algorithmica, 2019

Subexponential-Time Algorithms for Maximum Independent Set in $$P_t$$ P t -Free and Broom-Free Graphs.
Algorithmica, 2019

Finding and Counting Permutations via CSPs.
Proceedings of the 14th International Symposium on Parameterized and Exact Computation, 2019

How Does Object Fatness Impact the Complexity of Packing in d Dimensions?
Proceedings of the 30th International Symposium on Algorithms and Computation, 2019

Parameterized Streaming Algorithms for Min-Ones d-SAT.
Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2019

Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs.
Proceedings of the 35th International Symposium on Computational Geometry, 2019

Parameterized Algorithms for Generalizations of Directed Feedback Vertex Set.
Proceedings of the Algorithms and Complexity - 11th International Conference, 2019

2018
Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal.
ACM Trans. Algorithms, 2018

Slightly Superexponential Parameterized Problems.
SIAM J. Comput., 2018

Fine-grained complexity of coloring unit disks and balls.
JoCG, 2018

Subexponential-time Algorithms for Maximum Independent Set in Pt-free and Broom-free Graphs.
CoRR, 2018

The Parameterized Hardness of the k-Center Problem in Transportation Networks.
Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Finding List Homomorphisms from Bounded-treewidth Graphs to Reflexive Graphs: a Complete Complexity Characterization.
Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

Covering a tree with rooted subtrees - parameterized and approximation algorithms.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Multi-Budgeted Directed Cuts.
Proceedings of the 13th International Symposium on Parameterized and Exact Computation, 2018

On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017
Coloring Graphs with Constraints on Connectivity.
Journal of Graph Theory, 2017

Rooted grid minors.
J. Comb. Theory, Ser. B, 2017

Hitting forbidden subgraphs in graphs of bounded treewidth.
Inf. Comput., 2017

List H-Coloring a Graph by Removing Few Vertices.
Algorithmica, 2017

Homomorphisms are a good basis for counting small subgraphs.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Parameterized and Approximation Results for Scheduling with a Low Rank Processing Time Matrix.
Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Graphs, Hypergraphs, and the Complexity of Conjunctive Database Queries (Invited Talk).
Proceedings of the 20th International Conference on Database Theory, 2017

Subexponential Parameterized Algorithms for Graphs of Polynomial Growth.
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016
Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems.
TOCT, 2016

On Problems as Hard as CNF-SAT.
ACM Trans. Algorithms, 2016

Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221).
Dagstuhl Reports, 2016

Chordal Editing is Fixed-Parameter Tractable.
Algorithmica, 2016

Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2016

The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems (Invited Talk).
Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

H-Free Graphs, Independent Sets, and Subexponential-Time Algorithms.
Proceedings of the 11th International Symposium on Parameterized and Exact Computation, 2016

Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Fixed-Parameter Approximability of Boolean MinCSPs.
Proceedings of the 24th Annual European Symposium on Algorithms, 2016

Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems.
Proceedings of the 32nd International Symposium on Computational Geometry, 2016

Constant-Factor Approximations for Asymmetric TSP on Nearly-Embeddable Graphs.
Proceedings of the Approximation, 2016

2015
Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation.
ACM Trans. Algorithms, 2015

Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable.
ACM Trans. Algorithms, 2015

Interval Deletion Is Fixed-Parameter Tractable.
ACM Trans. Algorithms, 2015

Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs.
SIAM J. Comput., 2015

The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301).
Dagstuhl Reports, 2015

Colouring graphs with constraints on connectivity.
CoRR, 2015

On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties.
Algorithmica, 2015

An exact characterization of tractable demand patterns for maximum disjoint path problems.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams.
Proceedings of the Algorithms - ESA 2015, 2015

Parameterized Algorithms
Springer, ISBN: 978-3-319-21275-3, 2015

2014
Constraint Solving via Fractional Edge Covers.
ACM Trans. Algorithms, 2014

Minimizing Movement: Fixed-Parameter Tractability.
ACM Trans. Algorithms, 2014

Exponential Time Complexity of the Permanent and the Tutte Polynomial.
ACM Trans. Algorithms, 2014

Immersions in Highly Edge Connected Graphs.
SIAM J. Discrete Math., 2014

Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset.
SIAM J. Comput., 2014

Constraint Satisfaction Parameterized by Solution Size.
SIAM J. Comput., 2014

Optimality and tight results in parameterized complexity (Dagstuhl Seminar 14451).
Dagstuhl Reports, 2014

Parameterized Complexity of Eulerian Deletion Problems.
Algorithmica, 2014

Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask).
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

A subexponential parameterized algorithm for Subset TSP on planar graphs.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Finding small patterns in permutations in linear time.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions).
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Complexity of Counting Subgraphs: Only the Boundedness of the Vertex-Cover Number Counts.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

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, 2014

2013
Finding small separators in linear time via treewidth reduction.
ACM Trans. Algorithms, 2013

Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset.
SIAM J. Comput., 2013

Size Bounds and Query Plans for Relational Joins.
SIAM J. Comput., 2013

Completely inapproximable monotone and antimonotone parameterized problems.
J. Comput. Syst. Sci., 2013

Bin packing with fixed number of bins revisited.
J. Comput. Syst. Sci., 2013

Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries.
J. ACM, 2013

A faster FPT algorithm for Bipartite Contraction.
Inf. Process. Lett., 2013

Clustering with local restrictions.
Inf. Comput., 2013

Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 13421).
Dagstuhl Reports, 2013

Cleaning Interval Graphs.
Algorithmica, 2013

Algorithmic Graph Structure Theory (Tutorial).
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

The Square Root Phenomenon in Planar Graphs.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Block-Sorted Quantified Conjunctive Queries.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

The Planar Directed K-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012
On the hardness of losing weight.
ACM Trans. Algorithms, 2012

Enumerating homomorphisms.
J. Comput. Syst. Sci., 2012

The Tractability of CSP Classes Defined by Forbidden Patterns.
J. Artif. Intell. Res., 2012

The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451).
Dagstuhl Reports, 2012

Data Reduction and Problem Kernels (Dagstuhl Seminar 12241).
Dagstuhl Reports, 2012

Obtaining a Planar Graph by Vertex Deletion.
Algorithmica, 2012

Kernelization of packing problems.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Randomized Techniques for Parameterized Algorithms.
Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012

A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

What's Next? Future Directions in Parameterized Complexity.
Proceedings of the Multivariate Algorithmic Revolution and Beyond, 2012

FPT Suspects and Tough Customers: Open Problems of Downey and Fellows.
Proceedings of the Multivariate Algorithmic Revolution and Beyond, 2012

2011
Complexity of clique coloring and related problems.
Theor. Comput. Sci., 2011

Geometric clustering: Fixed-parameter tractability and lower bounds with respect to the dimension.
ACM Trans. Algorithms, 2011

Sparse Balanced Partitions and the Complexity of Subgraph Problems.
SIAM J. Discrete Math., 2011

Tractable Structures for Constraint Satisfaction with Truth Tables.
Theory Comput. Syst., 2011

Packing cycles through prescribed vertices.
J. Comb. Theory, Ser. B, 2011

Soft Constraints of Difference and Equality.
J. Artif. Intell. Res., 2011

Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth.
J. ACM, 2011

Lower bounds based on the Exponential Time Hypothesis.
Bulletin of the EATCS, 2011

Stable assignment with couples: Parameterized complexity and local search.
Discret. Optim., 2011

On Problems as Hard as CNFSAT
CoRR, 2011

Important Separators and Parameterized Algorithms.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2011

Finding topological subgraphs is fixed-parameter tractable.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Prize-collecting Steiner Problems on Planar Graphs.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

On Guaranteeing Polynomially Bounded Search Tree Size.
Proceedings of the Principles and Practice of Constraint Programming - CP 2011, 2011

2010
Can You Beat Treewidth?
Theory of Computing, 2010

Approximating fractional hypertree width.
ACM Trans. Algorithms, 2010

Computing Geometric Minimum-Dilation Graphs is NP-Hard.
Int. J. Comput. Geometry Appl., 2010

The complexity of global cardinality constraints
Logical Methods in Computer Science, 2010

Prize-collecting Network Design on Planar Graphs
CoRR, 2010

Constraint satisfaction problems and global cardinality constraints.
Commun. ACM, 2010

Parameterized Complexity and Local Search Approaches for the Stable Marriage Problem with Ties.
Algorithmica, 2010

Chordal Deletion is Fixed-Parameter Tractable.
Algorithmica, 2010

Parameterized Complexity of the Arc-Preserving Subsequence Problem.
Proceedings of the Graph Theoretic Concepts in Computer Science, 2010

Treewidth Reduction for Constrained Separation and Bipartization Problems.
Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

2009
A parameterized view on matroid optimization problems.
Theor. Comput. Sci., 2009

On tree width, bramble size, and expansion.
J. Comb. Theory, Ser. B, 2009

Constant ratio fixed-parameter approximation of the edge multicut problem.
Inf. Process. Lett., 2009

Parameterized graph cleaning problems.
Discret. Appl. Math., 2009

The complexity of nonrepetitive coloring.
Discret. Appl. Math., 2009

Complexity results for minimum sum edge coloring.
Discret. Appl. Math., 2009

09511 Open Problems - Parameterized complexity and approximation algorithms.
Proceedings of the Parameterized complexity and approximation algorithms, 13.12., 2009

09511 Executive Summary - Parameterized complexity and approximation algorithms.
Proceedings of the Parameterized complexity and approximation algorithms, 13.12., 2009

09511 Abstracts Collection - Parameterized complexity and approximation algorithms.
Proceedings of the Parameterized complexity and approximation algorithms, 13.12., 2009

Constraints of Difference and Equality: A Complete Taxonomic Characterisation.
Proceedings of the Principles and Practice of Constraint Programming, 2009

2008
Complexity of unique list colorability.
Theor. Comput. Sci., 2008

Closest Substring Problems with Small Distances.
SIAM J. Comput., 2008

Searching the k-change neighborhood for TSP is W[1]-hard.
Oper. Res. Lett., 2008

Parameterized Complexity and Approximation Algorithms.
Comput. J., 2008

2007
On the Optimality of Planar and Geometric Approximation Schemes.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

07281 Open Problems -- Structure Theory and FPT Algorithmcs for Graphs, Digraphs and Hypergraphs.
Proceedings of the Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs, 08.07., 2007

07281 Abstracts Collection -- Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs.
Proceedings of the Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs, 08.07., 2007

2006
Minimum sum multicoloring on the edges of trees.
Theor. Comput. Sci., 2006

Parameterized coloring problems on chordal graphs.
Theor. Comput. Sci., 2006

Parameterized graph separation problems.
Theor. Comput. Sci., 2006

Precoloring extension on unit interval graphs.
Discret. Appl. Math., 2006

The complexity of chromatic strength and chromatic edge strength.
Computational Complexity, 2006

Parameterized Complexity of Independence and Domination on Geometric Graphs.
Proceedings of the Parameterized and Exact Computation, Second International Workshop, 2006

2005
A short proof of the NP-completeness of minimum sum interval coloring.
Oper. Res. Lett., 2005

NP-completeness of list coloring and precoloring extension on the edges of planar graphs.
Journal of Graph Theory, 2005

Parameterized complexity of constraint satisfaction problems.
Computational Complexity, 2005

The Closest Substring problem with small distances.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Efficient Approximation Schemes for Geometric Problems?.
Proceedings of the Algorithms, 2005

2004
List edge multicoloring in graphs with few cycles.
Inf. Process. Lett., 2004

Eulerian disjoint paths problem in grid graphs is NP-complete.
Discret. Appl. Math., 2004

Minimum Sum Multicoloring on the Edges of Planar Graphs and Partial k-Trees.
Proceedings of the Approximation and Online Algorithms, Second International Workshop, 2004

2003
Minimum Sum Multicoloring on the Edges of Trees: (Extended Abstract).
Proceedings of the Approximation and Online Algorithms, First International Workshop, 2003

2002
The Complexity of Tree Multicolorings.
Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

2000
Heuristic Algorithms for Joint Configuration of the Optical and Electrical Layer in Multi-Hop Wavelength Routing Networks.
Proceedings of the Proceedings IEEE INFOCOM 2000, 2000