Marcin Pilipczuk

Orcid: 0000-0001-5680-7397

Affiliations:
  • University of Warsaw, Faculty of Mathematics, Informatics and Mechanics, Poland


According to our database1, Marcin Pilipczuk authored at least 172 papers between 2008 and 2024.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Flow-augmentation II: Undirected Graphs.
ACM Trans. Algorithms, April, 2024

Tight Bound on Treedepth in Terms of Pathwidth and Longest Path.
Comb., April, 2024

On Weighted Graph Separation Problems and Flow Augmentation.
SIAM J. Discret. Math., March, 2024

Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs.
SIAM J. Comput., February, 2024

Cluster Editing Parameterized above Modification-disjoint <i>P</i><sub>3</sub>-packings.
ACM Trans. Algorithms, January, 2024

Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument.
ACM Trans. Comput. Theory, 2024

Induced Subgraphs of Bounded Treewidth and the Container Method.
SIAM J. Comput., 2024

Embedding Planar Graphs into Graphs of Treewidth O(log<sup>3</sup> n).
CoRR, 2024

Bounding ϵ-scatter dimension via metric sparsity.
CoRR, 2024

Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Combinatorial Correlation Clustering.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Max Weight Independent Set in Sparse Graphs with No Long Claws.
Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof.
Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

Simple and tight complexity lower bounds for solving Rabin games.
Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

Sparse induced subgraphs in <i>P</i><sub>6</sub>-free graphs.
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Parameterized Complexity of MinCSP over the Point Algebra.
Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

2023
The Complexity of Routing Problems in Forbidden-Transition Graphs and Edge-Colored Graphs.
Algorithmica, May, 2023

A polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number.
CoRR, 2023

Directed Symmetric Multicut is W[1]-hard.
CoRR, 2023

Sparse induced subgraphs in P_6-free graphs.
CoRR, 2023

Proving a Directed Analogue of the Gyárfás-Sumner Conjecture for Orientations of $P_4$.
Electron. J. Comb., 2023

A tight quasi-polynomial bound for Global Label Min-Cut.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

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 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Parameterized Complexity Classification for Interval Constraints.
Proceedings of the 18th International Symposium on Parameterized and Exact Computation, 2023

Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

The Influence of Dimensions on the Complexity of Computing Decision Trees.
Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence, 2023

2022
Packing Directed Cycles Quarter- and Half-Integrally.
Comb., December, 2022

Polynomial-time Algorithm for Maximum Weight Independent Set on <i>P</i><sub>6</sub>-free Graphs.
ACM Trans. Algorithms, 2022

Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time.
ACM Trans. Algorithms, 2022

Constant Congestion Brambles in Directed Graphs.
SIAM J. Discret. Math., 2022

A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs.
SIAM J. Comput., 2022

Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering.
SIAM J. Comput., 2022

Constant Congestion Brambles.
Discret. Math. Theor. Comput. Sci., 2022

Highly unbreakable graph with a fixed excluded minor are almost rigid.
CoRR, 2022

Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of P<sub>4</sub>.
CoRR, 2022

On weighted graph separation problems and flow-augmentation.
CoRR, 2022

Hardness of Metric Dimension in Graphs of Constant Treewidth.
Algorithmica, 2022

Preface to the Special Issue on Parameterized and Exact Computation.
Algorithmica, 2022

Bounding Twin-Width for Bounded-Treewidth Graphs, Planar Graphs, and Bipartite Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2022

Fixed-parameter tractability of graph isomorphism in graphs with an excluded minor.
Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Directed flow-augmentation.
Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

On the Complexity of Problems on Tree-Structured Graphs.
Proceedings of the 17th International Symposium on Parameterized and Exact Computation, 2022

Taming Graphs with No Large Creatures and Skinny Ladders.
Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021
Randomized Contractions Meet Lean Decompositions.
ACM Trans. Algorithms, 2021

A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs.
SIAM J. Discret. Math., 2021

Improved Bounds for the Excluded-Minor Approximation of Treedepth.
SIAM J. Discret. Math., 2021

(Theta, triangle)-free and (even hole, K<sub>4</sub>)-free graphs. Part 2: Bounds on treewidth.
J. Graph Theory, 2021

Covering Minimal Separators and Potential Maximal Cliques in $P_t$-Free Graphs.
Electron. J. Comb., 2021

Jones' Conjecture in Subcubic Graphs.
Electron. J. Comb., 2021

Polynomial Treedepth Bounds in Linear Colorings.
Algorithmica, 2021

Finding large induced sparse subgraphs in <i>c<sub>>t</sub></i> -free graphs in quasipolynomial time.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Cluster Editing Parameterized Above Modification-Disjoint P₃-Packings.
Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

Quasi-polynomial-time algorithm for Independent Set in <i>P<sub>t</sub></i>-free graphs via shrinking the space of induced paths.
Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

Optimal Discretization is Fixed-parameter Tractable.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Solving hard cut problems via flow-augmentation.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Efficient fully dynamic elimination forests with applications to detecting long paths and cycles.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Close Relatives (Of Feedback Vertex Set), Revisited.
Proceedings of the 16th International Symposium on Parameterized and Exact Computation, 2021

2020
Introduction to the Special Issue on SODA'18.
ACM Trans. Algorithms, 2020

On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five.
SIAM J. Discret. Math., 2020

An Improved FPT Algorithm for Independent Feedback Vertex Set.
Theory Comput. Syst., 2020

A Double Exponential Lower Bound for the Distinct Vectors Problem.
Discret. Math. Theor. Comput. Sci., 2020

Two lower bounds for $p$-centered colorings.
Discret. Math. Theor. Comput. Sci., 2020

Quasi-polynomial-time algorithm for Independent Set in P<sub>t</sub>-free and C<sub>>t</sub>-free graphs via shrinking the space of connecting subgraphs.
CoRR, 2020

On Dynamic Parameterized k-Path.
CoRR, 2020

Covering minimal separators and potential maximal cliques in P<sub>t</sub>-free graphs.
CoRR, 2020

Multi-budgeted Directed Cuts.
Algorithmica, 2020

Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in <i>H</i>-free graphs.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth.
Proceedings of the 15th International Symposium on Parameterized and Exact Computation, 2020

The Complexity of Connectivity Problems in Forbidden-Transition Graphs And Edge-Colored Graphs.
Proceedings of the 31st International Symposium on Algorithms and Computation, 2020

Surprising Applications of Treewidth Bounds for Planar Graphs.
Proceedings of the Treewidth, Kernels, and Algorithms, 2020

2019
Minimum Bisection Is Fixed-Parameter Tractable.
SIAM J. Comput., 2019

Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation.
ACM J. Exp. Algorithmics, 2019

Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness.
ACM J. Exp. Algorithmics, 2019

Caterpillars in Erdős-Hajnal.
J. Comb. Theory B, 2019

Jones' Conjecture in subcubic graphs.
CoRR, 2019

Cluster Editing parameterized above the size of a modification-disjoint P<sub>3</sub> packing is para-NP-hard.
CoRR, 2019

Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs.
CoRR, 2019

Edge Bipartization Faster than $$2^k$$ 2 k.
Algorithmica, 2019

Deleting Vertices to Graphs of Bounded Genus.
Algorithmica, 2019

An Exponential Lower Bound for Cut Sparsifiers in Planar Graphs.
Algorithmica, 2019

Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor.
Algorithmica, 2019

Subexponential-Time Algorithms for Maximum Independent Set in $$P_t$$ P t -Free and Broom-Free Graphs.
Algorithmica, 2019

Polynomial-time algorithm for Maximum Weight Independent Set on P6-free graphs.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Packing Directed Circuits Quarter-Integrally.
Proceedings of the 27th Annual European Symposium on Algorithms, 2019

Efficient Approximation Schemes for Uniform-Cost Clustering Problems in Planar Graphs.
Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018
Directed Multicut is W[1]-hard, Even for Four Terminal Pairs.
ACM Trans. Comput. Theory, 2018

Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs.
ACM Trans. Algorithms, 2018

Independence and Efficient Domination on <i>P</i><sub>6</sub>-free Graphs.
ACM Trans. Algorithms, 2018

Subexponential Parameterized Algorithm for Interval Completion.
ACM Trans. Algorithms, 2018

Approximation and Kernelization for Chordal Vertex Deletion.
SIAM J. Discret. Math., 2018

Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs.
SIAM J. Discret. Math., 2018

Experimental Evaluation of Parameterized Algorithms for Graph Separation Problems: Half-Integral Relaxations and Matroid-based Kernelization.
CoRR, 2018

Randomized contractions meet lean decompositions.
CoRR, 2018

Subexponential-time Algorithms for Maximum Independent Set in P<sub>t</sub>-free and Broom-free Graphs.
CoRR, 2018

Excluding Hooks and their Complements.
Electron. J. Comb., 2018

Experimental Evaluation of Parameterized Algorithms for Feedback Vertex Set.
Proceedings of the 17th International Symposium on Experimental Algorithms, 2018

On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Planar Digraphs.
Proceedings of the Classes of Directed Graphs., 2018

2017
Hardness of Approximation for Strip Packing.
ACM Trans. Comput. Theory, 2017

Editorial.
ACM Trans. Algorithms, 2017

Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth.
SIAM J. Comput., 2017

Polynomial Kernelization for Removing Induced Claws and Diamonds.
Theory Comput. Syst., 2017

Hitting forbidden subgraphs in graphs of bounded treewidth.
Inf. Comput., 2017

A tight lower bound for Vertex Planarization on graphs of bounded treewidth.
Discret. Appl. Math., 2017

The Erdős-Hajnal conjecture for caterpillars and their complements.
CoRR, 2017

Polynomial-time algorithm for Maximum Weight Independent Set on $P_6$-free graphs.
CoRR, 2017

Turing Kernelization for Finding Long Paths in Graphs Excluding a Topological Minor.
Proceedings of the 12th International Symposium on Parameterized and Exact Computation, 2017

Subexponential Parameterized Algorithms for Graphs of Polynomial Growth.
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016
Planar Directed k-Vertex-Disjoint Paths Problem.
Encyclopedia of Algorithms, 2016

Exact Algorithms on Graphs of Bounded Average Degree.
Encyclopedia of Algorithms, 2016

Known Algorithms for Edge Clique Cover are Probably Optimal.
SIAM J. Comput., 2016

Designing FPT Algorithms for Cut Problems Using Randomized Contractions.
SIAM J. Comput., 2016

A Fast Branching Algorithm for Cluster Vertex Deletion.
Theory Comput. Syst., 2016

On Group Feedback Vertex Set Parameterized by the Size of the Cutset.
Algorithmica, 2016

On Routing Disjoint Paths in Bounded Treewidth Graphs.
Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

Lower Bounds for Approximation Schemes for Closest String.
Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

Kernelization and Sparseness: the Case of Dominating Set.
Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Directed multicut is <i>W</i>[1]-hard, even for four terminal pairs.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Edge Bipartization Faster Than 2^k.
Proceedings of the 11th International Symposium on Parameterized and Exact Computation, 2016

2015
Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs.
SIAM J. Discret. Math., 2015

A Subexponential Parameterized Algorithm for Proper Interval Completion.
SIAM J. Discret. Math., 2015

Sitting Closer to Friends than Enemies, Revisited.
Theory Comput. Syst., 2015

Faster exponential-time algorithms in graphs of bounded average degree.
Inf. Comput., 2015

Edge Bipartization faster than 2<sup>k</sup>.
CoRR, 2015

Independence and Efficient Domination on P<sub>6</sub>-free Graph.
CoRR, 2015

The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015


2014
Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs.
ACM Trans. Comput. Theory, 2014

Clique Cover and Graph Separation: New Incompressibility Results.
ACM Trans. Comput. Theory, 2014

On the Hardness of Losing Width.
Theory Comput. Syst., 2014

Tight bounds for parameterized complexity of Cluster Editing with a small number of clusters.
J. Comput. Syst. Sci., 2014

Faster deterministic Feedback Vertex Set.
Inf. Process. Lett., 2014

Kernelization and Sparseness: the case of Dominating Set.
CoRR, 2014

Solving the 2-Disjoint Connected Subgraphs Problem Faster than 2 n.
Algorithmica, 2014

Scheduling Partially Ordered Jobs Faster than 2 n.
Algorithmica, 2014

Parameterized Complexity of Eulerian Deletion Problems.
Algorithmica, 2014

On Cutwidth Parameterized by Vertex Cover.
Algorithmica, 2014

2013
On multiway cut parameterized above lower bounds.
ACM Trans. Comput. Theory, 2013

Subset Feedback Vertex Set Is Fixed-Parameter Tractable.
SIAM J. Discret. Math., 2013

Split Vertex Deletion meets Vertex Cover: New fixed-parameter and exact exponential-time algorithms.
Inf. Process. Lett., 2013

A bound on the number of perfect matchings in Klee-graphs.
Discret. Math. Theor. Comput. Sci., 2013

Towards optimal kernel for connected vertex cover in planar graphs.
Discret. Appl. Math., 2013

Dynamic Steiner Tree in Planar Graphs.
CoRR, 2013

Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs.
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Tight bounds for Parameterized Complexity of Cluster Editing.
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

The Planar Directed K-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012
Even Faster Exact Bandwidth.
ACM Trans. Algorithms, 2012

A Polynomial Algorithm for 3-Compatible Coloring and the Stubborn List Partition Problem (The Stubborn Problem Is Stubborn No More).
SIAM J. Comput., 2012

Some results on Vizing's conjecture and related problems.
Discret. Appl. Math., 2012

Kernelization hardness of connectivity problems in d-degenerate graphs.
Discret. Appl. Math., 2012

Bandwidth and distortion revisited.
Discret. Appl. Math., 2012

On fixed-parameter algorithms for Split Vertex Deletion
CoRR, 2012

An Improved FPT Algorithm and a Quadratic Kernel for Pathwidth One Vertex Deletion.
Algorithmica, 2012

Finding a Maximum Induced Degenerate Subgraph Faster Than 2 n.
Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012

A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees.
Proceedings of the Algorithms - ESA 2012, 2012

2011
Dominating set is fixed parameter tractable in claw-free graphs.
Theor. Comput. Sci., 2011

Breaking the 2<sup>n</sup>-barrier for Irredundance: Two lines of attack.
J. Discrete Algorithms, 2011

Capacitated domination faster than <i>O</i>(<i>n</i><sup>2</sup>).
Inf. Process. Lett., 2011

On the Zagreb index inequality of graphs with prescribed vertex degrees.
Discret. Appl. Math., 2011

Subexponential fixed-parameter tractability of cluster editing
CoRR, 2011

The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem).
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Approximation Algorithms for Union and Intersection Covering Problems.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

2010
Exact and approximate bandwidth.
Theor. Comput. Sci., 2010

Kernelization Hardness of Connectivity Problems in <i>d</i>-Degenerate Graphs.
Proceedings of the Graph Theoretic Concepts in Computer Science, 2010

Capacitated Domination Faster Than <i>O</i>(2<sup><i>n</i></sup>).
Proceedings of the Algorithm Theory, 2010

Fast Approximation in Subspaces by Doubling Metric Decomposition.
Proceedings of the Algorithms, 2010

Irredundant Set Faster Than <i>O</i>(2<sup><i>n</i></sup>).
Proceedings of the Algorithms and Complexity, 7th International Conference, 2010

2009
Beyond O*(2^n) in domination-type problems
CoRR, 2009

2008
Exponential-Time Approximation of Hard Problems
CoRR, 2008

Faster Exact Bandwidth.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2008


  Loading...