Marcin Pilipczuk

ORCID

Publication Activity (10 Years)

Years Active: 2008-2024
Publications (10 Years): 178

Top Venues

CoRR

Algorithmica

SODA

ACM Trans. Algorithms

Publications

Eun Jung Kim, Tomás Masarík, Marcin Pilipczuk, Roohani Sharma, Magnus Wahlström
On Weighted Graph Separation Problems and Flow Augmentation. SIAM J. Discret. Math. 38 (1) (2024)
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
Flow-augmentation II: Undirected Graphs. ACM Trans. Algorithms 20 (2) (2024)
Karthik C. S., Dániel Marx, Marcin Pilipczuk, Uéverton S. Souza
Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof. SOSA (2024)
Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Pawel Rzazewski, Paul D. Seymour
Induced Subgraphs of Bounded Treewidth and the Container Method. SIAM J. Comput. 53 (3) (2024)
Vincent Cohen-Addad, David Rasmussen Lolck, Marcin Pilipczuk, Mikkel Thorup, Shuyi Yan, Hanwen Zhang
Combinatorial Correlation Clustering. CoRR (2024)
Maria Chudnovsky, Marcin Pilipczuk, Michal Pilipczuk, Stéphan Thomassé
Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in $\boldsymbol{H}$-Free Graphs. SIAM J. Comput. 53 (1) (2024)
Antonio Casares, Marcin Pilipczuk, Michal Pilipczuk, Uéverton S. Souza, K. S. Thejaswini
Simple and tight complexity lower bounds for solving Rabin games. SOSA (2024)
Vincent Cohen-Addad, David Rasmussen Lolck, Marcin Pilipczuk, Mikkel Thorup, Shuyi Yan, Hanwen Zhang
Combinatorial Correlation Clustering. STOC (2024)
Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Pawel Rzazewski
Max Weight Independent Set in Sparse Graphs with No Long Claws. STACS (2024)
Peter Gartland, Daniel Lokshtanov, Tomás Masarík, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski
Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time. STOC (2024)
Maria Chudnovsky, Rose McCarty, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski
-free graphs. SODA (2024)
Shaohua Li, Marcin Pilipczuk, Manuel Sorge
-packings. ACM Trans. Algorithms 20 (1) (2024)
Meike Hatzel, Gwenaël Joret, Piotr Micek, Marcin Pilipczuk, Torsten Ueckerdt, Bartosz Walczak
Tight Bound on Treedepth in Terms of Pathwidth and Longest Path. Comb. 44 (2) (2024)
Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Pawel Rzazewski
Max Weight Independent Set in sparse graphs with no long claws. CoRR (2023)
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints. SODA (2023)
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, Marcin Pilipczuk, Roohani Sharma
Parameterized Complexity Classification for Interval Constraints. IPEC (2023)
George Osipov, Marcin Pilipczuk
Directed Symmetric Multicut is W[1]-hard. CoRR (2023)
Linda Cook, Tomás Masarík, Marcin Pilipczuk, Amadeus Reinald, Uéverton S. Souza
Proving a Directed Analogue of the Gyárfás-Sumner Conjecture for Orientations of $P_4$. Electron. J. Comb. 30 (3) (2023)
Meike Hatzel, Gwenaël Joret, Piotr Micek, Marcin Pilipczuk, Torsten Ueckerdt, Bartosz Walczak
Tight bound on treedepth in terms of pathwidth and longest path. CoRR (2023)
Stephen G. Kobourov, Maarten Löffler, Fabrizio Montecchiani, Marcin Pilipczuk, Ignaz Rutter, Raimund Seidel, Manuel Sorge, Jules Wulms
The Influence of Dimensions on the Complexity of Computing Decision Trees. AAAI (2023)
Meike Hatzel, Lars Jaffke, Paloma T. Lima, Tomás Masarí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. SODA (2023)
Vincent Cohen-Addad, Hung Le, Marcin Pilipczuk, Michal Pilipczuk
Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1. FOCS (2023)
Antonio Casares, Marcin Pilipczuk, Michal Pilipczuk, Uéverton S. Souza, K. S. Thejaswini
Simple and tight complexity lower bounds for solving Rabin games. CoRR (2023)
Marcin Pilipczuk, Pawel Rzazewski
A polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number. CoRR (2023)
Karthik C. S., Dániel Marx, Marcin Pilipczuk, Uéverton S. Souza
Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof. CoRR (2023)
Lars Jaffke, Paloma T. Lima, Tomás Masarík, Marcin Pilipczuk, Uéverton S. Souza
A tight quasi-polynomial bound for Global Label Min-Cut. SODA (2023)
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, Marcin Pilipczuk, Roohani Sharma
Parameterized Complexity Classification for Interval Constraints. CoRR (2023)
Peter Gartland, Daniel Lokshtanov, Tomás Masarík, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski
Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time. CoRR (2023)
Maria Chudnovsky, Rose McCarty, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski
Sparse induced subgraphs in P_6-free graphs. CoRR (2023)
Vincent Cohen-Addad, Hung Le, Marcin Pilipczuk, Michal Pilipczuk
Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1. CoRR (2023)
Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, Manuel Sorge
The Complexity of Routing Problems in Forbidden-Transition Graphs and Edge-Colored Graphs. Algorithmica 85 (5) (2023)
Hugo Jacob, Marcin Pilipczuk
Bounding Twin-Width for Bounded-Treewidth Graphs, Planar Graphs, and Bipartite Graphs. WG (2022)
Andrzej Grzesik, Tereza Klimosová, Marcin Pilipczuk, Michal Pilipczuk
-free Graphs. ACM Trans. Algorithms 18 (1) (2022)
Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering. SIAM J. Comput. 51 (6) (2022)
Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk, Michal Pilipczuk
On the Complexity of Problems on Tree-Structured Graphs. IPEC (2022)
Tomás Masarík, Marcin Pilipczuk, Pawel Rzazewski, Manuel Sorge
Constant Congestion Brambles in Directed Graphs. SIAM J. Discret. Math. 36 (2) (2022)
Jakub Gajarský, Lars Jaffke, Paloma T. Lima, Jana Novotná, Marcin Pilipczuk, Pawel Rzazewski, Uéverton S. Souza
Taming graphs with no large creatures and skinny ladders. CoRR (2022)
Jakub Gajarský, Lars Jaffke, Paloma T. Lima, Jana Novotná, Marcin Pilipczuk, Pawel Rzazewski, Uéverton S. Souza
Taming Graphs with No Large Creatures and Skinny Ladders. ESA (2022)
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints. CoRR (2022)
Meike Hatzel, Pawel Komosa, Marcin Pilipczuk, Manuel Sorge
Constant Congestion Brambles. Discret. Math. Theor. Comput. Sci. 24 (1) (2022)
Tomás Masarík, Irene Muzi, Marcin Pilipczuk, Pawel Rzazewski, Manuel Sorge
Packing Directed Cycles Quarter- and Half-Integrally. Comb. 42 (Supplement 2) (2022)
Meike Hatzel, Lars Jaffke, Paloma T. Lima, Tomás Masarí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. CoRR (2022)
Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, Jakub Onufry Wojtaszczyk
Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time. ACM Trans. Algorithms 18 (2) (2022)
Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
Highly unbreakable graph with a fixed excluded minor are almost rigid. CoRR (2022)
Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
Fixed-parameter tractability of Graph Isomorphism in graphs with an excluded minor. CoRR (2022)
Yixin Cao, Marcin Pilipczuk
Preface to the Special Issue on Parameterized and Exact Computation. Algorithmica 84 (8) (2022)
Stephen G. Kobourov, Maarten Löffler, Fabrizio Montecchiani, Marcin Pilipczuk, Ignaz Rutter, Raimund Seidel, Manuel Sorge, Jules Wulms
The Influence of Dimensions on the Complexity of Computing Decision Trees. CoRR (2022)
Lars Jaffke, Paloma T. Lima, Tomás Masarík, Marcin Pilipczuk, Uéverton S. Souza
A tight quasi-polynomial bound for Global Label Min-Cut. CoRR (2022)
Hugo Jacob, Marcin Pilipczuk
Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs. CoRR (2022)
Konrad Majewski, Tomás Masarík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Pawel Rzazewski, Marek Sokolowski
Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument. ICALP (2022)
Eun Jung Kim, Marcin Pilipczuk, Roohani Sharma, Magnus Wahlström
On weighted graph separation problems and flow-augmentation. CoRR (2022)
Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk, Michal Pilipczuk
On the Complexity of Problems on Tree-structured Graphs. CoRR (2022)
Konrad Majewski, Tomás Masarík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Pawel Rzazewski, Marek Sokolowski
Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument. CoRR (2022)
Linda Cook, Tomás Masarík, Marcin Pilipczuk, Amadeus Reinald, Uéverton S. Souza
. CoRR (2022)
Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk
A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs. SIAM J. Comput. 51 (2) (2022)
Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
Fixed-parameter tractability of graph isomorphism in graphs with an excluded minor. STOC (2022)
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
Directed flow-augmentation. STOC (2022)
Shaohua Li, Marcin Pilipczuk
Hardness of Metric Dimension in Graphs of Constant Treewidth. Algorithmica 84 (11) (2022)
Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski
-free graphs in quasipolynomial time. STOC (2021)
Hugo Jacob, Thomas Bellitto, Oscar Defrain, Marcin Pilipczuk
Close relatives (of Feedback Vertex Set), revisited. CoRR (2021)
Shaohua Li, Marcin Pilipczuk
Hardness of Metric Dimension in Graphs of Constant Treewidth. IPEC (2021)
Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski
-free graphs via shrinking the space of induced paths. SOSA (2021)
Wojciech Czerwinski, Wojciech Nadara, Marcin Pilipczuk
Improved Bounds for the Excluded-Minor Approximation of Treedepth. SIAM J. Discret. Math. 35 (2) (2021)
Marthe Bonamy, François Dross, Tomás Masarík, Andrea Munaro, Wojciech Nadara, Marcin Pilipczuk, Michal Pilipczuk
Jones' Conjecture in Subcubic Graphs. Electron. J. Comb. 28 (4) (2021)
Andrzej Grzesik, Tereza Klimosová, Marcin Pilipczuk, Michal Pilipczuk
Covering Minimal Separators and Potential Maximal Cliques in $P_t$-Free Graphs. Electron. J. Comb. 28 (1) (2021)
Shaohua Li, Marcin Pilipczuk, Manuel Sorge
Cluster Editing Parameterized Above Modification-Disjoint P₃-Packings. STACS (2021)
Bart M. P. Jansen, Marcin Pilipczuk, Erik Jan van Leeuwen
A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs. SIAM J. Discret. Math. 35 (4) (2021)
Hugo Jacob, Thomas Bellitto, Oscar Defrain, Marcin Pilipczuk
Close Relatives (Of Feedback Vertex Set), Revisited. IPEC (2021)
Tomás Masarík, Marcin Pilipczuk, Pawel Rzazewski, Manuel Sorge
Constant congestion brambles in directed graphs. CoRR (2021)
Marek Cygan, Pawel Komosa, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh, Magnus Wahlström
Randomized Contractions Meet Lean Decompositions. ACM Trans. Algorithms 17 (1) (2021)
Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Pawel Rzazewski, Paul D. Seymour
Induced subgraphs of bounded treewidth and the container method. SODA (2021)
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
Directed flow-augmentation. CoRR (2021)
Jeremy Kun, Michael P. O'Brien, Marcin Pilipczuk, Blair D. Sullivan
Polynomial Treedepth Bounds in Linear Colorings. Algorithmica 83 (1) (2021)
Shaohua Li, Marcin Pilipczuk
Hardness of Metric Dimension in Graphs of Constant Treewidth. CoRR (2021)
Marcin Pilipczuk, Ni Luh Dewi Sintiari, Stéphan Thomassé, Nicolas Trotignon
)-free graphs. Part 2: Bounds on treewidth. J. Graph Theory 97 (4) (2021)
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
Solving hard cut problems via flow-augmentation. SODA (2021)
Stefan Kratsch, Tomás Masarík, Irene Muzi, Marcin Pilipczuk, Manuel Sorge
Optimal Discretization is Fixed-parameter Tractable. SODA (2021)
Jiehua Chen, Wojciech Czerwinski, Yann Disser, Andreas Emil Feldmann, Danny Hermelin, Wojciech Nadara, Marcin Pilipczuk, Michal Pilipczuk, Manuel Sorge, Bartlomiej Wróblewski, Anna Zych-Pawlewicz
Efficient fully dynamic elimination forests with applications to detecting long paths and cycles. SODA (2021)
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
Solving hard cut problems via flow-augmentation. CoRR (2020)
Loïc Dubois, Gwenaël Joret, Guillem Perarnau, Marcin Pilipczuk, François Pitois
Two lower bounds for $p$-centered colorings. Discret. Math. Theor. Comput. Sci. 22 (4) (2020)
Marcin Pilipczuk, Manuel Sorge
A Double Exponential Lower Bound for the Distinct Vectors Problem. Discret. Math. Theor. Comput. Sci. 22 (4) (2020)
Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, Manuel Sorge
The Complexity of Connectivity Problems in Forbidden-Transition Graphs And Edge-Colored Graphs. ISAAC (2020)
Stefan Kratsch, Tomás Masarík, Irene Muzi, Marcin Pilipczuk, Manuel Sorge
Optimal Discretization is Fixed-parameter Tractable. CoRR (2020)
Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, Manuel Sorge
The Complexity of Connectivity Problems in Forbidden-Transition Graphs and Edge-Colored Graphs. CoRR (2020)
Loïc Dubois, Gwenaël Joret, Guillem Perarnau, Marcin Pilipczuk, François Pitois
Two lower bounds for $p$-centered colorings. CoRR (2020)
Maria Chudnovsky, Marcin Pilipczuk, Michal Pilipczuk, Stéphan Thomassé
On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five. SIAM J. Discret. Math. 34 (2) (2020)
Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Pawel Rzazewski, Paul D. Seymour
Induced subgraphs of bounded treewidth and the container method. CoRR (2020)
Marcin Pilipczuk, Manuel Sorge
A Double Exponential Lower Bound for the Distinct Vectors Problem. CoRR (2020)
Yin Tat Lee, Marcin Pilipczuk, David P. Woodruff
Introduction to the Special Issue on SODA'18. ACM Trans. Algorithms 16 (1) (2020)
Jiehua Chen, Wojciech Czerwinski, Yann Disser, Andreas Emil Feldmann, Danny Hermelin, Wojciech Nadara, Michal Pilipczuk, Marcin Pilipczuk, Manuel Sorge, Bartlomiej Wróblewski, Anna Zych-Pawlewicz
On Dynamic Parameterized k-Path. CoRR (2020)
Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski
-free graphs via shrinking the space of connecting subgraphs. CoRR (2020)
Lukasz Kowalik, Marcin Mucha, Wojciech Nadara, Marcin Pilipczuk, Manuel Sorge, Piotr Wygocki
The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth. IPEC (2020)
Meike Hatzel, Pawel Komosa, Marcin Pilipczuk, Manuel Sorge
Constant Congestion Brambles. CoRR (2020)
Marcin Pilipczuk, Ni Luh Dewi Sintiari, Stéphan Thomassé, Nicolas Trotignon
)-free graphs. Part 2 : bounds on treewidth. CoRR (2020)
Maria Chudnovsky, Marcin Pilipczuk, Michal Pilipczuk, Stéphan Thomassé
-free graphs. SODA (2020)
Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, Magnus Wahlström
Multi-budgeted Directed Cuts. Algorithmica 82 (8) (2020)
Marcin Pilipczuk
Surprising Applications of Treewidth Bounds for Planar Graphs. Treewidth, Kernels, and Algorithms (2020)
Andrzej Grzesik, Tereza Klimosová, Marcin Pilipczuk, Michal Pilipczuk
-free graphs. CoRR (2020)
Shaohua Li, Marcin Pilipczuk
An Improved FPT Algorithm for Independent Feedback Vertex Set. Theory Comput. Syst. 64 (8) (2020)
Gábor Bacsó, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Zsolt Tuza, Erik Jan van Leeuwen
Subexponential-Time Algorithms for Maximum Independent Set in $$P_t$$ P t -Free and Broom-Free Graphs. Algorithmica 81 (2) (2019)

Marcin Pilipczuk.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Marcin Pilipczuk