16 citations · 188 across the 122 of their papers we have counts for
89 papers · 1 filter
SETH-based Lower Bound for Dynamic Degeneracy
Konrad Majewski, Michał Pilipczuk
In this work, we consider the problem of maintaining an approximate value of degeneracy of a given dynamic -vertex graph updated by edge insertions and deletions. From the w…
Dynamic domination and independence in sparse graphs
Bartłomiej Bosek, Wojciech Nadara, Michał Pilipczuk +1
Let be a class of graphs of bounded expansion and be fixed. We give a dynamic data structure that for a given dynamic graph , updated by edge i…
Dynamic Detours
Daniel Dadush, Michał Pilipczuk, Amadeus Reinald +2
Fix a parameter . We give dynamic data structures that for a fully dynamic undirected graph , updated over time by edge insertions and edge deletions, can answe…
Pattern-Sparse Tree Decompositions in -Minor-Free Graphs
Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk
Given an -minor-free graph and an integer , our main technical contribution is sampling in randomized polynomial time an induced subgraph of and a tree decomposi…
Dynamic data structures for twin-ordered matrices
Bartłomiej Bosek, Jadwiga Czyżewska, Evangelos Kipouridis +4
We present a dynamic data structure for representing binary matrices that are -twin-ordered, for a~fixed parameter . Our structure supports cell queries and singl…
Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number
Daniel Lokshtanov, Michał Pilipczuk, Paweł Rzążewski
The independence number of a tree decomposition is the size of a largest independent set contained in a single bag. The tree-independence number of a graph is the minimum indep…
On Integer Programs That Look Like Paths
Marcin Briański, Alexandra Lassota, Kristýna Pekárková +2
Solving integer programs of the form is, in general, $…
Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
Michał Pilipczuk, Giannos Stamoulis, Michał Włodarczyk
In the Disjoint Shortest Paths problem one is given a graph and a set of vertex pairs. The question is whether there exist verte…
Faster diameter computation in graphs of bounded Euler genus
Kacper Kluk, Marcin Pilipczuk, Michał Pilipczuk +1
We show that for any fixed integer , there exists an algorithm that computes the diameter and the eccentricies of all vertices of an input unweighted, undirected -vert…
Embedding Planar Graphs into Graphs of Treewidth
Hsien-Chih Chang, Vincent Cohen-Addad, Jonathan Conroy +3
Cohen-Addad, Le, Pilipczuk, and Pilipczuk [CLPP23] recently constructed a stochastic embedding with expected distortion of -vertex planar graphs (with polynomial…
Minor Containment and Disjoint Paths in almost-linear time
Tuukka Korhonen, Michał Pilipczuk, Giannos Stamoulis
We give an algorithm that, given graphs and , tests whether is a minor of in time ; here, is the number of vertices of and the ${\cal…
Parameterized dynamic data structure for Split Completion
Konrad Majewski, Michał Pilipczuk, Anna Zych-Pawlewicz
We design a randomized data structure that, for a fully dynamic graph updated by edge insertions and deletions and integers fixed upon initialization, maintains the answ…
Parameterized algorithms for block-structured integer programs with large entries
Jana Cslovjecsek, Martin Koutecký, Alexandra Lassota +2
We study two classic variants of block-structured integer programming. Two-stage stochastic programs are integer programs of the form $\{A_i \mathbf{x} + D_i \mathbf{y}_i = \mathbf…
Fully dynamic approximation schemes on planar and apex-minor-free graphs
Tuukka Korhonen, Wojciech Nadara, Michał Pilipczuk +1
The classic technique of Baker [J. ACM '94] is the most fundamental approach for designing approximation schemes on planar, or more generally topologically-constrained graphs, and…
A parameterized approximation scheme for the 2D-Knapsack problem with wide items
Michal Pilipczuk, Mathieu Mari, Timothe Picavet
We study a natural geometric variant of the classic Knapsack problem called 2D-Knapsack: we are given a set of axis-parallel rectangles and a rectangular bounding box, and the goal…
Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
Benjamin Bergougnoux, Vera Chekan, Robert Ganian +5
Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simpl…
Sparse induced subgraphs in P_6-free graphs
Maria Chudnovsky, Rose McCarty, Marcin Pilipczuk +2
We prove that a number of computational problems that ask for the largest sparse induced subgraph satisfying some property definable in CMSO2 logic, most notably Feedback Vertex Se…
Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard
Łukasz Kowalik, Alexandra Lassota, Konrad Majewski +2
Let be a positive integer. For a finite set , we define its integer cone as the set $\mathsf{IntCone}(X) := \{ \sum_{x \in X} λ_x \cdot x \mid λ_x \in…
Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
Peter Gartland, Daniel Lokshtanov, Tomáš Masařík +3
We show that the Maximum Weight Independent Set problem (MWIS) can be solved in quasi-polynomial time on -free graphs (graphs excluding a fixed graph as an induced subgraph)…
Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1
Vincent Cohen-Addad, Hung Le, Marcin Pilipczuk +1
We prove that there is a randomized polynomial-time algorithm that given an edge-weighted graph excluding a fixed-minor on vertices and an accuracy parameter $\varepsil…
Dynamic treewidth
Tuukka Korhonen, Konrad Majewski, Wojciech Nadara +2
We present a data structure that for a dynamic graph that is updated by edge insertions and deletions, maintains a tree decomposition of of width at most under the p…
Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments
Jana Cslovjecsek, Michał Pilipczuk, Karol Węgrzycki
In the Maximum Weight Independent Set of Rectangles problem (MWISR) we are given a weighted set of axis-parallel rectangles in the plane. The task is to find a subset of pairwi…
Fixed-parameter tractability of Graph Isomorphism in graphs with an excluded minor
Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk +1
We prove that Graph Isomorphism and Canonization in graphs excluding a fixed graph as a minor can be solved by an algorithm working in time , where is s…
Polynomial kernel for immersion hitting in tournaments
Łukasz Bożyk, Michał Pilipczuk
For a fixed simple digraph without isolated vertices, we consider the problem of deleting arcs from a given tournament to get a digraph which does not contain as an immersi…