16 citations · 188 across the 122 of their papers we have counts for
173 papers
Universally extendible characters
Benjamin Sambale
Let theta be an ordinary character or a Brauer character of a finite group N. We show that theta extends to every overgroup if and only if Z(N) <= Ker(the…
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…
Fatness and Flatness
Arnold Filtser, Hung Le, Nikolas Mählmann +2
Fat minors are the metric analog of graph minors that are tailored to the analysis of metric (edge-weighted) graphs and, more generally, metric spaces having a suitable notion of s…
Neighborhood Complexity and Radius-1 Merge-Width in Monadically Dependent Graph Classes
Jan Dreier, Nikolas Mählmann, Rose McCarty +2
Monadic dependence is a proposed structural dividing line for fixed-parameter tractability of first-order model checking on hereditary graph classes. A graph class is \emph{monadic…
A coarse block-cut tree theorem
Júlia Baligács, Václav Blažej, Jadwiga Czyżewska +2
We prove a coarse analogue of the classic fact that every graph can be decomposed along its cut-vertices into -connected components. Precisely, we prove that for every graph …
A coarse Menger's Theorem for planar and bounded genus graphs
Václav Blažej, Michał Pilipczuk, Evangelos Protopapas
Menger's Theorem is a fundamental result in graph theory. It states that if in a graph with distinguished sets of terminal vertices and there are no pairwise vertex…
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…
Coarse Balanced Separators in Fat-Minor-Free Graphs
Édouard Bonnet, Hung Le, Marcin Pilipczuk +1
Fat minors are a coarse analogue of graph minors where the subgraphs modeling vertices and edges of the embedded graph are required to be distant from each other, instead of just b…
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…
Tree decompositions whose trees are subgraphs: An application of Simon's factorization
Romain Bourneuf, Gwenaël Joret, Piotr Micek +2
We show that every connected graph has a tree decomposition indexed by a tree such that is a subgraph of and the width of the tree decomposition is bounded from abo…
Variants of Merge-Width and Applications
Karolina Drabik, Maël Dumas, Colin Geniet +3
Merge-width is a recently introduced family of graph parameters that unifies treewidth, clique-width, twin-width, and generalised colouring numbers. We prove the equivalence of sev…
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…
Efficient reversal of transductions of sparse graph classes
Jan Dreier, Jakub Gajarský, Michał Pilipczuk
(First-order) transductions are a basic notion capturing graph modifications that can be described in first-order logic. In this work, we propose an efficient algorithmic method to…
A Note on the Parameterised Complexity of Coverability in Vector Addition Systems
Michał Pilipczuk, Sylvain Schmitz, Henry Sinclair-Banks
We investigate the parameterised complexity of the classic coverability problem for vector addition systems (VAS): given a finite set of vectors , an initi…
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, $…
Box-Reachability in Vector Addition Systems
Shaull Almagor, Itay Hasson, Michał Pilipczuk +1
We consider a variant of reachability in Vector Addition Systems (VAS) dubbed \emph{box reachability}, whereby a vector is box-reachable from in a VAS i…
First-order transducibility among classes of sparse graphs
Jakub Gajarský, Jeremi Gładkowski, Jan Jedelský +2
We prove several negative results about first-order transducibility for classes of sparse graphs: - for every , the class of graphs of treewidth at most is…
Strong odd colorings in graph classes of bounded expansion
Michał Pilipczuk
We prove that for every and a graph class of bounded expansion , there exists some so that every graph from admits a…
Separability Properties of Monadically Dependent Graph Classes
Édouard Bonnet, Samuel Braunfeld, Ioannis Eleftheriadis +5
A graph class is monadically dependent if one cannot interpret all graphs in colored graphs from using a fixed first-order interpretation. We prove that m…
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…
On graphs coverable by chubby shortest paths
Meike Hatzel, Michał Pilipczuk
Dumas, Foucaud, Perez, and Todinca [SIAM J. Disc. Math., 2024] proved that if the vertex set of a graph can be covered by shortest paths, then the pathwidth of is bound…
Low rank MSO
Mikołaj Bojańczyk, Michał Pilipczuk, Wojciech Przybyszewski +2
We introduce a new logic for describing properties of graphs, which we call low rank MSO. This is the fragment of monadic second-order logic in which set quantification is restrict…