LIPIcs, Volume 285
IPEC 2023, September 6-8, 2023, Amsterdam, The Netherlands
Editors: Neeldhara Misra and Magnus Wahlström
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Enver Aman, Karthik C. S., and Sharath Punna. On Connections Between k-Coloring and Euclidean k-Means. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{aman_et_al:LIPIcs.ESA.2024.9, author = {Aman, Enver and Karthik C. S. and Punna, Sharath}, title = {{On Connections Between k-Coloring and Euclidean k-Means}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {9:1--9:18}, 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.9}, URN = {urn:nbn:de:0030-drops-210808}, doi = {10.4230/LIPIcs.ESA.2024.9}, annote = {Keywords: k-means, k-minsum, Euclidean space, fine-grained complexity} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Aritra Banik, Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Satyabrata Jana, and Saket Saurabh. Cuts in Graphs with Matroid Constraints. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{banik_et_al:LIPIcs.ESA.2024.17, author = {Banik, Aritra and Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Jana, Satyabrata and Saurabh, Saket}, title = {{Cuts in Graphs with Matroid Constraints}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {17:1--17:15}, 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.17}, URN = {urn:nbn:de:0030-drops-210887}, doi = {10.4230/LIPIcs.ESA.2024.17}, annote = {Keywords: s-t-cut, multiway Cut, matroid, odd cycle transversal, feedback vertex set, fixed-parameter tractability} }
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 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Paloma T. Lima, Martin Milanič, Peter Muršič, Karolina Okrasa, Paweł Rzążewski, and Kenny Štorgel. Tree Decompositions Meet Induced Matchings: Beyond Max Weight Independent Set. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 85:1-85:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{lima_et_al:LIPIcs.ESA.2024.85, author = {Lima, Paloma T. and Milani\v{c}, Martin and Mur\v{s}i\v{c}, Peter and Okrasa, Karolina and Rz\k{a}\.{z}ewski, Pawe{\l} and \v{S}torgel, Kenny}, title = {{Tree Decompositions Meet Induced Matchings: Beyond Max Weight Independent Set}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {85:1--85:17}, 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.85}, URN = {urn:nbn:de:0030-drops-211569}, doi = {10.4230/LIPIcs.ESA.2024.85}, annote = {Keywords: induced matching treewidth, tree-independence number, feedback vertex set, induced packing, algorithmic meta-theorem} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
George Osipov, Marcin Pilipczuk, and Magnus Wahlström. Parameterized Complexity of MinCSP over the Point Algebra. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 93:1-93:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{osipov_et_al:LIPIcs.ESA.2024.93, author = {Osipov, George and Pilipczuk, Marcin and Wahlstr\"{o}m, Magnus}, title = {{Parameterized Complexity of MinCSP over the Point Algebra}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {93:1--93:15}, 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.93}, URN = {urn:nbn:de:0030-drops-211640}, doi = {10.4230/LIPIcs.ESA.2024.93}, annote = {Keywords: parameterized complexity, constraint satisfaction, point algebra, multicut, feedback arc set} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Mingyu Xiao. Solving Directed Multiway Cut Faster Than 2ⁿ. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 104:1-104:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{xiao:LIPIcs.ESA.2024.104, author = {Xiao, Mingyu}, title = {{Solving Directed Multiway Cut Faster Than 2ⁿ}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {104:1--104:13}, 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.104}, URN = {urn:nbn:de:0030-drops-211758}, doi = {10.4230/LIPIcs.ESA.2024.104}, annote = {Keywords: Exact Algorithms, Parameterized Algorithms, Directed Multiway Cut, Directed Multicut, Directed Graphs} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi. Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{lokshtanov_et_al:LIPIcs.APPROX/RANDOM.2024.6, author = {Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket and Xue, Jie and Zehavi, Meirav}, title = {{Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {6:1--6:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.6}, URN = {urn:nbn:de:0030-drops-209990}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.6}, annote = {Keywords: bipartization, geometric intersection graphs, approximation algorithms} }
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)
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} }
Feedback for Dagstuhl Publishing