Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Barış Can Esmer, Jacob Focke, Dániel Marx, and Paweł Rzążewski. List Homomorphisms by Deleting Edges and Vertices: Tight Complexity Bounds for Bounded-Treewidth Graphs. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 39:1-39:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{canesmer_et_al:LIPIcs.ESA.2024.39, author = {Can Esmer, Bar{\i}\c{s} and Focke, Jacob and Marx, D\'{a}niel and Rz\k{a}\.{z}ewski, Pawe{\l}}, title = {{List Homomorphisms by Deleting Edges and Vertices: Tight Complexity Bounds for Bounded-Treewidth Graphs}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {39:1--39:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.39}, URN = {urn:nbn:de:0030-drops-211103}, doi = {10.4230/LIPIcs.ESA.2024.39}, annote = {Keywords: Graph Homomorphism, List Homomorphism, Vertex Deletion, Edge Deletion, Multiway Cut, Parameterized Complexity, Tight Bounds, Treewidth, SETH} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Jacob Focke, Fabian Frei, Shaohua Li, Dániel Marx, Philipp Schepper, Roohani Sharma, and Karol Węgrzycki. Hitting Meets Packing: How Hard Can It Be?. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 55:1-55:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{focke_et_al:LIPIcs.ESA.2024.55, author = {Focke, Jacob and Frei, Fabian and Li, Shaohua and Marx, D\'{a}niel and Schepper, Philipp and Sharma, Roohani and W\k{e}grzycki, Karol}, title = {{Hitting Meets Packing: How Hard Can It Be?}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {55:1--55:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.55}, URN = {urn:nbn:de:0030-drops-211261}, doi = {10.4230/LIPIcs.ESA.2024.55}, annote = {Keywords: Hitting, Packing, Covering, Parameterized Algorithms, Lower Bounds, Treewidth} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Fateme Abbasi, Sandip Banerjee, Jarosław Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, and Joachim Spoerhase. Parameterized Approximation For Robust Clustering in Discrete Geometric Spaces. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{abbasi_et_al:LIPIcs.ICALP.2024.6, author = {Abbasi, Fateme and Banerjee, Sandip and Byrka, Jaros{\l}aw and Chalermsook, Parinya and Gadekar, Ameet and Khodamoradi, Kamyar and Marx, D\'{a}niel and Sharma, Roohani and Spoerhase, Joachim}, title = {{Parameterized Approximation For Robust Clustering in Discrete Geometric Spaces}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {6:1--6:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.6}, URN = {urn:nbn:de:0030-drops-201494}, doi = {10.4230/LIPIcs.ICALP.2024.6}, annote = {Keywords: Clustering, approximation algorithms, parameterized complexity} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Barış Can Esmer, Jacob Focke, Dániel Marx, and Paweł Rzążewski. Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{canesmer_et_al:LIPIcs.ICALP.2024.34, author = {Can Esmer, Bar{\i}\c{s} and Focke, Jacob and Marx, D\'{a}niel and Rz\k{a}\.{z}ewski, Pawe{\l}}, title = {{Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {34:1--34:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.34}, URN = {urn:nbn:de:0030-drops-201772}, doi = {10.4230/LIPIcs.ICALP.2024.34}, annote = {Keywords: Parameterized Complexity, Tight Bounds, Hub, Treewidth, Strong Exponential Time Hypothesis, Vertex Coloring, Vertex Deletion, Edge Deletion, Triangle Packing, Triangle Partition, Set Cover Hypothesis, Dominating Set} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Esther Galby, Sándor Kisfaludi-Bak, Dániel Marx, and Roohani Sharma. Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 67:1-67:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{galby_et_al:LIPIcs.ICALP.2024.67, author = {Galby, Esther and Kisfaludi-Bak, S\'{a}ndor and Marx, D\'{a}niel and Sharma, Roohani}, title = {{Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {67:1--67:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.67}, URN = {urn:nbn:de:0030-drops-202104}, doi = {10.4230/LIPIcs.ICALP.2024.67}, annote = {Keywords: Directed Steiner Network, Sub-exponential algorithm} }
Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
Jacob Focke, Florian Hörsch, Shaohua Li, and Dániel Marx. Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{focke_et_al:LIPIcs.SoCG.2024.57, author = {Focke, Jacob and H\"{o}rsch, Florian and Li, Shaohua and Marx, D\'{a}niel}, title = {{Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {57:1--57:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-316-4}, ISSN = {1868-8969}, year = {2024}, volume = {293}, editor = {Mulzer, Wolfgang and Phillips, Jeff M.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.57}, URN = {urn:nbn:de:0030-drops-200021}, doi = {10.4230/LIPIcs.SoCG.2024.57}, annote = {Keywords: MultiCut, Multiway Cut, Parameterized Complexity, Tight Bounds, Embedded Graph, Planar Graph, Genus, Surface, Exponential Time Hypothesis} }
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Barış Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, and Roohani Sharma. Approximate Monotone Local Search for Weighted Problems. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 17:1-17:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{esmer_et_al:LIPIcs.IPEC.2023.17, author = {Esmer, Bar{\i}\c{s} Can and Kulik, Ariel and Marx, D\'{a}niel and Neuen, Daniel and Sharma, Roohani}, title = {{Approximate Monotone Local Search for Weighted Problems}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {17:1--17:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-305-8}, ISSN = {1868-8969}, year = {2023}, volume = {285}, editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.17}, URN = {urn:nbn:de:0030-drops-194360}, doi = {10.4230/LIPIcs.IPEC.2023.17}, annote = {Keywords: parameterized approximations, exponential approximations, monotone local search} }
Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Barış Can Esmer, Ariel Kulik, Dániel Marx, Philipp Schepper, and Karol Węgrzycki. Computing Generalized Convolutions Faster Than Brute Force. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{esmer_et_al:LIPIcs.IPEC.2022.12, author = {Esmer, Bar{\i}\c{s} Can and Kulik, Ariel and Marx, D\'{a}niel and Schepper, Philipp and W\k{e}grzycki, Karol}, title = {{Computing Generalized Convolutions Faster Than Brute Force}}, booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, pages = {12:1--12:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-260-0}, ISSN = {1868-8969}, year = {2022}, volume = {249}, editor = {Dell, Holger and Nederlof, Jesper}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.12}, URN = {urn:nbn:de:0030-drops-173685}, doi = {10.4230/LIPIcs.IPEC.2022.12}, annote = {Keywords: Generalized Convolution, Fast Fourier Transform, Fast Subset Convolution} }
Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Esther Galby, Dániel Marx, Philipp Schepper, Roohani Sharma, and Prafullkumar Tale. Domination and Cut Problems on Chordal Graphs with Bounded Leafage. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 14:1-14:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{galby_et_al:LIPIcs.IPEC.2022.14, author = {Galby, Esther and Marx, D\'{a}niel and Schepper, Philipp and Sharma, Roohani and Tale, Prafullkumar}, title = {{Domination and Cut Problems on Chordal Graphs with Bounded Leafage}}, booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, pages = {14:1--14:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-260-0}, ISSN = {1868-8969}, year = {2022}, volume = {249}, editor = {Dell, Holger and Nederlof, Jesper}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.14}, URN = {urn:nbn:de:0030-drops-173704}, doi = {10.4230/LIPIcs.IPEC.2022.14}, annote = {Keywords: Chordal Graphs, Leafage, FPT Algorithms, Dominating Set, MultiCut with Undeletable Terminals, Multiway Cut with Undeletable Terminals} }
Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Dániel Marx, Govind S. Sankar, and Philipp Schepper. Anti-Factor Is FPT Parameterized by Treewidth and List Size (But Counting Is Hard). In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 22:1-22:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{marx_et_al:LIPIcs.IPEC.2022.22, author = {Marx, D\'{a}niel and Sankar, Govind S. and Schepper, Philipp}, title = {{Anti-Factor Is FPT Parameterized by Treewidth and List Size (But Counting Is Hard)}}, booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, pages = {22:1--22:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-260-0}, ISSN = {1868-8969}, year = {2022}, volume = {249}, editor = {Dell, Holger and Nederlof, Jesper}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.22}, URN = {urn:nbn:de:0030-drops-173780}, doi = {10.4230/LIPIcs.IPEC.2022.22}, annote = {Keywords: Anti-Factor, General Factor, Treewidth, Representative Sets, SETH} }
Published in: Dagstuhl Reports, Volume 12, Issue 5 (2022)
Martin Grohe, Venkatesan Guruswami, Dániel Marx, and Stanislav Živný. The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201). In Dagstuhl Reports, Volume 12, Issue 5, pp. 112-130, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@Article{grohe_et_al:DagRep.12.5.112, author = {Grohe, Martin and Guruswami, Venkatesan and Marx, D\'{a}niel and \v{Z}ivn\'{y}, Stanislav}, title = {{The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201)}}, pages = {112--130}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2022}, volume = {12}, number = {5}, editor = {Grohe, Martin and Guruswami, Venkatesan and Marx, D\'{a}niel and \v{Z}ivn\'{y}, Stanislav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.5.112}, URN = {urn:nbn:de:0030-drops-174453}, doi = {10.4230/DagRep.12.5.112}, annote = {Keywords: Constraint satisfaction problem (CSP); Computational complexity; Hardness of approximation; Universal algebra; Semidefinite programming} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Barış Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, and Roohani Sharma. Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 50:1-50:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{esmer_et_al:LIPIcs.ESA.2022.50, author = {Esmer, Bar{\i}\c{s} Can and Kulik, Ariel and Marx, D\'{a}niel and Neuen, Daniel and Sharma, Roohani}, title = {{Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {50:1--50:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.50}, URN = {urn:nbn:de:0030-drops-169887}, doi = {10.4230/LIPIcs.ESA.2022.50}, annote = {Keywords: parameterized approximations, exponential approximations, monotone local search} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Karl Bringmann, Sándor Kisfaludi‑Bak, Marvin Künnemann, Dániel Marx, and André Nusser. Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bringmann_et_al:LIPIcs.SoCG.2022.20, author = {Bringmann, Karl and Kisfaludi‑Bak, S\'{a}ndor and K\"{u}nnemann, Marvin and Marx, D\'{a}niel and Nusser, Andr\'{e}}, title = {{Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {20:1--20:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-227-3}, ISSN = {1868-8969}, year = {2022}, volume = {224}, editor = {Goaoc, Xavier and Kerber, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.20}, URN = {urn:nbn:de:0030-drops-160287}, doi = {10.4230/LIPIcs.SoCG.2022.20}, annote = {Keywords: Dynamic Time Warping, Sequence Similarity Measures} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Dániel Marx, Govind S. Sankar, and Philipp Schepper. 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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 95:1-95:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{marx_et_al:LIPIcs.ICALP.2021.95, author = {Marx, D\'{a}niel and Sankar, Govind S. and Schepper, Philipp}, title = {{Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {95:1--95:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.95}, URN = {urn:nbn:de:0030-drops-141647}, doi = {10.4230/LIPIcs.ICALP.2021.95}, annote = {Keywords: General Factor, General Matching, Treewidth, Cutwidth} }
Published in: LIPIcs, Volume 192, 2nd Symposium on Foundations of Responsible Computing (FORC 2021)
Vincent Cohen-Addad, Philip N. Klein, Dániel Marx, Archer Wheeler, and Christopher Wolfram. On the Computational Tractability of a Geographic Clustering Problem Arising in Redistricting. In 2nd Symposium on Foundations of Responsible Computing (FORC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 192, pp. 3:1-3:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{cohenaddad_et_al:LIPIcs.FORC.2021.3, author = {Cohen-Addad, Vincent and Klein, Philip N. and Marx, D\'{a}niel and Wheeler, Archer and Wolfram, Christopher}, title = {{On the Computational Tractability of a Geographic Clustering Problem Arising in Redistricting}}, booktitle = {2nd Symposium on Foundations of Responsible Computing (FORC 2021)}, pages = {3:1--3:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-187-0}, ISSN = {1868-8969}, year = {2021}, volume = {192}, editor = {Ligett, Katrina and Gupta, Swati}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2021.3}, URN = {urn:nbn:de:0030-drops-138718}, doi = {10.4230/LIPIcs.FORC.2021.3}, annote = {Keywords: redistricting, algorithms, planar graphs, lower bounds} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Dániel Marx. Chordless Cycle Packing Is Fixed-Parameter Tractable. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 71:1-71:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{marx:LIPIcs.ESA.2020.71, author = {Marx, D\'{a}niel}, title = {{Chordless Cycle Packing Is Fixed-Parameter Tractable}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {71:1--71:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.71}, URN = {urn:nbn:de:0030-drops-129373}, doi = {10.4230/LIPIcs.ESA.2020.71}, annote = {Keywords: chordal graphs, packing, fixed-parameter tractability} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Dániel Marx and R. B. Sandeep. Incompressibility of H-Free Edge Modification Problems: Towards a Dichotomy. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 72:1-72:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{marx_et_al:LIPIcs.ESA.2020.72, author = {Marx, D\'{a}niel and Sandeep, R. B.}, title = {{Incompressibility of H-Free Edge Modification Problems: Towards a Dichotomy}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {72:1--72:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.72}, URN = {urn:nbn:de:0030-drops-129383}, doi = {10.4230/LIPIcs.ESA.2020.72}, annote = {Keywords: incompressibility, edge modification problems, H-free graphs} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Marvin Künnemann and Dániel Marx. Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-Grained Perspective into Boolean Constraint Satisfaction. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 27:1-27:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kunnemann_et_al:LIPIcs.CCC.2020.27, author = {K\"{u}nnemann, Marvin and Marx, D\'{a}niel}, title = {{Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-Grained Perspective into Boolean Constraint Satisfaction}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {27:1--27:28}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.27}, URN = {urn:nbn:de:0030-drops-125791}, doi = {10.4230/LIPIcs.CCC.2020.27}, annote = {Keywords: Fine-grained complexity theory, algorithmic classification theorem, multivariate algorithms and complexity, constraint satisfaction problems, satisfiability} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Alexander Göke, Dániel Marx, and Matthias Mnich. Hitting Long Directed Cycles Is Fixed-Parameter Tractable. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 59:1-59:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{goke_et_al:LIPIcs.ICALP.2020.59, author = {G\"{o}ke, Alexander and Marx, D\'{a}niel and Mnich, Matthias}, title = {{Hitting Long Directed Cycles Is Fixed-Parameter Tractable}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {59:1--59:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.59}, URN = {urn:nbn:de:0030-drops-124664}, doi = {10.4230/LIPIcs.ICALP.2020.59}, annote = {Keywords: Directed graphs, directed feedback vertex set, circumference} }
Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Benjamin Aram Berendsohn, László Kozma, and Dániel Marx. Finding and Counting Permutations via CSPs. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{berendsohn_et_al:LIPIcs.IPEC.2019.1, author = {Berendsohn, Benjamin Aram and Kozma, L\'{a}szl\'{o} and Marx, D\'{a}niel}, title = {{Finding and Counting Permutations via CSPs}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {1:1--1:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.1}, URN = {urn:nbn:de:0030-drops-114627}, doi = {10.4230/LIPIcs.IPEC.2019.1}, annote = {Keywords: permutations, pattern matching, constraint satisfaction, exponential time} }
Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Akanksha Agrawal, Arindam Biswas, Édouard Bonnet, Nick Brettell, Radu Curticapean, Dániel Marx, Tillmann Miltzow, Venkatesh Raman, and Saket Saurabh. Parameterized Streaming Algorithms for Min-Ones d-SAT. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{agrawal_et_al:LIPIcs.FSTTCS.2019.8, author = {Agrawal, Akanksha and Biswas, Arindam and Bonnet, \'{E}douard and Brettell, Nick and Curticapean, Radu and Marx, D\'{a}niel and Miltzow, Tillmann and Raman, Venkatesh and Saurabh, Saket}, title = {{Parameterized Streaming Algorithms for Min-Ones d-SAT}}, booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)}, pages = {8:1--8:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-131-3}, ISSN = {1868-8969}, year = {2019}, volume = {150}, editor = {Chattopadhyay, Arkadev and Gastin, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.8}, URN = {urn:nbn:de:0030-drops-115708}, doi = {10.4230/LIPIcs.FSTTCS.2019.8}, annote = {Keywords: min, ones, sat, d-sat, parameterized, kernelization, streaming, space, efficient, algorithm, parameter} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden. How Does Object Fatness Impact the Complexity of Packing in d Dimensions?. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 36:1-36:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kisfaludibak_et_al:LIPIcs.ISAAC.2019.36, author = {Kisfaludi-Bak, S\'{a}ndor and Marx, D\'{a}niel and van der Zanden, Tom C.}, title = {{How Does Object Fatness Impact the Complexity of Packing in d Dimensions?}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {36:1--36:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.36}, URN = {urn:nbn:de:0030-drops-115327}, doi = {10.4230/LIPIcs.ISAAC.2019.36}, annote = {Keywords: Geometric intersection graph, Independent Set, Object fatness} }
Published in: Dagstuhl Reports, Volume 9, Issue 1 (2019)
Fedor V. Fomin, Dániel Marx, Saket Saurabh, and Meirav Zehavi. New Horizons in Parameterized Complexity (Dagstuhl Seminar 19041). In Dagstuhl Reports, Volume 9, Issue 1, pp. 67-87, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@Article{fomin_et_al:DagRep.9.1.67, author = {Fomin, Fedor V. and Marx, D\'{a}niel and Saurabh, Saket and Zehavi, Meirav}, title = {{New Horizons in Parameterized Complexity (Dagstuhl Seminar 19041)}}, pages = {67--87}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2019}, volume = {9}, number = {1}, editor = {Fomin, Fedor V. and Marx, D\'{a}niel and Saurabh, Saket and Zehavi, Meirav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.1.67}, URN = {urn:nbn:de:0030-drops-105706}, doi = {10.4230/DagRep.9.1.67}, annote = {Keywords: Intractability, Parameterized Complexity} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Vincent Cohen-Addad, Éric Colin de Verdière, Dániel Marx, and Arnaud de Mesmay. Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{cohenaddad_et_al:LIPIcs.SoCG.2019.27, author = {Cohen-Addad, Vincent and Colin de Verdi\`{e}re, \'{E}ric and Marx, D\'{a}niel and de Mesmay, Arnaud}, title = {{Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {27:1--27:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.27}, URN = {urn:nbn:de:0030-drops-104311}, doi = {10.4230/LIPIcs.SoCG.2019.27}, annote = {Keywords: Cut graph, Multiway cut, Surface, Lower bound, Parameterized Complexity, Exponential Time Hypothesis} }
Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, and Magnus Wahlström. Multi-Budgeted Directed Cuts. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kratsch_et_al:LIPIcs.IPEC.2018.18, author = {Kratsch, Stefan and Li, Shaohua and Marx, D\'{a}niel and Pilipczuk, Marcin and Wahlstr\"{o}m, Magnus}, title = {{Multi-Budgeted Directed Cuts}}, booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)}, pages = {18:1--18:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-084-2}, ISSN = {1868-8969}, year = {2019}, volume = {115}, editor = {Paul, Christophe and Pilipczuk, Michal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.18}, URN = {urn:nbn:de:0030-drops-102194}, doi = {10.4230/LIPIcs.IPEC.2018.18}, annote = {Keywords: important separators, multi-budgeted cuts, Directed Feedback Vertex Set, fixed-parameter tractability, minimum cut} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@Proceedings{chatzigiannakis_et_al:LIPIcs.ICALP.2018, title = {{LIPIcs, Volume 107, ICALP'18, Complete Volume}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018}, URN = {urn:nbn:de:0030-drops-92803}, doi = {10.4230/LIPIcs.ICALP.2018}, annote = {Keywords: Theory of computation} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 0:i-0:xlviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{chatzigiannakis_et_al:LIPIcs.ICALP.2018.0, author = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {0:i--0:xlviii}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.0}, URN = {urn:nbn:de:0030-drops-90049}, doi = {10.4230/LIPIcs.ICALP.2018.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Andreas Emil Feldmann and Dániel Marx. The Parameterized Hardness of the k-Center Problem in Transportation Networks. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{feldmann_et_al:LIPIcs.SWAT.2018.19, author = {Feldmann, Andreas Emil and Marx, D\'{a}niel}, title = {{The Parameterized Hardness of the k-Center Problem in Transportation Networks}}, booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)}, pages = {19:1--19:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-068-2}, ISSN = {1868-8969}, year = {2018}, volume = {101}, editor = {Eppstein, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.19}, URN = {urn:nbn:de:0030-drops-88450}, doi = {10.4230/LIPIcs.SWAT.2018.19}, annote = {Keywords: k-center, parameterized complexity, planar graphs, doubling dimension, highway dimension, treewidth} }
Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Édouard Bonnet, Nick Brettell, O-joung Kwon, and Dániel Marx. Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality Is the Key to Single-Exponential Parameterized Algorithms. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bonnet_et_al:LIPIcs.IPEC.2017.7, author = {Bonnet, \'{E}douard and Brettell, Nick and Kwon, O-joung and Marx, D\'{a}niel}, title = {{Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality Is the Key to Single-Exponential Parameterized Algorithms}}, booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)}, pages = {7:1--7:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-051-4}, ISSN = {1868-8969}, year = {2018}, volume = {89}, editor = {Lokshtanov, Daniel and Nishimura, Naomi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.7}, URN = {urn:nbn:de:0030-drops-85653}, doi = {10.4230/LIPIcs.IPEC.2017.7}, annote = {Keywords: fixed-parameter tractable algorithms, treewidth, feedback vertex set} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
László Egri, Dániel Marx, and Pawel Rzazewski. 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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{egri_et_al:LIPIcs.STACS.2018.27, author = {Egri, L\'{a}szl\'{o} and Marx, D\'{a}niel and Rzazewski, Pawel}, title = {{Finding List Homomorphisms from Bounded-treewidth Graphs to Reflexive Graphs: a Complete Complexity Characterization}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {27:1--27:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.27}, URN = {urn:nbn:de:0030-drops-84867}, doi = {10.4230/LIPIcs.STACS.2018.27}, annote = {Keywords: graph homomorphism, list homomorphism, reflexive graph, treewidth} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Dániel Marx and Marcin Pilipczuk. Subexponential Parameterized Algorithms for Graphs of Polynomial Growth. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{marx_et_al:LIPIcs.ESA.2017.59, author = {Marx, D\'{a}niel and Pilipczuk, Marcin}, title = {{Subexponential Parameterized Algorithms for Graphs of Polynomial Growth}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {59:1--59:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.59}, URN = {urn:nbn:de:0030-drops-78162}, doi = {10.4230/LIPIcs.ESA.2017.59}, annote = {Keywords: polynomial growth, subexponential algorithm, low treewidth pattern covering} }
Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)
Csaba Biró, Édouard Bonnet, Dániel Marx, Tillmann Miltzow, and Pawel Rzazewski. Fine-Grained Complexity of Coloring Unit Disks and Balls. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{biro_et_al:LIPIcs.SoCG.2017.18, author = {Bir\'{o}, Csaba and Bonnet, \'{E}douard and Marx, D\'{a}niel and Miltzow, Tillmann and Rzazewski, Pawel}, title = {{Fine-Grained Complexity of Coloring Unit Disks and Balls}}, booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)}, pages = {18:1--18:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-038-5}, ISSN = {1868-8969}, year = {2017}, volume = {77}, editor = {Aronov, Boris and Katz, Matthew J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.18}, URN = {urn:nbn:de:0030-drops-71800}, doi = {10.4230/LIPIcs.SoCG.2017.18}, annote = {Keywords: unit disk graphs, unit ball graphs, coloring, exact algorithm} }
Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)
Dániel Marx. Graphs, Hypergraphs, and the Complexity of Conjunctive Database Queries (Invited Talk). In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{marx:LIPIcs.ICDT.2017.2, author = {Marx, D\'{a}niel}, title = {{Graphs, Hypergraphs, and the Complexity of Conjunctive Database Queries}}, booktitle = {20th International Conference on Database Theory (ICDT 2017)}, pages = {2:1--2:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-024-8}, ISSN = {1868-8969}, year = {2017}, volume = {68}, editor = {Benedikt, Michael and Orsi, Giorgio}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.2}, URN = {urn:nbn:de:0030-drops-70652}, doi = {10.4230/LIPIcs.ICDT.2017.2}, annote = {Keywords: Conjunctive queries, treewidth, complexity} }
Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Lin Chen, Dániel Marx, Deshi Ye, and Guochuan Zhang. Parameterized and Approximation Results for Scheduling with a Low Rank Processing Time Matrix. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{chen_et_al:LIPIcs.STACS.2017.22, author = {Chen, Lin and Marx, D\'{a}niel and Ye, Deshi and Zhang, Guochuan}, title = {{Parameterized and Approximation Results for Scheduling with a Low Rank Processing Time Matrix}}, booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)}, pages = {22:1--22:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-028-6}, ISSN = {1868-8969}, year = {2017}, volume = {66}, editor = {Vollmer, Heribert and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.22}, URN = {urn:nbn:de:0030-drops-70110}, doi = {10.4230/LIPIcs.STACS.2017.22}, annote = {Keywords: APX-hardness, Parameterized algorithm, Scheduling, Exponential Time Hypothesis} }
Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Gábor Bacsó, Dániel Marx, and Zsolt Tuza. H-Free Graphs, Independent Sets, and Subexponential-Time Algorithms. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{bacso_et_al:LIPIcs.IPEC.2016.3, author = {Bacs\'{o}, G\'{a}bor and Marx, D\'{a}niel and Tuza, Zsolt}, title = {{H-Free Graphs, Independent Sets, and Subexponential-Time Algorithms}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, pages = {3:1--3:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-023-1}, ISSN = {1868-8969}, year = {2017}, volume = {63}, editor = {Guo, Jiong and Hermelin, Danny}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.3}, URN = {urn:nbn:de:0030-drops-69397}, doi = {10.4230/LIPIcs.IPEC.2016.3}, annote = {Keywords: independent set, scattered set, subexponential algorithms, H-free graphs} }
Published in: Dagstuhl Reports, Volume 6, Issue 5 (2016)
Jeff Erickson, Philip N. Klein, Dániel Marx, and Claire Mathieu. Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221). In Dagstuhl Reports, Volume 6, Issue 5, pp. 94-113, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@Article{erickson_et_al:DagRep.6.5.94, author = {Erickson, Jeff and Klein, Philip N. and Marx, D\'{a}niel and Mathieu, Claire}, title = {{Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221)}}, pages = {94--113}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2016}, volume = {6}, number = {5}, editor = {Erickson, Jeff and Klein, Philip N. and Marx, D\'{a}niel and Mathieu, Claire}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.5.94}, URN = {urn:nbn:de:0030-drops-67227}, doi = {10.4230/DagRep.6.5.94}, annote = {Keywords: Algorithms, planar graphs, theory, approximation, fixed-parameter tractable, network flow, network design, kernelization} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Dániel Marx, Ario Salmasi, and Anastasios Sidiropoulos. Constant-Factor Approximations for Asymmetric TSP on Nearly-Embeddable Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 16:1-16:54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{marx_et_al:LIPIcs.APPROX-RANDOM.2016.16, author = {Marx, D\'{a}niel and Salmasi, Ario and Sidiropoulos, Anastasios}, title = {{Constant-Factor Approximations for Asymmetric TSP on Nearly-Embeddable Graphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {16:1--16:54}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.16}, URN = {urn:nbn:de:0030-drops-66391}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.16}, annote = {Keywords: asymmetric TSP, approximation algorithms, nearly-embeddable graphs, Held-Karp LP, exponential time hypothesis} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Andreas Emil Feldmann and Dániel Marx. The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{feldmann_et_al:LIPIcs.ICALP.2016.27, author = {Feldmann, Andreas Emil and Marx, D\'{a}niel}, title = {{The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {27:1--27:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.27}, URN = {urn:nbn:de:0030-drops-63060}, doi = {10.4230/LIPIcs.ICALP.2016.27}, annote = {Keywords: Directed Steiner Tree, Directed Steiner Network, fixed-parameter tractability, dichotomy} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Dániel Marx and Valia Mitsou. Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{marx_et_al:LIPIcs.ICALP.2016.28, author = {Marx, D\'{a}niel and Mitsou, Valia}, title = {{Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {28:1--28:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.28}, URN = {urn:nbn:de:0030-drops-63078}, doi = {10.4230/LIPIcs.ICALP.2016.28}, annote = {Keywords: Parameterized Complexity, List coloring, Treewidth, Lower bounds under ETH} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, and Roman Rabinovich. Routing with Congestion in Acyclic Digraphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 7:1-7:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{amiri_et_al:LIPIcs.MFCS.2016.7, author = {Amiri, Saeed Akhoondian and Kreutzer, Stephan and Marx, D\'{a}niel and Rabinovich, Roman}, title = {{Routing with Congestion in Acyclic Digraphs}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {7:1--7:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.7}, URN = {urn:nbn:de:0030-drops-64244}, doi = {10.4230/LIPIcs.MFCS.2016.7}, annote = {Keywords: algorithms, disjoint paths, congestion, acyclic digraphs, XP, W\lbrack1\rbrack-hard} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Édouard Bonnet, László Egri, and Dániel Marx. Fixed-Parameter Approximability of Boolean MinCSPs. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{bonnet_et_al:LIPIcs.ESA.2016.18, author = {Bonnet, \'{E}douard and Egri, L\'{a}szl\'{o} and Marx, D\'{a}niel}, title = {{Fixed-Parameter Approximability of Boolean MinCSPs}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {18:1--18:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.18}, URN = {urn:nbn:de:0030-drops-63694}, doi = {10.4230/LIPIcs.ESA.2016.18}, annote = {Keywords: constraint satisfaction problems, approximability, fixed-parameter tractability} }
Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Dániel Marx. The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems (Invited Talk). In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, p. 32:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{marx:LIPIcs.SWAT.2016.32, author = {Marx, D\'{a}niel}, title = {{The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems}}, booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)}, pages = {32:1--32:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-011-8}, ISSN = {1868-8969}, year = {2016}, volume = {53}, editor = {Pagh, Rasmus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.32}, URN = {urn:nbn:de:0030-drops-60535}, doi = {10.4230/LIPIcs.SWAT.2016.32}, annote = {Keywords: Directed Steiner Tree, Directed Steiner Network, fixed-parameter tractability, dichotomy} }
Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)
Dániel Marx and Tillmann Miltzow. Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 52:1-52:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{marx_et_al:LIPIcs.SoCG.2016.52, author = {Marx, D\'{a}niel and Miltzow, Tillmann}, title = {{Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems}}, booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)}, pages = {52:1--52:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-009-5}, ISSN = {1868-8969}, year = {2016}, volume = {51}, editor = {Fekete, S\'{a}ndor and Lubiw, Anna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.52}, URN = {urn:nbn:de:0030-drops-59445}, doi = {10.4230/LIPIcs.SoCG.2016.52}, annote = {Keywords: computational geometry, triangulations, exponential-time algorithms} }
Published in: Dagstuhl Reports, Volume 5, Issue 7 (2016)
Andrei A. Bulatov, Venkatesan Guruswami, Andrei Krokhin, and Dániel Marx. The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301). In Dagstuhl Reports, Volume 5, Issue 7, pp. 22-41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@Article{bulatov_et_al:DagRep.5.7.22, author = {Bulatov, Andrei A. and Guruswami, Venkatesan and Krokhin, Andrei and Marx, D\'{a}niel}, title = {{The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301)}}, pages = {22--41}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2016}, volume = {5}, number = {7}, editor = {Bulatov, Andrei A. and Guruswami, Venkatesan and Krokhin, Andrei and Marx, D\'{a}niel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.7.22}, URN = {urn:nbn:de:0030-drops-56714}, doi = {10.4230/DagRep.5.7.22}, annote = {Keywords: Constraint satisfaction problem (CSP), Computational complexity, CSP dichotomy conjecture, Hardness of approximation, Unique games conjecture, Fixed-parameter tractability, Descriptive complexity, Universal algebra, Logic, Decomposition methods} }
Published in: Dagstuhl Reports, Volume 4, Issue 11 (2015)
Stefan Kratsch, Daniel Lokshtanov, Dániel Marx, and Peter Rossmanith. Optimality and tight results in parameterized complexity (Dagstuhl Seminar 14451). In Dagstuhl Reports, Volume 4, Issue 11, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@Article{kratsch_et_al:DagRep.4.11.1, author = {Kratsch, Stefan and Lokshtanov, Daniel and Marx, D\'{a}niel and Rossmanith, Peter}, title = {{Optimality and tight results in parameterized complexity (Dagstuhl Seminar 14451)}}, pages = {1--21}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2015}, volume = {4}, number = {11}, editor = {Kratsch, Stefan and Lokshtanov, Daniel and Marx, D\'{a}niel and Rossmanith, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.11.1}, URN = {urn:nbn:de:0030-drops-49677}, doi = {10.4230/DagRep.4.11.1}, annote = {Keywords: Algorithms, parameterized complexity, kernels, width measures, exponential time hypothesis, lower bounds} }
Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Yixin Cao and Dániel Marx. Chordal Editing is Fixed-Parameter Tractable. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 214-225, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{cao_et_al:LIPIcs.STACS.2014.214, author = {Cao, Yixin and Marx, D\'{a}niel}, title = {{Chordal Editing is Fixed-Parameter Tractable}}, booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)}, pages = {214--225}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-65-1}, ISSN = {1868-8969}, year = {2014}, volume = {25}, editor = {Mayr, Ernst W. and Portier, Natacha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.214}, URN = {urn:nbn:de:0030-drops-44591}, doi = {10.4230/LIPIcs.STACS.2014.214}, annote = {Keywords: chordal graph, parameterized computation, graph modification problems, chordal deletion, chordal completion, clique tree decomposition, holes, simplic} }
Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Dániel Marx and Michal Pilipczuk. Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask). In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 542-553, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{marx_et_al:LIPIcs.STACS.2014.542, author = {Marx, D\'{a}niel and Pilipczuk, Michal}, title = {{Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)}}, booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)}, pages = {542--553}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-65-1}, ISSN = {1868-8969}, year = {2014}, volume = {25}, editor = {Mayr, Ernst W. and Portier, Natacha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.542}, URN = {urn:nbn:de:0030-drops-44863}, doi = {10.4230/LIPIcs.STACS.2014.542}, annote = {Keywords: parameterized complexity, subgraph isomorphism} }
Published in: Dagstuhl Reports, Volume 3, Issue 10 (2014)
Glencora Borradaile, Philp Klein, Dániel Marx, and Claire Mathieu. Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 13421). In Dagstuhl Reports, Volume 3, Issue 10, pp. 36-57, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@Article{borradaile_et_al:DagRep.3.10.36, author = {Borradaile, Glencora and Klein, Philp and Marx, D\'{a}niel and Mathieu, Claire}, title = {{Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 13421)}}, pages = {36--57}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2014}, volume = {3}, number = {10}, editor = {Borradaile, Glencora and Klein, Philp and Marx, D\'{a}niel and Mathieu, Claire}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.10.36}, URN = {urn:nbn:de:0030-drops-44274}, doi = {10.4230/DagRep.3.10.36}, annote = {Keywords: Algorithms, planar graphs, theory, approximation, fixed-parameter tractable, network flow, network design, kernelization} }
Published in: Dagstuhl Reports, Volume 2, Issue 11 (2013)
Johan Hastad, Andrei Krokhin, and Dániel Marx. The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451). In Dagstuhl Reports, Volume 2, Issue 11, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@Article{hastad_et_al:DagRep.2.11.1, author = {Hastad, Johan and Krokhin, Andrei and Marx, D\'{a}niel}, title = {{The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451)}}, pages = {1--19}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2013}, volume = {2}, number = {11}, editor = {Hastad, Johan and Krokhin, Andrei and Marx, D\'{a}niel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.11.1}, URN = {urn:nbn:de:0030-drops-39764}, doi = {10.4230/DagRep.2.11.1}, annote = {Keywords: Constraint satisfaction problem (CSP); Computational complexity; CSP dichotomy conjecture; Hardness of approximation; Unique games conjceture; Fixed-parameter tractability; Descriptive complexity; niversal algebra; Logic; Decomposition methods} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Dániel Marx. Algorithmic Graph Structure Theory (Tutorial). In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, p. 7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{marx:LIPIcs.STACS.2013.7, author = {Marx, D\'{a}niel}, title = {{Algorithmic Graph Structure Theory}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {7--7}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.7}, URN = {urn:nbn:de:0030-drops-39175}, doi = {10.4230/LIPIcs.STACS.2013.7}, annote = {Keywords: Graph theory, graph minors, structure theorems} }
Published in: Dagstuhl Reports, Volume 2, Issue 6 (2012)
Michael R. Fellows, Jiong Guo, Dániel Marx, and Saket Saurabh. Data Reduction and Problem Kernels (Dagstuhl Seminar 12241). In Dagstuhl Reports, Volume 2, Issue 6, pp. 26-50, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@Article{fellows_et_al:DagRep.2.6.26, author = {Fellows, Michael R. and Guo, Jiong and Marx, D\'{a}niel and Saurabh, Saket}, title = {{Data Reduction and Problem Kernels (Dagstuhl Seminar 12241)}}, pages = {26--50}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2012}, volume = {2}, number = {6}, editor = {Fellows, Michael R. and Guo, Jiong and Marx, D\'{a}niel and Saurabh, Saket}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.6.26}, URN = {urn:nbn:de:0030-drops-37297}, doi = {10.4230/DagRep.2.6.26}, annote = {Keywords: Preprocessing, Fixed-parameter tractability, Parameterized algorithmics} }
Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)
Dániel Marx, Barry O'Sullivan, and Igor Razgon. Treewidth Reduction for Constrained Separation and Bipartization Problems. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 561-572, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{marx_et_al:LIPIcs.STACS.2010.2485, author = {Marx, D\'{a}niel and O'Sullivan, Barry and Razgon, Igor}, title = {{Treewidth Reduction for Constrained Separation and Bipartization Problems}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {561--572}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2485}, URN = {urn:nbn:de:0030-drops-24850}, doi = {10.4230/LIPIcs.STACS.2010.2485}, annote = {Keywords: Fixed-parameter algorithms, graph separation problems, treewidth} }
Published in: Dagstuhl Seminar Proceedings, Volume 9511, Parameterized complexity and approximation algorithms (2010)
Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dániel Marx. 09511 Abstracts Collection – Parameterized complexity and approximation algorithms. In Parameterized complexity and approximation algorithms. Dagstuhl Seminar Proceedings, Volume 9511, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{demaine_et_al:DagSemProc.09511.1, author = {Demaine, Erik D. and Hajiaghayi, MohammadTaghi and Marx, D\'{a}niel}, title = {{09511 Abstracts Collection – Parameterized complexity and approximation algorithms}}, booktitle = {Parameterized complexity and approximation algorithms}, pages = {1--14}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9511}, editor = {Erik D. Demaine and MohammadTaghi Hajiaghayi and D\'{a}niel Marx}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09511.1}, URN = {urn:nbn:de:0030-drops-25025}, doi = {10.4230/DagSemProc.09511.1}, annote = {Keywords: Parameterized complexity, Approximation algorithms} }
Published in: Dagstuhl Seminar Proceedings, Volume 9511, Parameterized complexity and approximation algorithms (2010)
Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dániel Marx. 09511 Executive Summary – Parameterized complexity and approximation algorithms. In Parameterized complexity and approximation algorithms. Dagstuhl Seminar Proceedings, Volume 9511, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{demaine_et_al:DagSemProc.09511.2, author = {Demaine, Erik D. and Hajiaghayi, MohammadTaghi and Marx, D\'{a}niel}, title = {{09511 Executive Summary – Parameterized complexity and approximation algorithms}}, booktitle = {Parameterized complexity and approximation algorithms}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9511}, editor = {Erik D. Demaine and MohammadTaghi Hajiaghayi and D\'{a}niel Marx}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09511.2}, URN = {urn:nbn:de:0030-drops-25011}, doi = {10.4230/DagSemProc.09511.2}, annote = {Keywords: Parameterized complexity, Approximation algorithms} }
Published in: Dagstuhl Seminar Proceedings, Volume 9511, Parameterized complexity and approximation algorithms (2010)
Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dániel Marx. 09511 Open Problems – Parameterized complexity and approximation algorithms. In Parameterized complexity and approximation algorithms. Dagstuhl Seminar Proceedings, Volume 9511, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{demaine_et_al:DagSemProc.09511.3, author = {Demaine, Erik D. and Hajiaghayi, MohammadTaghi and Marx, D\'{a}niel}, title = {{09511 Open Problems – Parameterized complexity and approximation algorithms}}, booktitle = {Parameterized complexity and approximation algorithms}, pages = {1--10}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9511}, editor = {Erik D. Demaine and MohammadTaghi Hajiaghayi and D\'{a}niel Marx}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09511.3}, URN = {urn:nbn:de:0030-drops-24992}, doi = {10.4230/DagSemProc.09511.3}, annote = {Keywords: Parameterized complexity, approximation algorithms, open problems} }
Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)
Andrei A. Bulatov, Victor Dalmau, Martin Grohe, and Daniel Marx. Enumerating Homomorphisms. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 231-242, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{bulatov_et_al:LIPIcs.STACS.2009.1838, author = {Bulatov, Andrei A. and Dalmau, Victor and Grohe, Martin and Marx, Daniel}, title = {{Enumerating Homomorphisms}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {231--242}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1838}, URN = {urn:nbn:de:0030-drops-18385}, doi = {10.4230/LIPIcs.STACS.2009.1838}, annote = {Keywords: } }
Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)
Daniel Marx. Tractable Structures for Constraint Satisfaction with Truth Tables. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 649-660, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{marx:LIPIcs.STACS.2009.1807, author = {Marx, Daniel}, title = {{Tractable Structures for Constraint Satisfaction with Truth Tables}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {649--660}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1807}, URN = {urn:nbn:de:0030-drops-18079}, doi = {10.4230/LIPIcs.STACS.2009.1807}, annote = {Keywords: Computational complexity, Constraint satisfaction, Treewidth, Adaptive width} }
Published in: Dagstuhl Seminar Proceedings, Volume 7281, Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs (2007)
Erik Demaine, Gregory Z. Gutin, Daniel Marx, and Ulrike Stege. 07281 Open Problems – Structure Theory and FPT Algorithmcs for Graphs, Digraphs and Hypergraphs. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Dagstuhl Seminar Proceedings, Volume 7281, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
@InProceedings{demaine_et_al:DagSemProc.07281.2, author = {Demaine, Erik and Gutin, Gregory Z. and Marx, Daniel and Stege, Ulrike}, title = {{07281 Open Problems – Structure Theory and FPT Algorithmcs for Graphs, Digraphs and Hypergraphs}}, booktitle = {Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs}, pages = {1--6}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2007}, volume = {7281}, editor = {Erik Demaine and Gregory Z. Gutin and Daniel Marx and Ulrike Stege}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07281.2}, URN = {urn:nbn:de:0030-drops-12542}, doi = {10.4230/DagSemProc.07281.2}, annote = {Keywords: } }
Published in: Dagstuhl Seminar Proceedings, Volume 7281, Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs (2007)
Erik Demaine, Gregory Z. Gutin, Daniel Marx, and Ulrike Stege. 07281 Abstracts Collection – Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Dagstuhl Seminar Proceedings, Volume 7281, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
@InProceedings{demaine_et_al:DagSemProc.07281.1, author = {Demaine, Erik and Gutin, Gregory Z. and Marx, Daniel and Stege, Ulrike}, title = {{07281 Abstracts Collection – Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs}}, booktitle = {Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs}, pages = {1--14}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2007}, volume = {7281}, editor = {Erik Demaine and Gregory Z. Gutin and Daniel Marx and Ulrike Stege}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07281.1}, URN = {urn:nbn:de:0030-drops-12450}, doi = {10.4230/DagSemProc.07281.1}, annote = {Keywords: Parameterized complexity, fixed-parameter tractability, graph structure theory} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Barış Can Esmer, Jacob Focke, Dániel Marx, and Paweł Rzążewski. List Homomorphisms by Deleting Edges and Vertices: Tight Complexity Bounds for Bounded-Treewidth Graphs. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 39:1-39:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{canesmer_et_al:LIPIcs.ESA.2024.39, author = {Can Esmer, Bar{\i}\c{s} and Focke, Jacob and Marx, D\'{a}niel and Rz\k{a}\.{z}ewski, Pawe{\l}}, title = {{List Homomorphisms by Deleting Edges and Vertices: Tight Complexity Bounds for Bounded-Treewidth Graphs}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {39:1--39:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.39}, URN = {urn:nbn:de:0030-drops-211103}, doi = {10.4230/LIPIcs.ESA.2024.39}, annote = {Keywords: Graph Homomorphism, List Homomorphism, Vertex Deletion, Edge Deletion, Multiway Cut, Parameterized Complexity, Tight Bounds, Treewidth, SETH} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Jacob Focke, Fabian Frei, Shaohua Li, Dániel Marx, Philipp Schepper, Roohani Sharma, and Karol Węgrzycki. Hitting Meets Packing: How Hard Can It Be?. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 55:1-55:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{focke_et_al:LIPIcs.ESA.2024.55, author = {Focke, Jacob and Frei, Fabian and Li, Shaohua and Marx, D\'{a}niel and Schepper, Philipp and Sharma, Roohani and W\k{e}grzycki, Karol}, title = {{Hitting Meets Packing: How Hard Can It Be?}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {55:1--55:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.55}, URN = {urn:nbn:de:0030-drops-211261}, doi = {10.4230/LIPIcs.ESA.2024.55}, annote = {Keywords: Hitting, Packing, Covering, Parameterized Algorithms, Lower Bounds, Treewidth} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Fateme Abbasi, Sandip Banerjee, Jarosław Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, and Joachim Spoerhase. Parameterized Approximation For Robust Clustering in Discrete Geometric Spaces. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{abbasi_et_al:LIPIcs.ICALP.2024.6, author = {Abbasi, Fateme and Banerjee, Sandip and Byrka, Jaros{\l}aw and Chalermsook, Parinya and Gadekar, Ameet and Khodamoradi, Kamyar and Marx, D\'{a}niel and Sharma, Roohani and Spoerhase, Joachim}, title = {{Parameterized Approximation For Robust Clustering in Discrete Geometric Spaces}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {6:1--6:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.6}, URN = {urn:nbn:de:0030-drops-201494}, doi = {10.4230/LIPIcs.ICALP.2024.6}, annote = {Keywords: Clustering, approximation algorithms, parameterized complexity} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Barış Can Esmer, Jacob Focke, Dániel Marx, and Paweł Rzążewski. Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{canesmer_et_al:LIPIcs.ICALP.2024.34, author = {Can Esmer, Bar{\i}\c{s} and Focke, Jacob and Marx, D\'{a}niel and Rz\k{a}\.{z}ewski, Pawe{\l}}, title = {{Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {34:1--34:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.34}, URN = {urn:nbn:de:0030-drops-201772}, doi = {10.4230/LIPIcs.ICALP.2024.34}, annote = {Keywords: Parameterized Complexity, Tight Bounds, Hub, Treewidth, Strong Exponential Time Hypothesis, Vertex Coloring, Vertex Deletion, Edge Deletion, Triangle Packing, Triangle Partition, Set Cover Hypothesis, Dominating Set} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Esther Galby, Sándor Kisfaludi-Bak, Dániel Marx, and Roohani Sharma. Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 67:1-67:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{galby_et_al:LIPIcs.ICALP.2024.67, author = {Galby, Esther and Kisfaludi-Bak, S\'{a}ndor and Marx, D\'{a}niel and Sharma, Roohani}, title = {{Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {67:1--67:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.67}, URN = {urn:nbn:de:0030-drops-202104}, doi = {10.4230/LIPIcs.ICALP.2024.67}, annote = {Keywords: Directed Steiner Network, Sub-exponential algorithm} }
Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
Jacob Focke, Florian Hörsch, Shaohua Li, and Dániel Marx. Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{focke_et_al:LIPIcs.SoCG.2024.57, author = {Focke, Jacob and H\"{o}rsch, Florian and Li, Shaohua and Marx, D\'{a}niel}, title = {{Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {57:1--57:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-316-4}, ISSN = {1868-8969}, year = {2024}, volume = {293}, editor = {Mulzer, Wolfgang and Phillips, Jeff M.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.57}, URN = {urn:nbn:de:0030-drops-200021}, doi = {10.4230/LIPIcs.SoCG.2024.57}, annote = {Keywords: MultiCut, Multiway Cut, Parameterized Complexity, Tight Bounds, Embedded Graph, Planar Graph, Genus, Surface, Exponential Time Hypothesis} }
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Barış Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, and Roohani Sharma. Approximate Monotone Local Search for Weighted Problems. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 17:1-17:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{esmer_et_al:LIPIcs.IPEC.2023.17, author = {Esmer, Bar{\i}\c{s} Can and Kulik, Ariel and Marx, D\'{a}niel and Neuen, Daniel and Sharma, Roohani}, title = {{Approximate Monotone Local Search for Weighted Problems}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {17:1--17:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-305-8}, ISSN = {1868-8969}, year = {2023}, volume = {285}, editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.17}, URN = {urn:nbn:de:0030-drops-194360}, doi = {10.4230/LIPIcs.IPEC.2023.17}, annote = {Keywords: parameterized approximations, exponential approximations, monotone local search} }
Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Barış Can Esmer, Ariel Kulik, Dániel Marx, Philipp Schepper, and Karol Węgrzycki. Computing Generalized Convolutions Faster Than Brute Force. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{esmer_et_al:LIPIcs.IPEC.2022.12, author = {Esmer, Bar{\i}\c{s} Can and Kulik, Ariel and Marx, D\'{a}niel and Schepper, Philipp and W\k{e}grzycki, Karol}, title = {{Computing Generalized Convolutions Faster Than Brute Force}}, booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, pages = {12:1--12:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-260-0}, ISSN = {1868-8969}, year = {2022}, volume = {249}, editor = {Dell, Holger and Nederlof, Jesper}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.12}, URN = {urn:nbn:de:0030-drops-173685}, doi = {10.4230/LIPIcs.IPEC.2022.12}, annote = {Keywords: Generalized Convolution, Fast Fourier Transform, Fast Subset Convolution} }
Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Esther Galby, Dániel Marx, Philipp Schepper, Roohani Sharma, and Prafullkumar Tale. Domination and Cut Problems on Chordal Graphs with Bounded Leafage. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 14:1-14:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{galby_et_al:LIPIcs.IPEC.2022.14, author = {Galby, Esther and Marx, D\'{a}niel and Schepper, Philipp and Sharma, Roohani and Tale, Prafullkumar}, title = {{Domination and Cut Problems on Chordal Graphs with Bounded Leafage}}, booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, pages = {14:1--14:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-260-0}, ISSN = {1868-8969}, year = {2022}, volume = {249}, editor = {Dell, Holger and Nederlof, Jesper}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.14}, URN = {urn:nbn:de:0030-drops-173704}, doi = {10.4230/LIPIcs.IPEC.2022.14}, annote = {Keywords: Chordal Graphs, Leafage, FPT Algorithms, Dominating Set, MultiCut with Undeletable Terminals, Multiway Cut with Undeletable Terminals} }
Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Dániel Marx, Govind S. Sankar, and Philipp Schepper. Anti-Factor Is FPT Parameterized by Treewidth and List Size (But Counting Is Hard). In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 22:1-22:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{marx_et_al:LIPIcs.IPEC.2022.22, author = {Marx, D\'{a}niel and Sankar, Govind S. and Schepper, Philipp}, title = {{Anti-Factor Is FPT Parameterized by Treewidth and List Size (But Counting Is Hard)}}, booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, pages = {22:1--22:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-260-0}, ISSN = {1868-8969}, year = {2022}, volume = {249}, editor = {Dell, Holger and Nederlof, Jesper}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.22}, URN = {urn:nbn:de:0030-drops-173780}, doi = {10.4230/LIPIcs.IPEC.2022.22}, annote = {Keywords: Anti-Factor, General Factor, Treewidth, Representative Sets, SETH} }
Published in: Dagstuhl Reports, Volume 12, Issue 5 (2022)
Martin Grohe, Venkatesan Guruswami, Dániel Marx, and Stanislav Živný. The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201). In Dagstuhl Reports, Volume 12, Issue 5, pp. 112-130, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@Article{grohe_et_al:DagRep.12.5.112, author = {Grohe, Martin and Guruswami, Venkatesan and Marx, D\'{a}niel and \v{Z}ivn\'{y}, Stanislav}, title = {{The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201)}}, pages = {112--130}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2022}, volume = {12}, number = {5}, editor = {Grohe, Martin and Guruswami, Venkatesan and Marx, D\'{a}niel and \v{Z}ivn\'{y}, Stanislav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.5.112}, URN = {urn:nbn:de:0030-drops-174453}, doi = {10.4230/DagRep.12.5.112}, annote = {Keywords: Constraint satisfaction problem (CSP); Computational complexity; Hardness of approximation; Universal algebra; Semidefinite programming} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Barış Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, and Roohani Sharma. Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 50:1-50:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{esmer_et_al:LIPIcs.ESA.2022.50, author = {Esmer, Bar{\i}\c{s} Can and Kulik, Ariel and Marx, D\'{a}niel and Neuen, Daniel and Sharma, Roohani}, title = {{Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {50:1--50:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.50}, URN = {urn:nbn:de:0030-drops-169887}, doi = {10.4230/LIPIcs.ESA.2022.50}, annote = {Keywords: parameterized approximations, exponential approximations, monotone local search} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Karl Bringmann, Sándor Kisfaludi‑Bak, Marvin Künnemann, Dániel Marx, and André Nusser. Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bringmann_et_al:LIPIcs.SoCG.2022.20, author = {Bringmann, Karl and Kisfaludi‑Bak, S\'{a}ndor and K\"{u}nnemann, Marvin and Marx, D\'{a}niel and Nusser, Andr\'{e}}, title = {{Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {20:1--20:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-227-3}, ISSN = {1868-8969}, year = {2022}, volume = {224}, editor = {Goaoc, Xavier and Kerber, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.20}, URN = {urn:nbn:de:0030-drops-160287}, doi = {10.4230/LIPIcs.SoCG.2022.20}, annote = {Keywords: Dynamic Time Warping, Sequence Similarity Measures} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Dániel Marx, Govind S. Sankar, and Philipp Schepper. 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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 95:1-95:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{marx_et_al:LIPIcs.ICALP.2021.95, author = {Marx, D\'{a}niel and Sankar, Govind S. and Schepper, Philipp}, title = {{Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {95:1--95:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.95}, URN = {urn:nbn:de:0030-drops-141647}, doi = {10.4230/LIPIcs.ICALP.2021.95}, annote = {Keywords: General Factor, General Matching, Treewidth, Cutwidth} }
Published in: LIPIcs, Volume 192, 2nd Symposium on Foundations of Responsible Computing (FORC 2021)
Vincent Cohen-Addad, Philip N. Klein, Dániel Marx, Archer Wheeler, and Christopher Wolfram. On the Computational Tractability of a Geographic Clustering Problem Arising in Redistricting. In 2nd Symposium on Foundations of Responsible Computing (FORC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 192, pp. 3:1-3:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{cohenaddad_et_al:LIPIcs.FORC.2021.3, author = {Cohen-Addad, Vincent and Klein, Philip N. and Marx, D\'{a}niel and Wheeler, Archer and Wolfram, Christopher}, title = {{On the Computational Tractability of a Geographic Clustering Problem Arising in Redistricting}}, booktitle = {2nd Symposium on Foundations of Responsible Computing (FORC 2021)}, pages = {3:1--3:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-187-0}, ISSN = {1868-8969}, year = {2021}, volume = {192}, editor = {Ligett, Katrina and Gupta, Swati}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2021.3}, URN = {urn:nbn:de:0030-drops-138718}, doi = {10.4230/LIPIcs.FORC.2021.3}, annote = {Keywords: redistricting, algorithms, planar graphs, lower bounds} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Dániel Marx. Chordless Cycle Packing Is Fixed-Parameter Tractable. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 71:1-71:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{marx:LIPIcs.ESA.2020.71, author = {Marx, D\'{a}niel}, title = {{Chordless Cycle Packing Is Fixed-Parameter Tractable}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {71:1--71:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.71}, URN = {urn:nbn:de:0030-drops-129373}, doi = {10.4230/LIPIcs.ESA.2020.71}, annote = {Keywords: chordal graphs, packing, fixed-parameter tractability} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Dániel Marx and R. B. Sandeep. Incompressibility of H-Free Edge Modification Problems: Towards a Dichotomy. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 72:1-72:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{marx_et_al:LIPIcs.ESA.2020.72, author = {Marx, D\'{a}niel and Sandeep, R. B.}, title = {{Incompressibility of H-Free Edge Modification Problems: Towards a Dichotomy}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {72:1--72:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.72}, URN = {urn:nbn:de:0030-drops-129383}, doi = {10.4230/LIPIcs.ESA.2020.72}, annote = {Keywords: incompressibility, edge modification problems, H-free graphs} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Marvin Künnemann and Dániel Marx. Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-Grained Perspective into Boolean Constraint Satisfaction. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 27:1-27:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kunnemann_et_al:LIPIcs.CCC.2020.27, author = {K\"{u}nnemann, Marvin and Marx, D\'{a}niel}, title = {{Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-Grained Perspective into Boolean Constraint Satisfaction}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {27:1--27:28}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.27}, URN = {urn:nbn:de:0030-drops-125791}, doi = {10.4230/LIPIcs.CCC.2020.27}, annote = {Keywords: Fine-grained complexity theory, algorithmic classification theorem, multivariate algorithms and complexity, constraint satisfaction problems, satisfiability} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Alexander Göke, Dániel Marx, and Matthias Mnich. Hitting Long Directed Cycles Is Fixed-Parameter Tractable. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 59:1-59:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{goke_et_al:LIPIcs.ICALP.2020.59, author = {G\"{o}ke, Alexander and Marx, D\'{a}niel and Mnich, Matthias}, title = {{Hitting Long Directed Cycles Is Fixed-Parameter Tractable}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {59:1--59:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.59}, URN = {urn:nbn:de:0030-drops-124664}, doi = {10.4230/LIPIcs.ICALP.2020.59}, annote = {Keywords: Directed graphs, directed feedback vertex set, circumference} }
Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Benjamin Aram Berendsohn, László Kozma, and Dániel Marx. Finding and Counting Permutations via CSPs. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{berendsohn_et_al:LIPIcs.IPEC.2019.1, author = {Berendsohn, Benjamin Aram and Kozma, L\'{a}szl\'{o} and Marx, D\'{a}niel}, title = {{Finding and Counting Permutations via CSPs}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {1:1--1:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.1}, URN = {urn:nbn:de:0030-drops-114627}, doi = {10.4230/LIPIcs.IPEC.2019.1}, annote = {Keywords: permutations, pattern matching, constraint satisfaction, exponential time} }
Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Akanksha Agrawal, Arindam Biswas, Édouard Bonnet, Nick Brettell, Radu Curticapean, Dániel Marx, Tillmann Miltzow, Venkatesh Raman, and Saket Saurabh. Parameterized Streaming Algorithms for Min-Ones d-SAT. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{agrawal_et_al:LIPIcs.FSTTCS.2019.8, author = {Agrawal, Akanksha and Biswas, Arindam and Bonnet, \'{E}douard and Brettell, Nick and Curticapean, Radu and Marx, D\'{a}niel and Miltzow, Tillmann and Raman, Venkatesh and Saurabh, Saket}, title = {{Parameterized Streaming Algorithms for Min-Ones d-SAT}}, booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)}, pages = {8:1--8:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-131-3}, ISSN = {1868-8969}, year = {2019}, volume = {150}, editor = {Chattopadhyay, Arkadev and Gastin, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.8}, URN = {urn:nbn:de:0030-drops-115708}, doi = {10.4230/LIPIcs.FSTTCS.2019.8}, annote = {Keywords: min, ones, sat, d-sat, parameterized, kernelization, streaming, space, efficient, algorithm, parameter} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden. How Does Object Fatness Impact the Complexity of Packing in d Dimensions?. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 36:1-36:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kisfaludibak_et_al:LIPIcs.ISAAC.2019.36, author = {Kisfaludi-Bak, S\'{a}ndor and Marx, D\'{a}niel and van der Zanden, Tom C.}, title = {{How Does Object Fatness Impact the Complexity of Packing in d Dimensions?}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {36:1--36:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.36}, URN = {urn:nbn:de:0030-drops-115327}, doi = {10.4230/LIPIcs.ISAAC.2019.36}, annote = {Keywords: Geometric intersection graph, Independent Set, Object fatness} }
Published in: Dagstuhl Reports, Volume 9, Issue 1 (2019)
Fedor V. Fomin, Dániel Marx, Saket Saurabh, and Meirav Zehavi. New Horizons in Parameterized Complexity (Dagstuhl Seminar 19041). In Dagstuhl Reports, Volume 9, Issue 1, pp. 67-87, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@Article{fomin_et_al:DagRep.9.1.67, author = {Fomin, Fedor V. and Marx, D\'{a}niel and Saurabh, Saket and Zehavi, Meirav}, title = {{New Horizons in Parameterized Complexity (Dagstuhl Seminar 19041)}}, pages = {67--87}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2019}, volume = {9}, number = {1}, editor = {Fomin, Fedor V. and Marx, D\'{a}niel and Saurabh, Saket and Zehavi, Meirav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.1.67}, URN = {urn:nbn:de:0030-drops-105706}, doi = {10.4230/DagRep.9.1.67}, annote = {Keywords: Intractability, Parameterized Complexity} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Vincent Cohen-Addad, Éric Colin de Verdière, Dániel Marx, and Arnaud de Mesmay. Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{cohenaddad_et_al:LIPIcs.SoCG.2019.27, author = {Cohen-Addad, Vincent and Colin de Verdi\`{e}re, \'{E}ric and Marx, D\'{a}niel and de Mesmay, Arnaud}, title = {{Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {27:1--27:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.27}, URN = {urn:nbn:de:0030-drops-104311}, doi = {10.4230/LIPIcs.SoCG.2019.27}, annote = {Keywords: Cut graph, Multiway cut, Surface, Lower bound, Parameterized Complexity, Exponential Time Hypothesis} }
Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, and Magnus Wahlström. Multi-Budgeted Directed Cuts. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kratsch_et_al:LIPIcs.IPEC.2018.18, author = {Kratsch, Stefan and Li, Shaohua and Marx, D\'{a}niel and Pilipczuk, Marcin and Wahlstr\"{o}m, Magnus}, title = {{Multi-Budgeted Directed Cuts}}, booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)}, pages = {18:1--18:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-084-2}, ISSN = {1868-8969}, year = {2019}, volume = {115}, editor = {Paul, Christophe and Pilipczuk, Michal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.18}, URN = {urn:nbn:de:0030-drops-102194}, doi = {10.4230/LIPIcs.IPEC.2018.18}, annote = {Keywords: important separators, multi-budgeted cuts, Directed Feedback Vertex Set, fixed-parameter tractability, minimum cut} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@Proceedings{chatzigiannakis_et_al:LIPIcs.ICALP.2018, title = {{LIPIcs, Volume 107, ICALP'18, Complete Volume}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018}, URN = {urn:nbn:de:0030-drops-92803}, doi = {10.4230/LIPIcs.ICALP.2018}, annote = {Keywords: Theory of computation} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 0:i-0:xlviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{chatzigiannakis_et_al:LIPIcs.ICALP.2018.0, author = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {0:i--0:xlviii}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.0}, URN = {urn:nbn:de:0030-drops-90049}, doi = {10.4230/LIPIcs.ICALP.2018.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Andreas Emil Feldmann and Dániel Marx. The Parameterized Hardness of the k-Center Problem in Transportation Networks. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{feldmann_et_al:LIPIcs.SWAT.2018.19, author = {Feldmann, Andreas Emil and Marx, D\'{a}niel}, title = {{The Parameterized Hardness of the k-Center Problem in Transportation Networks}}, booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)}, pages = {19:1--19:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-068-2}, ISSN = {1868-8969}, year = {2018}, volume = {101}, editor = {Eppstein, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.19}, URN = {urn:nbn:de:0030-drops-88450}, doi = {10.4230/LIPIcs.SWAT.2018.19}, annote = {Keywords: k-center, parameterized complexity, planar graphs, doubling dimension, highway dimension, treewidth} }
Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Édouard Bonnet, Nick Brettell, O-joung Kwon, and Dániel Marx. Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality Is the Key to Single-Exponential Parameterized Algorithms. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bonnet_et_al:LIPIcs.IPEC.2017.7, author = {Bonnet, \'{E}douard and Brettell, Nick and Kwon, O-joung and Marx, D\'{a}niel}, title = {{Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality Is the Key to Single-Exponential Parameterized Algorithms}}, booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)}, pages = {7:1--7:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-051-4}, ISSN = {1868-8969}, year = {2018}, volume = {89}, editor = {Lokshtanov, Daniel and Nishimura, Naomi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.7}, URN = {urn:nbn:de:0030-drops-85653}, doi = {10.4230/LIPIcs.IPEC.2017.7}, annote = {Keywords: fixed-parameter tractable algorithms, treewidth, feedback vertex set} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
László Egri, Dániel Marx, and Pawel Rzazewski. 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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{egri_et_al:LIPIcs.STACS.2018.27, author = {Egri, L\'{a}szl\'{o} and Marx, D\'{a}niel and Rzazewski, Pawel}, title = {{Finding List Homomorphisms from Bounded-treewidth Graphs to Reflexive Graphs: a Complete Complexity Characterization}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {27:1--27:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.27}, URN = {urn:nbn:de:0030-drops-84867}, doi = {10.4230/LIPIcs.STACS.2018.27}, annote = {Keywords: graph homomorphism, list homomorphism, reflexive graph, treewidth} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Dániel Marx and Marcin Pilipczuk. Subexponential Parameterized Algorithms for Graphs of Polynomial Growth. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{marx_et_al:LIPIcs.ESA.2017.59, author = {Marx, D\'{a}niel and Pilipczuk, Marcin}, title = {{Subexponential Parameterized Algorithms for Graphs of Polynomial Growth}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {59:1--59:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.59}, URN = {urn:nbn:de:0030-drops-78162}, doi = {10.4230/LIPIcs.ESA.2017.59}, annote = {Keywords: polynomial growth, subexponential algorithm, low treewidth pattern covering} }
Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)
Csaba Biró, Édouard Bonnet, Dániel Marx, Tillmann Miltzow, and Pawel Rzazewski. Fine-Grained Complexity of Coloring Unit Disks and Balls. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{biro_et_al:LIPIcs.SoCG.2017.18, author = {Bir\'{o}, Csaba and Bonnet, \'{E}douard and Marx, D\'{a}niel and Miltzow, Tillmann and Rzazewski, Pawel}, title = {{Fine-Grained Complexity of Coloring Unit Disks and Balls}}, booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)}, pages = {18:1--18:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-038-5}, ISSN = {1868-8969}, year = {2017}, volume = {77}, editor = {Aronov, Boris and Katz, Matthew J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.18}, URN = {urn:nbn:de:0030-drops-71800}, doi = {10.4230/LIPIcs.SoCG.2017.18}, annote = {Keywords: unit disk graphs, unit ball graphs, coloring, exact algorithm} }
Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)
Dániel Marx. Graphs, Hypergraphs, and the Complexity of Conjunctive Database Queries (Invited Talk). In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{marx:LIPIcs.ICDT.2017.2, author = {Marx, D\'{a}niel}, title = {{Graphs, Hypergraphs, and the Complexity of Conjunctive Database Queries}}, booktitle = {20th International Conference on Database Theory (ICDT 2017)}, pages = {2:1--2:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-024-8}, ISSN = {1868-8969}, year = {2017}, volume = {68}, editor = {Benedikt, Michael and Orsi, Giorgio}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.2}, URN = {urn:nbn:de:0030-drops-70652}, doi = {10.4230/LIPIcs.ICDT.2017.2}, annote = {Keywords: Conjunctive queries, treewidth, complexity} }
Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Lin Chen, Dániel Marx, Deshi Ye, and Guochuan Zhang. Parameterized and Approximation Results for Scheduling with a Low Rank Processing Time Matrix. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{chen_et_al:LIPIcs.STACS.2017.22, author = {Chen, Lin and Marx, D\'{a}niel and Ye, Deshi and Zhang, Guochuan}, title = {{Parameterized and Approximation Results for Scheduling with a Low Rank Processing Time Matrix}}, booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)}, pages = {22:1--22:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-028-6}, ISSN = {1868-8969}, year = {2017}, volume = {66}, editor = {Vollmer, Heribert and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.22}, URN = {urn:nbn:de:0030-drops-70110}, doi = {10.4230/LIPIcs.STACS.2017.22}, annote = {Keywords: APX-hardness, Parameterized algorithm, Scheduling, Exponential Time Hypothesis} }
Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Gábor Bacsó, Dániel Marx, and Zsolt Tuza. H-Free Graphs, Independent Sets, and Subexponential-Time Algorithms. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{bacso_et_al:LIPIcs.IPEC.2016.3, author = {Bacs\'{o}, G\'{a}bor and Marx, D\'{a}niel and Tuza, Zsolt}, title = {{H-Free Graphs, Independent Sets, and Subexponential-Time Algorithms}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, pages = {3:1--3:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-023-1}, ISSN = {1868-8969}, year = {2017}, volume = {63}, editor = {Guo, Jiong and Hermelin, Danny}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.3}, URN = {urn:nbn:de:0030-drops-69397}, doi = {10.4230/LIPIcs.IPEC.2016.3}, annote = {Keywords: independent set, scattered set, subexponential algorithms, H-free graphs} }
Published in: Dagstuhl Reports, Volume 6, Issue 5 (2016)
Jeff Erickson, Philip N. Klein, Dániel Marx, and Claire Mathieu. Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221). In Dagstuhl Reports, Volume 6, Issue 5, pp. 94-113, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@Article{erickson_et_al:DagRep.6.5.94, author = {Erickson, Jeff and Klein, Philip N. and Marx, D\'{a}niel and Mathieu, Claire}, title = {{Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221)}}, pages = {94--113}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2016}, volume = {6}, number = {5}, editor = {Erickson, Jeff and Klein, Philip N. and Marx, D\'{a}niel and Mathieu, Claire}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.5.94}, URN = {urn:nbn:de:0030-drops-67227}, doi = {10.4230/DagRep.6.5.94}, annote = {Keywords: Algorithms, planar graphs, theory, approximation, fixed-parameter tractable, network flow, network design, kernelization} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Dániel Marx, Ario Salmasi, and Anastasios Sidiropoulos. Constant-Factor Approximations for Asymmetric TSP on Nearly-Embeddable Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 16:1-16:54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{marx_et_al:LIPIcs.APPROX-RANDOM.2016.16, author = {Marx, D\'{a}niel and Salmasi, Ario and Sidiropoulos, Anastasios}, title = {{Constant-Factor Approximations for Asymmetric TSP on Nearly-Embeddable Graphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {16:1--16:54}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.16}, URN = {urn:nbn:de:0030-drops-66391}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.16}, annote = {Keywords: asymmetric TSP, approximation algorithms, nearly-embeddable graphs, Held-Karp LP, exponential time hypothesis} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Andreas Emil Feldmann and Dániel Marx. The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{feldmann_et_al:LIPIcs.ICALP.2016.27, author = {Feldmann, Andreas Emil and Marx, D\'{a}niel}, title = {{The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {27:1--27:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.27}, URN = {urn:nbn:de:0030-drops-63060}, doi = {10.4230/LIPIcs.ICALP.2016.27}, annote = {Keywords: Directed Steiner Tree, Directed Steiner Network, fixed-parameter tractability, dichotomy} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Dániel Marx and Valia Mitsou. Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{marx_et_al:LIPIcs.ICALP.2016.28, author = {Marx, D\'{a}niel and Mitsou, Valia}, title = {{Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {28:1--28:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.28}, URN = {urn:nbn:de:0030-drops-63078}, doi = {10.4230/LIPIcs.ICALP.2016.28}, annote = {Keywords: Parameterized Complexity, List coloring, Treewidth, Lower bounds under ETH} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, and Roman Rabinovich. Routing with Congestion in Acyclic Digraphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 7:1-7:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{amiri_et_al:LIPIcs.MFCS.2016.7, author = {Amiri, Saeed Akhoondian and Kreutzer, Stephan and Marx, D\'{a}niel and Rabinovich, Roman}, title = {{Routing with Congestion in Acyclic Digraphs}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {7:1--7:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.7}, URN = {urn:nbn:de:0030-drops-64244}, doi = {10.4230/LIPIcs.MFCS.2016.7}, annote = {Keywords: algorithms, disjoint paths, congestion, acyclic digraphs, XP, W\lbrack1\rbrack-hard} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Édouard Bonnet, László Egri, and Dániel Marx. Fixed-Parameter Approximability of Boolean MinCSPs. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{bonnet_et_al:LIPIcs.ESA.2016.18, author = {Bonnet, \'{E}douard and Egri, L\'{a}szl\'{o} and Marx, D\'{a}niel}, title = {{Fixed-Parameter Approximability of Boolean MinCSPs}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {18:1--18:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.18}, URN = {urn:nbn:de:0030-drops-63694}, doi = {10.4230/LIPIcs.ESA.2016.18}, annote = {Keywords: constraint satisfaction problems, approximability, fixed-parameter tractability} }
Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Dániel Marx. The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems (Invited Talk). In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, p. 32:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{marx:LIPIcs.SWAT.2016.32, author = {Marx, D\'{a}niel}, title = {{The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems}}, booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)}, pages = {32:1--32:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-011-8}, ISSN = {1868-8969}, year = {2016}, volume = {53}, editor = {Pagh, Rasmus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.32}, URN = {urn:nbn:de:0030-drops-60535}, doi = {10.4230/LIPIcs.SWAT.2016.32}, annote = {Keywords: Directed Steiner Tree, Directed Steiner Network, fixed-parameter tractability, dichotomy} }
Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)
Dániel Marx and Tillmann Miltzow. Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 52:1-52:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{marx_et_al:LIPIcs.SoCG.2016.52, author = {Marx, D\'{a}niel and Miltzow, Tillmann}, title = {{Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems}}, booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)}, pages = {52:1--52:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-009-5}, ISSN = {1868-8969}, year = {2016}, volume = {51}, editor = {Fekete, S\'{a}ndor and Lubiw, Anna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.52}, URN = {urn:nbn:de:0030-drops-59445}, doi = {10.4230/LIPIcs.SoCG.2016.52}, annote = {Keywords: computational geometry, triangulations, exponential-time algorithms} }
Published in: Dagstuhl Reports, Volume 5, Issue 7 (2016)
Andrei A. Bulatov, Venkatesan Guruswami, Andrei Krokhin, and Dániel Marx. The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301). In Dagstuhl Reports, Volume 5, Issue 7, pp. 22-41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@Article{bulatov_et_al:DagRep.5.7.22, author = {Bulatov, Andrei A. and Guruswami, Venkatesan and Krokhin, Andrei and Marx, D\'{a}niel}, title = {{The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301)}}, pages = {22--41}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2016}, volume = {5}, number = {7}, editor = {Bulatov, Andrei A. and Guruswami, Venkatesan and Krokhin, Andrei and Marx, D\'{a}niel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.7.22}, URN = {urn:nbn:de:0030-drops-56714}, doi = {10.4230/DagRep.5.7.22}, annote = {Keywords: Constraint satisfaction problem (CSP), Computational complexity, CSP dichotomy conjecture, Hardness of approximation, Unique games conjecture, Fixed-parameter tractability, Descriptive complexity, Universal algebra, Logic, Decomposition methods} }
Published in: Dagstuhl Reports, Volume 4, Issue 11 (2015)
Stefan Kratsch, Daniel Lokshtanov, Dániel Marx, and Peter Rossmanith. Optimality and tight results in parameterized complexity (Dagstuhl Seminar 14451). In Dagstuhl Reports, Volume 4, Issue 11, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@Article{kratsch_et_al:DagRep.4.11.1, author = {Kratsch, Stefan and Lokshtanov, Daniel and Marx, D\'{a}niel and Rossmanith, Peter}, title = {{Optimality and tight results in parameterized complexity (Dagstuhl Seminar 14451)}}, pages = {1--21}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2015}, volume = {4}, number = {11}, editor = {Kratsch, Stefan and Lokshtanov, Daniel and Marx, D\'{a}niel and Rossmanith, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.11.1}, URN = {urn:nbn:de:0030-drops-49677}, doi = {10.4230/DagRep.4.11.1}, annote = {Keywords: Algorithms, parameterized complexity, kernels, width measures, exponential time hypothesis, lower bounds} }
Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Yixin Cao and Dániel Marx. Chordal Editing is Fixed-Parameter Tractable. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 214-225, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{cao_et_al:LIPIcs.STACS.2014.214, author = {Cao, Yixin and Marx, D\'{a}niel}, title = {{Chordal Editing is Fixed-Parameter Tractable}}, booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)}, pages = {214--225}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-65-1}, ISSN = {1868-8969}, year = {2014}, volume = {25}, editor = {Mayr, Ernst W. and Portier, Natacha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.214}, URN = {urn:nbn:de:0030-drops-44591}, doi = {10.4230/LIPIcs.STACS.2014.214}, annote = {Keywords: chordal graph, parameterized computation, graph modification problems, chordal deletion, chordal completion, clique tree decomposition, holes, simplic} }
Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Dániel Marx and Michal Pilipczuk. Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask). In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 542-553, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{marx_et_al:LIPIcs.STACS.2014.542, author = {Marx, D\'{a}niel and Pilipczuk, Michal}, title = {{Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)}}, booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)}, pages = {542--553}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-65-1}, ISSN = {1868-8969}, year = {2014}, volume = {25}, editor = {Mayr, Ernst W. and Portier, Natacha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.542}, URN = {urn:nbn:de:0030-drops-44863}, doi = {10.4230/LIPIcs.STACS.2014.542}, annote = {Keywords: parameterized complexity, subgraph isomorphism} }
Published in: Dagstuhl Reports, Volume 3, Issue 10 (2014)
Glencora Borradaile, Philp Klein, Dániel Marx, and Claire Mathieu. Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 13421). In Dagstuhl Reports, Volume 3, Issue 10, pp. 36-57, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@Article{borradaile_et_al:DagRep.3.10.36, author = {Borradaile, Glencora and Klein, Philp and Marx, D\'{a}niel and Mathieu, Claire}, title = {{Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 13421)}}, pages = {36--57}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2014}, volume = {3}, number = {10}, editor = {Borradaile, Glencora and Klein, Philp and Marx, D\'{a}niel and Mathieu, Claire}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.10.36}, URN = {urn:nbn:de:0030-drops-44274}, doi = {10.4230/DagRep.3.10.36}, annote = {Keywords: Algorithms, planar graphs, theory, approximation, fixed-parameter tractable, network flow, network design, kernelization} }
Published in: Dagstuhl Reports, Volume 2, Issue 11 (2013)
Johan Hastad, Andrei Krokhin, and Dániel Marx. The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451). In Dagstuhl Reports, Volume 2, Issue 11, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@Article{hastad_et_al:DagRep.2.11.1, author = {Hastad, Johan and Krokhin, Andrei and Marx, D\'{a}niel}, title = {{The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451)}}, pages = {1--19}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2013}, volume = {2}, number = {11}, editor = {Hastad, Johan and Krokhin, Andrei and Marx, D\'{a}niel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.11.1}, URN = {urn:nbn:de:0030-drops-39764}, doi = {10.4230/DagRep.2.11.1}, annote = {Keywords: Constraint satisfaction problem (CSP); Computational complexity; CSP dichotomy conjecture; Hardness of approximation; Unique games conjceture; Fixed-parameter tractability; Descriptive complexity; niversal algebra; Logic; Decomposition methods} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Dániel Marx. Algorithmic Graph Structure Theory (Tutorial). In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, p. 7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{marx:LIPIcs.STACS.2013.7, author = {Marx, D\'{a}niel}, title = {{Algorithmic Graph Structure Theory}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {7--7}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.7}, URN = {urn:nbn:de:0030-drops-39175}, doi = {10.4230/LIPIcs.STACS.2013.7}, annote = {Keywords: Graph theory, graph minors, structure theorems} }
Published in: Dagstuhl Reports, Volume 2, Issue 6 (2012)
Michael R. Fellows, Jiong Guo, Dániel Marx, and Saket Saurabh. Data Reduction and Problem Kernels (Dagstuhl Seminar 12241). In Dagstuhl Reports, Volume 2, Issue 6, pp. 26-50, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@Article{fellows_et_al:DagRep.2.6.26, author = {Fellows, Michael R. and Guo, Jiong and Marx, D\'{a}niel and Saurabh, Saket}, title = {{Data Reduction and Problem Kernels (Dagstuhl Seminar 12241)}}, pages = {26--50}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2012}, volume = {2}, number = {6}, editor = {Fellows, Michael R. and Guo, Jiong and Marx, D\'{a}niel and Saurabh, Saket}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.6.26}, URN = {urn:nbn:de:0030-drops-37297}, doi = {10.4230/DagRep.2.6.26}, annote = {Keywords: Preprocessing, Fixed-parameter tractability, Parameterized algorithmics} }
Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)
Dániel Marx, Barry O'Sullivan, and Igor Razgon. Treewidth Reduction for Constrained Separation and Bipartization Problems. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 561-572, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{marx_et_al:LIPIcs.STACS.2010.2485, author = {Marx, D\'{a}niel and O'Sullivan, Barry and Razgon, Igor}, title = {{Treewidth Reduction for Constrained Separation and Bipartization Problems}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {561--572}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2485}, URN = {urn:nbn:de:0030-drops-24850}, doi = {10.4230/LIPIcs.STACS.2010.2485}, annote = {Keywords: Fixed-parameter algorithms, graph separation problems, treewidth} }
Published in: Dagstuhl Seminar Proceedings, Volume 9511, Parameterized complexity and approximation algorithms (2010)
Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dániel Marx. 09511 Abstracts Collection – Parameterized complexity and approximation algorithms. In Parameterized complexity and approximation algorithms. Dagstuhl Seminar Proceedings, Volume 9511, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{demaine_et_al:DagSemProc.09511.1, author = {Demaine, Erik D. and Hajiaghayi, MohammadTaghi and Marx, D\'{a}niel}, title = {{09511 Abstracts Collection – Parameterized complexity and approximation algorithms}}, booktitle = {Parameterized complexity and approximation algorithms}, pages = {1--14}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9511}, editor = {Erik D. Demaine and MohammadTaghi Hajiaghayi and D\'{a}niel Marx}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09511.1}, URN = {urn:nbn:de:0030-drops-25025}, doi = {10.4230/DagSemProc.09511.1}, annote = {Keywords: Parameterized complexity, Approximation algorithms} }
Published in: Dagstuhl Seminar Proceedings, Volume 9511, Parameterized complexity and approximation algorithms (2010)
Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dániel Marx. 09511 Executive Summary – Parameterized complexity and approximation algorithms. In Parameterized complexity and approximation algorithms. Dagstuhl Seminar Proceedings, Volume 9511, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{demaine_et_al:DagSemProc.09511.2, author = {Demaine, Erik D. and Hajiaghayi, MohammadTaghi and Marx, D\'{a}niel}, title = {{09511 Executive Summary – Parameterized complexity and approximation algorithms}}, booktitle = {Parameterized complexity and approximation algorithms}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9511}, editor = {Erik D. Demaine and MohammadTaghi Hajiaghayi and D\'{a}niel Marx}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09511.2}, URN = {urn:nbn:de:0030-drops-25011}, doi = {10.4230/DagSemProc.09511.2}, annote = {Keywords: Parameterized complexity, Approximation algorithms} }
Published in: Dagstuhl Seminar Proceedings, Volume 9511, Parameterized complexity and approximation algorithms (2010)
Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dániel Marx. 09511 Open Problems – Parameterized complexity and approximation algorithms. In Parameterized complexity and approximation algorithms. Dagstuhl Seminar Proceedings, Volume 9511, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{demaine_et_al:DagSemProc.09511.3, author = {Demaine, Erik D. and Hajiaghayi, MohammadTaghi and Marx, D\'{a}niel}, title = {{09511 Open Problems – Parameterized complexity and approximation algorithms}}, booktitle = {Parameterized complexity and approximation algorithms}, pages = {1--10}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9511}, editor = {Erik D. Demaine and MohammadTaghi Hajiaghayi and D\'{a}niel Marx}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09511.3}, URN = {urn:nbn:de:0030-drops-24992}, doi = {10.4230/DagSemProc.09511.3}, annote = {Keywords: Parameterized complexity, approximation algorithms, open problems} }
Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)
Andrei A. Bulatov, Victor Dalmau, Martin Grohe, and Daniel Marx. Enumerating Homomorphisms. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 231-242, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{bulatov_et_al:LIPIcs.STACS.2009.1838, author = {Bulatov, Andrei A. and Dalmau, Victor and Grohe, Martin and Marx, Daniel}, title = {{Enumerating Homomorphisms}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {231--242}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1838}, URN = {urn:nbn:de:0030-drops-18385}, doi = {10.4230/LIPIcs.STACS.2009.1838}, annote = {Keywords: } }
Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)
Daniel Marx. Tractable Structures for Constraint Satisfaction with Truth Tables. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 649-660, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{marx:LIPIcs.STACS.2009.1807, author = {Marx, Daniel}, title = {{Tractable Structures for Constraint Satisfaction with Truth Tables}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {649--660}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1807}, URN = {urn:nbn:de:0030-drops-18079}, doi = {10.4230/LIPIcs.STACS.2009.1807}, annote = {Keywords: Computational complexity, Constraint satisfaction, Treewidth, Adaptive width} }
Published in: Dagstuhl Seminar Proceedings, Volume 7281, Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs (2007)
Erik Demaine, Gregory Z. Gutin, Daniel Marx, and Ulrike Stege. 07281 Open Problems – Structure Theory and FPT Algorithmcs for Graphs, Digraphs and Hypergraphs. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Dagstuhl Seminar Proceedings, Volume 7281, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
@InProceedings{demaine_et_al:DagSemProc.07281.2, author = {Demaine, Erik and Gutin, Gregory Z. and Marx, Daniel and Stege, Ulrike}, title = {{07281 Open Problems – Structure Theory and FPT Algorithmcs for Graphs, Digraphs and Hypergraphs}}, booktitle = {Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs}, pages = {1--6}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2007}, volume = {7281}, editor = {Erik Demaine and Gregory Z. Gutin and Daniel Marx and Ulrike Stege}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07281.2}, URN = {urn:nbn:de:0030-drops-12542}, doi = {10.4230/DagSemProc.07281.2}, annote = {Keywords: } }
Published in: Dagstuhl Seminar Proceedings, Volume 7281, Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs (2007)
Erik Demaine, Gregory Z. Gutin, Daniel Marx, and Ulrike Stege. 07281 Abstracts Collection – Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Dagstuhl Seminar Proceedings, Volume 7281, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
@InProceedings{demaine_et_al:DagSemProc.07281.1, author = {Demaine, Erik and Gutin, Gregory Z. and Marx, Daniel and Stege, Ulrike}, title = {{07281 Abstracts Collection – Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs}}, booktitle = {Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs}, pages = {1--14}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2007}, volume = {7281}, editor = {Erik Demaine and Gregory Z. Gutin and Daniel Marx and Ulrike Stege}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07281.1}, URN = {urn:nbn:de:0030-drops-12450}, doi = {10.4230/DagSemProc.07281.1}, annote = {Keywords: Parameterized complexity, fixed-parameter tractability, graph structure theory} }
Feedback for Dagstuhl Publishing