LIPIcs, Volume 285
IPEC 2023, September 6-8, 2023, Amsterdam, The Netherlands
Editors: Neeldhara Misra and Magnus Wahlström
Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)
Peter Jonsson, Victor Lagerkvist, and George Osipov. CSPs with Few Alien Constraints. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{jonsson_et_al:LIPIcs.CP.2024.15, author = {Jonsson, Peter and Lagerkvist, Victor and Osipov, George}, title = {{CSPs with Few Alien Constraints}}, booktitle = {30th International Conference on Principles and Practice of Constraint Programming (CP 2024)}, pages = {15:1--15:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-336-2}, ISSN = {1868-8969}, year = {2024}, volume = {307}, editor = {Shaw, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.15}, URN = {urn:nbn:de:0030-drops-207005}, doi = {10.4230/LIPIcs.CP.2024.15}, annote = {Keywords: Constraint satisfaction, parameterized complexity, hybrid theories} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Tian Bai and Mingyu Xiao. Breaking the Barrier 2^k for Subset Feedback Vertex Set in Chordal Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bai_et_al:LIPIcs.MFCS.2024.15, author = {Bai, Tian and Xiao, Mingyu}, title = {{Breaking the Barrier 2^k for Subset Feedback Vertex Set in Chordal Graphs}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {15:1--15:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.15}, URN = {urn:nbn:de:0030-drops-205711}, doi = {10.4230/LIPIcs.MFCS.2024.15}, annote = {Keywords: Subset Feedback Vertex Set, Prize-Collecting Maximum Independent Set, Parameterized Algorithms, Split Graphs, Chordal Graphs, Dulmage-Mendelsohn Decomposition} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Max Bannach, Florian Chudigiewitsch, and Till Tantau. On the Descriptive Complexity of Vertex Deletion Problems. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bannach_et_al:LIPIcs.MFCS.2024.17, author = {Bannach, Max and Chudigiewitsch, Florian and Tantau, Till}, title = {{On the Descriptive Complexity of Vertex Deletion Problems}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {17:1--17:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.17}, URN = {urn:nbn:de:0030-drops-205733}, doi = {10.4230/LIPIcs.MFCS.2024.17}, annote = {Keywords: graph problems, fixed-parameter tractability, descriptive complexity, vertex deletion} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Arnaud Casteigts, Nils Morawietz, and Petra Wolf. Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 36:1-36:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{casteigts_et_al:LIPIcs.MFCS.2024.36, author = {Casteigts, Arnaud and Morawietz, Nils and Wolf, Petra}, title = {{Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {36:1--36:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.36}, URN = {urn:nbn:de:0030-drops-205923}, doi = {10.4230/LIPIcs.MFCS.2024.36}, annote = {Keywords: Temporal graphs, Parameterized complexity, Reachability, Transitivity} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Shyan Akmal, Virginia Vassilevska Williams, and Nicole Wein. Detecting Disjoint Shortest Paths in Linear Time and More. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{akmal_et_al:LIPIcs.ICALP.2024.9, author = {Akmal, Shyan and Vassilevska Williams, Virginia and Wein, Nicole}, title = {{Detecting Disjoint Shortest Paths in Linear Time and More}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {9:1--9: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.9}, URN = {urn:nbn:de:0030-drops-201529}, doi = {10.4230/LIPIcs.ICALP.2024.9}, annote = {Keywords: disjoint shortest paths, algebraic graph algorithms, disjoint paths, fine-grained complexity, clique} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Matthias Bentert, Pål Grønås Drange, Fedor V. Fomin, Petr A. Golovach, and Tuukka Korhonen. Two-Sets Cut-Uncut on Planar Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bentert_et_al:LIPIcs.ICALP.2024.22, author = {Bentert, Matthias and Drange, P\r{a}l Gr{\o}n\r{a}s and Fomin, Fedor V. and Golovach, Petr A. and Korhonen, Tuukka}, title = {{Two-Sets Cut-Uncut on Planar Graphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {22:1--22:18}, 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.22}, URN = {urn:nbn:de:0030-drops-201654}, doi = {10.4230/LIPIcs.ICALP.2024.22}, annote = {Keywords: planar graphs, cut-uncut, group-constrained paths} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Marin Bougeret, Bart M. P. Jansen, and Ignasi Sau. Kernelization Dichotomies for Hitting Subgraphs Under Structural Parameterizations. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 33:1-33:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bougeret_et_al:LIPIcs.ICALP.2024.33, author = {Bougeret, Marin and Jansen, Bart M. P. and Sau, Ignasi}, title = {{Kernelization Dichotomies for Hitting Subgraphs Under Structural Parameterizations}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {33:1--33:20}, 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.33}, URN = {urn:nbn:de:0030-drops-201766}, doi = {10.4230/LIPIcs.ICALP.2024.33}, annote = {Keywords: hitting subgraphs, hitting induced subgraphs, parameterized complexity, polynomial kernel, complexity dichotomy, elimination distance} }
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)
Nick Fischer and Leo Wennmann. Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 64:1-64:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{fischer_et_al:LIPIcs.ICALP.2024.64, author = {Fischer, Nick and Wennmann, Leo}, title = {{Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {64:1--64:15}, 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.64}, URN = {urn:nbn:de:0030-drops-202079}, doi = {10.4230/LIPIcs.ICALP.2024.64}, annote = {Keywords: Scheduling, Fine-Grained Complexity, Dynamic Strings} }
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 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Carla Groenland, Isja Mannens, Jesper Nederlof, Marta Piecyk, and Paweł Rzążewski. Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Matrix Parameters. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 77:1-77:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{groenland_et_al:LIPIcs.ICALP.2024.77, author = {Groenland, Carla and Mannens, Isja and Nederlof, Jesper and Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}}, title = {{Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Matrix Parameters}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {77:1--77:21}, 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.77}, URN = {urn:nbn:de:0030-drops-202208}, doi = {10.4230/LIPIcs.ICALP.2024.77}, annote = {Keywords: graph homomorphism, cutwidth, asymptotic matrix parameters} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Antoine Mottet, Tomáš Nagy, and Michael Pinsker. An Order out of Nowhere: A New Algorithm for Infinite-Domain {CSP}s. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 148:1-148:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mottet_et_al:LIPIcs.ICALP.2024.148, author = {Mottet, Antoine and Nagy, Tom\'{a}\v{s} and Pinsker, Michael}, title = {{An Order out of Nowhere: A New Algorithm for Infinite-Domain \{CSP\}s}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {148:1--148:18}, 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.148}, URN = {urn:nbn:de:0030-drops-202912}, doi = {10.4230/LIPIcs.ICALP.2024.148}, annote = {Keywords: Constraint Satisfaction Problems, Hypergraphs, Polymorphisms} }
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 1-644, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@Proceedings{misra_et_al:LIPIcs.IPEC.2023, title = {{LIPIcs, Volume 285, IPEC 2023, Complete Volume}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {1--644}, 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}, URN = {urn:nbn:de:0030-drops-194183}, doi = {10.4230/LIPIcs.IPEC.2023}, annote = {Keywords: LIPIcs, Volume 285, IPEC 2023, Complete Volume} }
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{misra_et_al:LIPIcs.IPEC.2023.0, author = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {0:i--0:xviii}, 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.0}, URN = {urn:nbn:de:0030-drops-194191}, doi = {10.4230/LIPIcs.IPEC.2023.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Feedback for Dagstuhl Publishing