16 citations · 188 across the 122 of their papers we have counts for
15 papers · 1 filter
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…