Michał Pilipczuk

research

∙ 08/23/2023

Cliquewidth and dimension

We prove that every poset with bounded cliquewidth and with sufficiently...

0 Gwenaël Joret, et al. ∙

research

∙ 07/20/2023

A parameterized approximation scheme for the 2D-Knapsack problem with wide items

We study a natural geometric variant of the classic Knapsack problem cal...

0 Michał Pilipczuk, et al. ∙

research

∙ 07/14/2023

Sparse induced subgraphs in P_6-free graphs

We prove that a number of computational problems that ask for the larges...

0 Maria Chudnovsky, et al. ∙

research

∙ 07/03/2023

Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth

Dynamic programming on various graph decompositions is one of the most f...

0 Benjamin Bergougnoux, et al. ∙

research

∙ 07/01/2023

Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard

Let d be a positive integer. For a finite set X ⊆ℝ^d, we define its inte...

0 Łukasz Kowalik, et al. ∙

research

∙ 05/25/2023

Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time

We show that the Maximum Weight Independent Set problem (MWIS) can be so...

0 Peter Gartland, et al. ∙

research

∙ 04/14/2023

Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1

We prove that there is a randomized polynomial-time algorithm that given...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 04/04/2023

Dynamic treewidth

We present a data structure that for a dynamic graph G that is updated b...

0 Tuukka Korhonen, et al. ∙

research

∙ 02/26/2023

Partitioning edges of a planar graph into linear forests and a matching

We show that the edges of any planar graph of maximum degree at most 9 c...

0 Marthe Bonamy, et al. ∙

research

∙ 01/31/2023

Flipper games for monadically stable graph classes

A class of graphs 𝒞 is monadically stable if for any unary expansion 𝒞 o...

0 Jakub Gajarsky, et al. ∙

research

∙ 01/06/2023

Simpler and faster algorithms for detours in planar digraphs

In the directed detour problem one is given a digraph G and a pair of ve...

0 Meike Hatzel, et al. ∙

research

∙ 12/03/2022

Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments

In the Maximum Weight Independent Set of Rectangles problem (MWISR) we a...

0 Jana Cslovjecsek, et al. ∙

research

∙ 11/28/2022

On digraphs without onion star immersions

The t-onion star is the digraph obtained from a star with 2t leaves by r...

0 Łukasz Bożyk, et al. ∙

research

∙ 10/26/2022

Fixed-parameter tractability of Graph Isomorphism in graphs with an excluded minor

We prove that Graph Isomorphism and Canonization in graphs excluding a f...

0 Daniel Lokshtanov, et al. ∙

research

∙ 10/26/2022

Highly unbreakable graph with a fixed excluded minor are almost rigid

A set X ⊆ V(G) in a graph G is (q,k)-unbreakable if every separation (A,...

0 Daniel Lokshtanov, et al. ∙

research

∙ 08/16/2022

Polynomial kernel for immersion hitting in tournaments

For a fixed simple digraph H without isolated vertices, we consider the ...

0 Łukasz Bożyk, et al. ∙

research

∙ 06/23/2022

On the Complexity of Problems on Tree-structured Graphs

In this paper, we introduce a new class of parameterized problems, which...

0 Hans L. Bodlaender, et al. ∙

research

∙ 06/16/2022

Twin-width and types

We study problems connected to first-order logic in graphs of bounded tw...

0 Jakub Gajarsky, et al. ∙

research

∙ 05/30/2022

Independence number of intersection graphs of axis-parallel segments

We prove that for any triangle-free intersection graph of n axis-paralle...

0 Marco Caoduro, et al. ∙

research

∙ 05/05/2022

Computing treedepth in polynomial space and linear fpt time

The treedepth of a graph G is the least possible depth of an elimination...

0 Wojciech Nadara, et al. ∙

research

∙ 05/01/2022

Dynamic data structures for parameterized string problems

We revisit classic string problems considered in the area of parameteriz...

0 Jedrzej Olkowski, et al. ∙

research

∙ 03/31/2022

Transducing paths in graph classes with unbounded shrubdepth

Transductions are a general formalism for expressing transformations of ...

0 Michał Pilipczuk, et al. ∙

research

∙ 02/15/2022

Graphs of bounded twin-width are quasi-polynomially χ-bounded

We prove that for every t∈ℕ there is a constant γ_t such that every grap...

0 Michał Pilipczuk, et al. ∙

research

∙ 01/26/2022

Treelike decompositions for transductions of sparse graphs

We give new decomposition theorems for classes of graphs that can be tra...

0 Jan Dreier, et al. ∙

research

∙ 01/23/2022

Bounding generalized coloring numbers of planar graphs using coin models

We study Koebe orderings of planar graphs: vertex orderings obtained by ...

0 Jesper Nederlof, et al. ∙

research

∙ 11/05/2021

Algorithms and data structures for first-order logic with connectivity under vertex failures

We introduce a new data structure for answering connectivity queries in ...

0 Michał Pilipczuk, et al. ∙

research

∙ 10/15/2021

Compact representation for matrices of bounded twin-width

For every fixed d ∈ℕ, we design a data structure that represents a binar...

0 Michał Pilipczuk, et al. ∙

research

∙ 07/13/2021

Maintaining 𝖢𝖬𝖲𝖮_2 properties on dynamic structures with bounded feedback vertex number

Let φ be a sentence of 𝖢𝖬𝖲𝖮_2 (monadic second-order logic with quantific...

0 Konrad Majewski, et al. ∙

research

∙ 07/08/2021

Stable graphs of bounded twin-width

We prove that every class of graphs 𝒞 that is monadically stable and has...

0 Jakub Gajarsky, et al. ∙

research

∙ 05/04/2021

Isolation schemes for problems on decomposable graphs

The Isolation Lemma of Mulmuley, Vazirani and Vazirani [Combinatorica'87...

0 Jesper Nederlof, et al. ∙

research

∙ 03/31/2021

An Exponential Time Parameterized Algorithm for Planar Disjoint Paths

In the Disjoint Paths problem, the input is an undirected graph G on n v...

0 Daniel Lokshtanov, et al. ∙

research

∙ 03/26/2021

On objects dual to tree-cut decompositions

Tree-cut width is a graph parameter introduced by Wollan that is an anal...

0 Łukasz Bożyk, et al. ∙

research

∙ 12/21/2020

Efficient sequential and parallel algorithms for multistage stochastic integer programming using proximity

We consider the problem of solving integer programs of the form min{ c^⊺...

0 Jana Cslovjecsek, et al. ∙

research

∙ 11/30/2020

Integer Programming and Incidence Treedepth

Recently a strong connection has been shown between the tractability of ...

0 Eduard Eiben, et al. ∙

research

∙ 09/28/2020

Quasi-polynomial-time algorithm for Independent Set in P_t-free graphs via shrinking the space of induced paths

In a recent breakthrough work, Gartland and Lokshtanov [FOCS 2020] showe...

0 Marcin Pilipczuk, et al. ∙

research

∙ 07/15/2020

Rankwidth meets stability

We study two notions of being well-structured for classes of graphs that...

0 Jaroslav Nešetřil, et al. ∙

research

∙ 05/31/2020

Efficient fully dynamic elimination forests with applications to detecting long paths and cycles

We present a data structure that in a dynamic graph of treedepth at most...

0 Jiehua Chen, et al. ∙

research

∙ 04/20/2020

Finding large H-colorable subgraphs in hereditary graph classes

We study the Max Partial H-Coloring problem: given a graph G, find the l...

0 Maria Chudnovsky, et al. ∙

research

∙ 03/31/2020

VC density of set systems defnable in tree-like graphs

We study set systems definable in graphs using variants of logic with di...

0 Adam Paszke, et al. ∙

research

∙ 03/27/2020

Covering minimal separators and potential maximal cliques in P_t-free graphs

A graph is called P_t-free if it does not contain a t-vertex path as an ...

0 Andrzej Grzesik, et al. ∙

research

∙ 03/07/2020

Clustering powers of sparse graphs

We prove that if G is a sparse graph — it belongs to a fixed class of bo...

0 Jaroslav Nešetřil, et al. ∙

research

∙ 02/11/2020

Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space

For many algorithmic problems on graphs of treewidth t, a standard dynam...

0 Jesper Nederlof, et al. ∙

research

∙ 02/10/2020

On the effect of symmetry requirement for rendezvous on the complete graph

We consider a classic rendezvous game where two players try to meet each...

0 Marthe Bonamy, et al. ∙

research

∙ 12/03/2019

Jones' Conjecture in subcubic graphs

We confirm Jones' Conjecture for subcubic graphs. Namely, if a subcubic ...

0 Marthe Bonamy, et al. ∙

research

∙ 10/02/2019

Subexponential-time algorithms for finding large induced sparse subgraphs

Let C and D be hereditary graph classes. Consider the following problem:...

0 Jana Novotná, et al. ∙

research

∙ 10/01/2019

Graphs of bounded cliquewidth are polynomially χ-bounded

We prove that if C is a hereditary class of graphs that is polynomially ...

0 Marthe Bonamy, et al. ∙

research

∙ 08/09/2019

Shorter Labeling Schemes for Planar Graphs

An adjacency labeling scheme for a given class of graphs is an algorithm...

0 Marthe Bonamy, et al. ∙

research

∙ 07/10/2019

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

In the Maximum Independent Set problem we are asked to find a set of pai...

0 Maria Chudnovsky, et al. ∙

research

∙ 05/02/2019

Efficient approximation schemes for uniform-cost clustering problems in planar graphs

We consider the k-Median problem on planar graphs: given an edge-weighte...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 04/24/2019

A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs

We consider the classic Facility Location problem on planar graphs (non-...

0 Vincent Cohen-Addad, et al. ∙

Michał Pilipczuk

Featured Co-authors