Michal Pilipczuk

According to our database1, Michal Pilipczuk authored at least 143 papers between 2010 and 2020.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2020
Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints.
ACM Trans. Comput. Theory, 2020

First-Order Interpretations of Bounded Expansion Classes.
ACM Trans. Comput. Log., 2020

Model-Checking on Ordered Structures.
ACM Trans. Comput. Log., 2020

Enumerating Minimal Dominating Sets in Kt-free Graphs and Variants.
ACM Trans. Algorithms, 2020

Lower Bounds for the Parameterized Complexity of Minimum Fill-in and Other Completion Problems.
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

On low rank-width colorings.
Eur. J. Comb., 2020

Efficient sequential and parallel algorithms for multistage stochastic integer programming using proximity.
CoRR, 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

Rankwidth meets stability.
CoRR, 2020

On Dynamic Parameterized k-Path.
CoRR, 2020

VC density of set systems defnable in tree-like graphs.
CoRR, 2020

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

The monitoring problem for timed automata.
CoRR, 2020

On the effect of symmetry requirement for rendezvous on the complete graph.
CoRR, 2020

Clustering Powers of Sparse Graphs.
Electron. J. Comb., 2020

Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs.
Algorithmica, 2020

Special Issue Dedicated to the 13th International Symposium on Parameterized and Exact Computation.
Algorithmica, 2020

Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2020

An exponential time parameterized algorithm for planar disjoint paths.
Proceedings of the Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 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

Shorter Labeling Schemes for Planar Graphs.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

VC Density of Set Systems Definable in Tree-Like Graphs.
Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

On Polynomial Recursive Sequences.
Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Finding Large H-Colorable Subgraphs in Hereditary Graph Classes.
Proceedings of the 28th Annual European Symposium on Algorithms, 2020

Computing Tree Decompositions.
Proceedings of the Treewidth, Kernels, and Algorithms, 2020

2019
Tight Lower Bounds for the Complexity of Multicoloring.
ACM Trans. Comput. Theory, 2019

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

Shortest paths in one-counter systems.
Log. Methods Comput. Sci., 2019

Strong immersion is a well-quasi-ordering for semicomplete digraphs.
J. Graph Theory, 2019

On width measures and topological problems on semi-complete digraphs.
J. Comb. Theory, Ser. B, 2019

Jones' Conjecture in subcubic graphs.
CoRR, 2019

Graphs of bounded cliquewidth are polynomially χ-bounded.
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

Cutwidth: Obstructions and Algorithmic Aspects.
Algorithmica, 2019

Progressive Algorithms for Domination and Independence.
Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

Polynomial bounds for centered colorings on proper minor-closed graph classes.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs.
Proceedings of the 14th International Symposium on Parameterized and Exact Computation, 2019

Integer Programming and Incidence Treedepth.
Proceedings of the Integer Programming and Combinatorial Optimization, 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

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

On Geometric Set Cover for Orthants.
Proceedings of the 27th Annual European Symposium on Algorithms, 2019

Reachability for Bounded Branching VASS.
Proceedings of the 30th International Conference on Concurrency Theory, 2019

2018
On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs.
ACM Trans. Comput. Theory, 2018

Hardness of Approximation for <i>H</i>-free Edge Modification Problems.
ACM Trans. Comput. Theory, 2018

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

Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth.
ACM Trans. Algorithms, 2018

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

Exploring the Complexity of Layout Parameters in Tournaments and Semicomplete Digraphs.
ACM Trans. Algorithms, 2018

Below All Subsets for Minimal Connected Dominating Set.
SIAM J. Discret. Math., 2018

Randomized contractions meet lean decompositions.
CoRR, 2018

Kernelization and approximation of distance-r independent sets on nowhere dense graphs.
CoRR, 2018

Parameterized circuit complexity of model checking first-order logic on sparse structures.
CoRR, 2018

A Polynomial Kernel for Trivially Perfect Editing.
Algorithmica, 2018

On Directed Feedback Vertex Set Parameterized by Treewidth.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2018

On the number of types in sparse graphs.
Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, 2018

Parameterized circuit complexity of model-checking on sparse structures.
Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, 2018

Definable decompositions for graphs of bounded linear cliquewidth.
Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, 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

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

On Wideness and Stability.
CoRR, 2017

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

Strong immersion is a well-quasi-ordering for semi-complete digraphs.
CoRR, 2017

Linear Kernels for Outbranching Problems in Sparse Digraphs.
Algorithmica, 2017

Optimizing Tree Decompositions in MSO.
Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking.
Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

On Definable and Recognizable Properties of Graphs of Bounded Treewidth (Invited Talk).
Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

Model-checking for successor-invariant first-order formulas on graph classes of bounded expansion.
Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Exploring the Complexity of Layout Parameters in Tournaments and Semi-Complete Digraphs.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016
Lower Bounds Based on the Exponential Time Hypothesis: Edge Clique Cover.
Encyclopedia of Algorithms, 2016

Exact Algorithms for Induced Subgraph Problems.
Encyclopedia of Algorithms, 2016

Computing Cutwidth and Pathwidth of Semi-complete Digraphs.
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 c<sup>k</sup> n 5-Approximation Algorithm for Treewidth.
SIAM J. Comput., 2016

How to hunt an invisible rabbit on a graph.
Eur. J. Comb., 2016

On Ultralimits of Sparse Graph Classes.
Electron. J. Comb., 2016

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

Largest Chordal and Interval Subgraphs Faster than $$2^n$$ 2 n.
Algorithmica, 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

Schema Validation via Streaming Circuits.
Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

The Generalised Colouring Numbers on Classes of Bounded Expansion.
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Definability equals recognizability for graphs of bounded treewidth.
Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 2016

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

Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Hardness of Approximation for H-Free Edge Modification Problems.
Proceedings of the Approximation, 2016

2015
Exploring the Subexponential Complexity of Completion Problems.
ACM Trans. Comput. Theory, 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

Minimizing Rosenthal Potential in Multicast Games.
Theory Comput. Syst., 2015

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

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

Modifying a Graph Using Vertex Elimination.
Algorithmica, 2015

Computing Tree-Depth Faster Than 2<sup>n</sup>.
Algorithmica, 2015

Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams.
Proceedings of the Algorithms - ESA 2015, 2015

Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints.
Proceedings of the Algorithms - ESA 2015, 2015


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

Preprocessing subgraph and minor problems: When does a small vertex cover help?
J. Comput. Syst. Sci., 2014

Representative sets for multisets.
CoRR, 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

Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask).
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

Exploring Subexponential Parameterized Complexity of Completion Problems.
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

Synthesizing transformations from XML schema mappings.
Proceedings of the Proc. 17th International Conference on Database Theory (ICDT), 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

A O(c^k n) 5-Approximation Algorithm for Treewidth
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

Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings.
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

Jungles, bundles, and fixed parameter tractability.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Computing Tree-Depth Faster Than 2 n.
Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 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

An O(c^k n) 5-Approximation Algorithm for Treewidth.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Subexponential Parameterized Algorithm for Computing the Cutwidth of a Semi-complete Digraph.
Proceedings of the Algorithms - ESA 2013, 2013

Largest Chordal and Interval Subgraphs Faster Than 2 n.
Proceedings of the Algorithms - ESA 2013, 2013

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

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

How to Eliminate a Graph.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2012

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

2011
Dominating set is fixed parameter tractable in claw-free graphs.
Theor. Comput. Sci., 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

Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach.
Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

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


  Loading...