Publications

Conference: ACM/SIAM Symposium on Discrete Algorithms

Number of publications: 48

2025

• Romain Bourneuf, Marcin Pilipczuk , Bounding ε-scatter dimension via metric sparsity, Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), Nowy Orlean, Luizjana, the United States of America, 12 January 2025 - 15 January 2025. See in PBN
• Hsien-Chih Chang, Vincent Cohen-Addad, Jonathan Conroy, Hung Le, Marcin Pilipczuk , Michał Pilipczuk , Embedding Planar Graphs into Graphs of Treewidth O (log^3 n ), Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), Nowy Orlean, Luizjana, the United States of America, 12 January 2025 - 15 January 2025. See in PBN
• Vikrant Ashvinkumar, Aaron Bernstein, Adam Karczmarz , Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs, 36th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, the United States of America, 11 January 2025 - 14 January 2025. See in PBN
• Michał Włodarczyk , Losing Treewidth In The Presence Of Weights, Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), Nowy Orlean, Luizjana, the United States of America, 12 January 2025 - 15 January 2025. See in PBN
• Adam Karczmarz , Da Wei Zheng, Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more, 36th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, the United States of America, 11 January 2025 - 14 January 2025. See in PBN

2024

• Jana Cslovjecsek, Michał Pilipczuk , Karol Węgrzycki, A polynomial-time OPTɛ-approximation algorithm for maximum independent set of connected subgraphs in a planar graph, 35th 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, Alexandria, the United States of America, 7 January 2024 - 10 January 2024. See in PBN
• Gwenaël Joret, Piotr Micek, Michał Pilipczuk , Bartosz Walczak, Cliquewidth and dimension, 35th 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, Alexandria, the United States of America, 7 January 2024 - 10 January 2024. See in PBN
• Adam Karczmarz , Wojciech Nadara , Marek Sokołowski , Exact Shortest Paths with Rational Weights on the Word RAM, 35th 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, Alexandria, the United States of America, 7 January 2024 - 10 January 2024. See in PBN
• Tuukka Korhonen, Wojciech Nadara , Michał Pilipczuk , Marek Sokołowski , Fully dynamic approximation schemes on planar and apex-minor-free graphs, 35th 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, Alexandria, the United States of America, 7 January 2024 - 10 January 2024. See in PBN
• Adam Karczmarz , Max s, t-Flow Oracles and Negative Cycle Detection in Planar Digraphs, 35th 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, Alexandria, the United States of America, 7 January 2024 - 10 January 2024. See in PBN
• Jana Cslovjecsek, Martin Koutecký, Alexandra Lassota, Michał Pilipczuk , Adam Polak, Parameterized algorithms for block-structured integer programs with large entries, 35th 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, Alexandria, the United States of America, 7 January 2024 - 10 January 2024. See in PBN
• Jesse Campion Loth, Kevin Halasz, Tomáš Masařík , Bojan Mohar, Robert Šámal, Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic, 35th 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, Alexandria, the United States of America, 7 January 2024 - 10 January 2024. See in PBN
• Mathieu Mari , Anish Mukherjee, Michał Pilipczuk , Piotr Sankowski , Shortest Disjoint Paths on a Grid, 35th 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, Alexandria, the United States of America, 7 January 2024 - 10 January 2024. See in PBN
• Paweł Rzążewski , Maria Chudnovsky, McCarty Rose, Michał Pilipczuk, Marcin Pilipczuk, Sparse induced subgraphs in P_6-free graphs, ACM-SIAM Symposium on Discrete Algorithms (SODA24), Alexandria, the United States of America, 6 January 2024 - 9 January 2024. See in PBN

2023

• Lars Jaffke, Paloma Thomé de Lima, Tomáš Masařík , Marcin Pilipczuk , Uéverton Dos Santos Souza, A tight quasi-polynomial bound for Global Label Min-Cut, Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms, 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, Florencja, Italy, 22 January 2023 - 25 January 2023. See in PBN
• Meike Hatzel, Lars Jaffke, Paloma Thomé de Lima, Tomáš Masařík , Marcin Pilipczuk , Roohani Sharma, Manuel Sorge, Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation, Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms, 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, Florencja, Italy, 22 January 2023 - 25 January 2023. See in PBN
• Eun Jung, Stefan Kratsch, Marcin Pilipczuk , Magnus Wahlstr¨om, Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints, 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, Florencja, Italy, 22 January 2023 - 25 January 2023. See in PBN
• Francois Dross, Krzysztof Fleszar , Karol Węgrzycki, Anna Zych-Pawlewicz , Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing Euclidean Travelling Salesman Tours, 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, Florencja, Italy, 22 January 2023 - 25 January 2023. See in PBN
• Stefan Göller, Paweł Parys , Weak Bisimulation Finiteness of Pushdown Systems With Deterministic ε-Transitions Is 2-EXPTIME-Complete, 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, Florencja, Italy, 22 January 2023 - 25 January 2023. See in PBN

2022

• Paweł Rzążewski , Jacob Focke, Dániel Marx, Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds, Thirty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, Alexandria (Virginia), the United States of America, 8 January 2022 - 11 January 2022. See in PBN
• Adam Karczmarz , Improved Strongly Polynomial Algorithms for Deterministic MDPs, 2VPI Feasibility, and Discounted All-Pairs Shortest Paths, 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, Alexandria, VA, the United States of America, 9 January 2022 - 12 January 2022. See in PBN
• Paweł Rzążewski , Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws, Thirty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, Alexandria (Virginia), the United States of America, 8 January 2022 - 11 January 2022. See in PBN

2021

• Adam Karczmarz , Piotr Sankowski , A Deterministic Parallel {APSP} Algorithm and its Applications, the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), Alexandria, Virginia (Virtual Conference), the United States of America, 10 January 2021 - 13 January 2021. See in PBN
• Jesper Nederlof, Jakub Pawlewicz , Celine Swennenhuis, Karol Węgrzycki, A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics, the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), Alexandria, Virginia (Virtual Conference), the United States of America, 10 January 2021 - 13 January 2021. See in PBN
• Carla Groenl, Gwenael Joret, Wojciech Nadara , Bartosz Walczak, Approximating pathwidth for graphs of small treewidth, the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), Alexandria, Virginia (Virtual Conference), the United States of America, 10 January 2021 - 13 January 2021. See in PBN
• Jiehua Chen, Wojciech Czerwiński , Yann Disser, Andreas Emil Feldmann, Danny Hermelin, Wojciech Nadara , Marcin Pilipczuk , Michał Pilipczuk , Manuel Sorge, Anna Zych-Pawlewicz , Efficient fully dynamic elimination forests with applications to detecting long paths and cycles, the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), Alexandria, Virginia (Virtual Conference), the United States of America, 10 January 2021 - 13 January 2021. See in PBN
• Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk , Paweł Rzążewski , Paul Seymour, Induced subgraphs of bounded treewidth and the container method, the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), Alexandria, Virginia (Virtual Conference), the United States of America, 10 January 2021 - 13 January 2021. See in PBN
• Stefan Kratsch, Tomáš Masařík , Irene Muzi, Marcin Pilipczuk , Manuel Sorge, Optimal Discretization is Fixed-parameter Tractable, the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), Alexandria, Virginia (Virtual Conference), the United States of America, 10 January 2021 - 13 January 2021. See in PBN
• Giuseppe F. Italiano, Adam Karczmarz , Nikos Parotsidis, Planar Reachability Under Single Vertex or Edge Failures, the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), Alexandria, Virginia (Virtual Conference), the United States of America, 10 January 2021 - 13 January 2021. See in PBN
• Jaroslav Nešetřil, Patrice Ossona de Mendez, Michał Pilipczuk , Roman Rabinovich, Sebastian Siebertz, Rankwidth meets stability*, the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), Alexandria, Virginia (Virtual Conference), the United States of America, 10 January 2021 - 13 January 2021. See in PBN
• Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk , Magnus Wahlström, Solving hard cut problems via flow-augmentation*, the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), Alexandria, Virginia (Virtual Conference), the United States of America, 10 January 2021 - 13 January 2021. See in PBN
• Miguel Romero, Marcin Wrochna , Stanislav Živný, Treewidth-pliability and PTAS for Max-CSPS, the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), Alexandria, Virginia (Virtual Conference), the United States of America, 10 January 2021 - 13 January 2021. See in PBN

2020

• Karolina Okrasa, Paweł Rzążewski , Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs, 31st ACM-SIAM Symposium on Discrete Algorithms, Salt Lake City, the United States of America, 5 January 2020 - 8 January 2020. See in PBN
• Marcin Wrochna , Stanislav Živný, Improved hardness for H-colourings of G-colourable graphs, 31st ACM-SIAM Symposium on Discrete Algorithms, Salt Lake City, the United States of America, 5 January 2020 - 8 January 2020. See in PBN
• Maria Chudnovsky, Marcin Pilipczuk , Michał Pilipczuk , Stéphan Thomassé, Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs, 31st ACM-SIAM Symposium on Discrete Algorithms, Salt Lake City, the United States of America, 5 January 2020 - 8 January 2020. See in PBN
• Marthe Bonamy, Cyril Gavoille, Michał Pilipczuk , Shorter Labeling Schemes for Planar Graphs, 31st ACM-SIAM Symposium on Discrete Algorithms, Salt Lake City, the United States of America, 5 January 2020 - 8 January 2020. See in PBN

2019

• Chris Schwiegelshohn, Shay Solomon, Fabrizio Grandoni, Stefano Leonardi, Piotr Sankowski , (1 + \(ε\))-Approximate Incremental Matching in Constant Deterministic Amortized Time, 30th ACM-SIAM Symposium on Discrete Algorithms, San Diego, the United States of America, 6 January 2019 - 9 January 2019. See in PBN
• Antonios Antoniadis, Krzysztof Fleszar , Ruben Hoeksma, Kevin Schewior, A PTAS for Euclidean TSP with Hyperplane Neighborhoods, 30th ACM-SIAM Symposium on Discrete Algorithms, San Diego, the United States of America, 6 January 2019 - 9 January 2019. See in PBN
• Marcin Mucha , Karol Węgrzycki, Michał Włodarczyk , A Subquadratic Approximation Scheme for Partition, 30th ACM-SIAM Symposium on Discrete Algorithms, San Diego, the United States of America, 6 January 2019 - 9 January 2019. See in PBN
• Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, Michał Włodarczyk , Losing Treewidth by Separating Subsets, 30th ACM-SIAM Symposium on Discrete Algorithms, San Diego, the United States of America, 6 January 2019 - 9 January 2019. See in PBN
• Michał Pilipczuk , Sebastian Siebertz, Polynomial bounds for centered colorings on proper minor-closed graph classes, 30th ACM-SIAM Symposium on Discrete Algorithms, San Diego, the United States of America, 6 January 2019 - 9 January 2019. See in PBN
• Tereza Klimošová, Andrzej Grzesik, Marcin Pilipczuk , Michał Pilipczuk , Polynomial-time algorithm for maximum weight independent set on P_{6}-free graphs, 30th ACM-SIAM Symposium on Discrete Algorithms, San Diego, the United States of America, 6 January 2019 - 9 January 2019. See in PBN
• Wojciech Czerwiński , Laure Daviaud, Nathanaël Fijalkow, Marcin Jurdziński, Ranko Lazić, Paweł Parys , Universal Trees Grow Inside Separating Automata: Quasi-Polynomial Lower Bounds for Parity Games, 30th ACM-SIAM Symposium on Discrete Algorithms, San Diego, the United States of America, 6 January 2019 - 9 January 2019. See in PBN

2018

• Adam Karczmarz , Decremental Transitive Closure and Shortest Paths for Planar Digraphs and Beyond, 29th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, the United States of America, 7 January 2018 - 10 January 2018. See in PBN
• Paweł Gawrychowski, Adam Karczmarz , Tomasz Kociumaka, Piotr Sankowski , Jakub Łącki, Optimal dynamic strings, 29th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, the United States of America, 7 January 2018 - 10 January 2018. See in PBN

2017

• Bart M. P. Jansen, Marcin Pilipczuk , Approximation and Kernelization for Chordal Vertex Deletion, 28th ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 16 January 2017 - 19 January 2017. See in PBN
• Fedor V. Fomin, Daniel Lokshtanov, Michał Pilipczuk , Saket Saurabh, Marcin Wrochna , Fully polynomial-time parameterized computations for graphs and matrices of low treewidth, 28th ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 16 January 2017 - 19 January 2017. See in PBN
• Michael B. Cohen, Aleksander Mądry, Piotr Sankowski , Adrian Vladu, Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ(m^10/7 log W) Time, 28th ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 16 January 2017 - 19 January 2017. See in PBN