Publications

Journal: ACM Transactions on Computation Theory

Number of publications: 15

2025

• Konrad Majewski , Michał Pilipczuk , Marek Sokołowski, Maintaining CMSO₂ properties on dynamic structures with bounded feedback vertex number, ACM Transactions on Computation Theory, 17 (2) 2025, p. 1-72. See in PBN
• 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, ACM Transactions on Computation Theory, 2025. See in PBN

2024

• Karolina Okrasa, Paweł Rzążewski , Konrad Majewski, Tomáš Masařík, Jana Masaříková, Marek Sokołowski, Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás′ path argument, ACM Transactions on Computation Theory, 16 (2) 2024, p. 1-18. See in PBN
• Bart M. P. Jansen, Michał Włodarczyk , Optimal Polynomial-Time Compression for Boolean Max CSP, ACM Transactions on Computation Theory, 16 (1) 2024, p. 1-20. See in PBN

2023

• Karolina Okrasa, Paweł Rzążewski , Hubie Chen, Bart M. P. Jansen, Astrid Pieterse, Sparsification Lower Bounds for List H-Coloring, ACM Transactions on Computation Theory, 15 (3-4) 2023, p. 1-23. See in PBN

2021

• Alex Brandts, Marcin Wrochna , Stanislav Živný, The Complexity of Promise SAT on Non-Boolean Domains, ACM Transactions on Computation Theory, 13 (4) 2021, p. 1-20. See in PBN

2020

• Dusan Knop, Michał Pilipczuk , Marcin Wrochna , Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints, ACM Transactions on Computation Theory, 12 (3) 2020, p. 19:1--19:19. See in PBN

2019

• Marthe Bonamy, Łukasz Kowalik , Michał Pilipczuk , Arkadiusz Socała, Marcin Wrochna , Tight Lower Bounds for the Complexity of Multicoloring, ACM Transactions on Computation Theory, 11 (3) 2019, p. 1-19. See in PBN

2018

• Marcin Pilipczuk , Magnus Wahlström, Directed Multicut is W[1]-hard, Even for Four Terminal Pairs, ACM Transactions on Computation Theory, 10 (3) 2018, p. 1–18. See in PBN
• Ivan Bliznets, Marek Cygan , Paweł Komosa, Michał Pilipczuk , Hardness of Approximation for H-free Edge Modification Problems, ACM Transactions on Computation Theory, 10 (2) 2018, p. 2018. See in PBN
• Michał Pilipczuk , Marcin Wrochna , On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs, ACM Transactions on Computation Theory, 9 (4) 2018, p. 18: 1–36. See in PBN

2017

• Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk , Michał Pilipczuk , Hardness of Approximation for Strip Packing, ACM Transactions on Computation Theory, 9 (3) 2017, p. 14:1-7. See in PBN

2015

• Pål Grønås Drange, Fedor V. Fomin, Michał Pilipczuk , Yngve Villanger, Exploring the Subexponential Complexity of Completion Problems, ACM Transactions on Computation Theory, 2015. See in PBN

2014

• Marek Cygan , Stefan Kratsch, Marcin Pilipczuk , Michał Pilipczuk , Magnus Wahlström, Clique Cover and Graph Separation: New Incompressibility Results, ACM Transactions on Computation Theory, 2014. See in PBN

2013

• Marek Cygan , Marcin Pilipczuk , Michał Pilipczuk , Jakub Wojtaszczyk, On multiway cut parameterized above lower bounds, ACM Transactions on Computation Theory, 2013. See in PBN