2025
Jacob Holm, Wojciech Nadara, Eva Rotenberg, Marek Sokołowski
Fully Dynamic Biconnectivity in Õ(log² n) Time
57th Annual ACM Symposium on Theory of Computing, STOC 2025
Jan Dreier, Szymon Toruńczyk
Merge-width and First-Order model checking
57th Annual ACM Symposium on Theory of Computing, STOC 2025
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)
36th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025
2024
Tuukka Korhonen, Michał Pilipczuk, Giannos Stamoulis
Minor Containment and Disjoint Paths in almost-linear time
65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024
Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann, Rose McCarty, Michał Pilipczuk, Szymon Toruńczyk
First-Order model checking on monadically stable graph classes
65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024
Jana Cslovjecsek, Michał Pilipczuk, Karol Węgrzycki
Parameterized approximation for Maximum Weight Independent Set of rectangles and segments
32nd Annual European Symposium on Algorithms, ESA 2024
Konrad Majewski, Michał Pilipczuk, Anna Zych-Pawlewicz
Parameterized dynamic data structure for Split Completion
32nd Annual European Symposium on Algorithms, ESA 2024
Jakub Gajarský, Michał Pilipczuk, Marek Sokołowski, Giannos Stamoulis, Szymon Toruńczyk
Elementary first-order model checking for sparse graphs
39th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2024
Tuukka Korhonen, Marek Sokołowski
Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
56th Annual ACM Symposium on Theory of Computing, STOC 2024
Peter Gartland, Daniel Lokshtanov, Tomáš Masařík, Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski
Maximum Weight Independent Set in graphs with no long claws in quasi-polynomial time
56th Annual ACM Symposium on Theory of Computing, STOC 2024
Jan Dreier, Nikolas Mählmann, Szymon Toruńczyk
Flip-breakability: a combinatorial dichotomy for monadically dependent graph classes
56th Annual ACM Symposium on Theory of Computing, STOC 2024
Katarzyna Kowalska, Michał Pilipczuk
Parameterized and approximation algorithms for covering points with segments in the plane
41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024
Łukasz Kowalik, Alexandra Lassota, Konrad Majewski, Michał Pilipczuk, Marek Sokołowski
Detecting points in integer cones of polytopes is double-exponentially hard
7th Symposium on Simplicity in Algorithms, SOSA 2024
Antonio Casares, Marcin Pilipczuk, Michał Pilipczuk, Uéverton S. Souza, K. S. Thejaswini
Simple and tight complexity lower bounds for solving Rabin games
7th Symposium on Simplicity in Algorithms, SOSA 2024
Tuukka Korhonen, Wojciech Nadara, Michał Pilipczuk, Marek Sokołowski
Fully dynamic approximation schemes on planar and apex-minor-free graphs
35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
Mathieu Mari, Anish Mukherjee, Michał Pilipczuk, Piotr Sankowski
Shortest Disjoint Paths on a grid
35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 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 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
Jana Cslovjecsek, Martin Koutecký, Alexandra Lassota, Michał Pilipczuk, Adam Polak
Parameterized algorithms for block-structured integer programs with large entries
35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
Gwenaël Joret, Piotr Micek, Michał Pilipczuk, Bartosz Walczak
Cliquewidth and dimension
35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
Maria Chudnovsky, Rose McCarty, Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski
Sparse induced subgraphs in P6-free graphs
35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
Adam Karczmarz, Wojciech Nadara, Marek Sokołowski
Exact shortest paths with rational weights on the word RAM
35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
2023
Jesper Nederlof, Michał Pilipczuk, Karol Węgrzycki
Bounding generalized coloring numbers of planar graphs using coin models
Electronic Journal of Combinatorics 30(3), 2023
Michał Pilipczuk, Marek Sokołowski
Graphs of bounded twin-width are quasi-polynomially χ-bounded
Journal of Combinatorial Theory, Series B 161: 382-406, 2023
Marco Caoduro, Jana Cslovjecsek, Michał Pilipczuk, Karol Węgrzycki
On the independence number of intersection graphs of axis-parallel segments
Journal of Computational Geometry 14(1), 2023
Marthe Bonamy, Jadwiga Czyżewska, Łukasz Kowalik, Michał Pilipczuk
Partitioning edges of a planar graph into linear forests and a matching
Journal of Graph Theory 104(3): 659-677, 2023
Marcin Briański, Gwenaël Joret, Konrad Majewski, Piotr Micek, Michał T. Seweryn, Roohani Sharma
Treedepth vs circumference
Combinatorica, 43(4): 659-664, 2023
Albert Atserias, Joanna Fijalkow
Definable ellipsoid method, sums-of-squares proofs, and the Graph Isomorphism problem
SIAM Journal on Computing, 52(5): 1193-1229, 2023
Natasha Morrison, JD Nir, Sergey Norin, Paweł Rzążewski, Alexandra Wesolek
Every graph is eventually Turán-good
Journal of Combinatorial Theory, series B, 162: 231-243, 2023
Pierre Ohlmann
Characterizing positionality in games of infinite duration over infinite graphs
TheoretiCS 2(3), 2023
Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guśpiel, Petr Hliněný, Filip Pokrývka, Marek Sokołowski
Sparse graphs of twin-width 2 have bounded tree-width
34th International Symposium on Algorithms and Computation, ISAAC 2023
Tuukka Korhonen, Konrad Majewski, Wojciech Nadara, Michał Pilipczuk, Marek Sokolowski
Dynamic treewidth
64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023
Vincent Cohen-Addad, Hung Le, Marcin Pilipczuk, Michał Pilipczuk
Planar and minor-free metrics embed into metrics of polylogarithmic treewidth with expected multiplicative distortion arbitrarily close to 1
64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023
Szymon Toruńczyk
Flip-width: Cops and Robber on dense graphs
64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023
Benjamin Bergougnoux, Vera Chekan, Robert Ganian, Mamadou Moustapha Kanté, Matthias Mnich, Sang-il Oum, Michał Pilipczuk, Erik Jan van Leeuwen
Space-efficient parameterized algorithms on graphs of low shrubdepth
31st Annual European Symposium on Algorithms, ESA 2023
Mathieu Mari, Timothé Picavet, Michał Pilipczuk
A parameterized approximation scheme for the Geometric Knapsack problem with wide items
18th International Symposium on Parameterized and Exact Computation, IPEC 2023
Hans L. Bodlaender, Carla Groenland, Michał Pilipczuk
Parameterized complexity of binary CSP: vertex cover, treedepth, and related parameters
50th International Colloquium on Automata, Languages, and Programming, ICALP 2023; track A
Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, Szymon Toruńczyk
Indiscernibles and flatness in monadically stable and monadically NIP classes
50th International Colloquium on Automata, Languages, and Programming, ICALP 2023; track B
Jakub Gajarský, Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michał Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Sokołowski, Szymon Toruńczyk
Flipper games for monadically stable graph classes
50th International Colloquium on Automata, Languages, and Programming, ICALP 2023; track B
Pierre Ohlmann, Michał Pilipczuk, Wojciech Przybyszewski, Szymon Toruńczyk
Canonical decompositions in monadically stable and bounded shrubdepth graph classes
50th International Colloquium on Automata, Languages, and Programming, ICALP 2023; track B
Antonio Casares, Pierre Ohlmann
Characterising memory in infinite games
50th International Colloquium on Automata, Languages, and Programming, ICALP 2023; track B
Lorenzo Clemente, Maria Donten-Bury, Filip Mazowiecki, Michał Pilipczuk
On rational recursive sequences
40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023
Jędrzej Olkowski, Michał Pilipczuk, Mateusz Rychlicki, Karol Węgrzycki, Anna Zych-Pawlewicz
Dynamic data structures for parameterized string problems
40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023
Konrad Majewski, Michał Pilipczuk, Marek Sokołowski
On maintaining CMSO₂ properties on dynamic structures with bounded feedback vertex number
40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023
Meike Hatzel, Konrad Majewski, Michał Pilipczuk, Marek Sokołowski
Simpler and faster algorithms for detours in planar digraphs
6th Symposium on Simplicity in Algorithms, SOSA 2023
2022
Patrice Ossona de Mendez, Michał Pilipczuk, Sebastian Siebertz
Transducing paths in graph classes with unbounded shrubdepth
European Journal of Combinatorics, In Press:103660, 2022
Pavel Dvořák, Tomáš Masařík, Jana Novotná, Monika Krawczyk, Paweł Rzążewski, Aneta Żuk
List locally surjective homomorphisms in hereditary graph classes
33rd International Symposium on Algorithms and Computation, ISAAC 2022
K. S. Thejaswini, Pierre Ohlmann, Marcin Jurdziński
A technique to speed up symmetric attractor-based algorithms for parity games
42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022
Łukasz Bożyk, Michał Pilipczuk
Polynomial kernel for immersion hitting in tournaments
30th Annual European Symposium on Algorithms, ESA 2022
Wojciech Nadara, Michał Pilipczuk, Marcin Smulewicz
Computing treedepth in polynomial space and linear FPT time
30th Annual European Symposium on Algorithms, ESA 2022
Jakub Gajarský, Lars Jaffke, Paloma T. Lima, Jana Novotná, Marcin Pilipczuk, Paweł Rzążewski, Uéverton S. Souza
Taming graphs with no large creatures and skinny ladders
30th Annual European Symposium on Algorithms, ESA 2022
Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk, Michał Pilipczuk
On the complexity of problems on tree-structured graphs
17th International Symposium on Parameterized and Exact Computation, IPEC 2022
Michał Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz, Szymon Toruńczyk, Alexandre Vigny
Algorithms and data structures for First-Order logic with connectivity under vertex failures
49th International Colloquium on Automata, Languages, and Programming, ICALP 2022; track A
Konrad Majewski, Tomáš Masařík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, Marek Sokołowski
Max Weight Independent Set in graphs with no long claws: an analog of the Gyárfás' path argument
49th International Colloquium on Automata, Languages, and Programming, ICALP 2022; track A
Jakub Gajarský, Michał Pilipczuk, Wojciech Przybyszewski, Szymon Toruńczyk
Twin-width and types
49th International Colloquium on Automata, Languages, and Programming, ICALP 2022; track B
Jan Dreier, Jakub Gajarský, Sandra Kiefer, Michał Pilipczuk, Szymon Toruńczyk
Treelike decompositions for transductions of sparse graphs
37th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2022
Jakub Gajarský, Michał Pilipczuk, Szymon Toruńczyk
Stable graphs of bounded twin-width
37th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2022
Édouard Bonnet, Jan Dreier, Jakub Gajarský, Stephan Kreutzer, Nikolas Mählmann, Pierre Simon, Szymon Toruńczyk
Model checking on interpretations of classes of bounded local cliquewidth
37th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2022
Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
Fixed-parameter tractability of graph isomorphism in graphs with an excluded minor
54th Annual ACM Symposium on Theory of Computing, STOC 2022
Michał Pilipczuk, Marek Sokołowski, Anna Zych-Pawlewicz
Compact representation for matrices of bounded twin-width
39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022
2021
Wojciech Nadara, Mateusz Radecki, Marcin Smulewicz, Marek Sokołowski
Determining 4-edge-connected components in linear time
29th Annual European Symposium on Algorithms, ESA 2021