1 citations · 4 across the 22 of their papers we have counts for
26 papers
Time-Optimal APSP and Matrix Multiplication in Classes of Linear Neighborhood Complexity
Édouard Bonnet, Julien Duron, Marcin Pilipczuk +2
The notion of linear neighborhood complexity is a very general structural assumption on a graph class, covering most classes of sparse graphs such as planar graphs, graphs excludin…
A tight lower bound for malicious online bipartite matching with limited recourse budget
Julia Baligacs, Bartłomiej Bosek, Paweł Putra +2
We study one-sided online bipartite matching with recourse. In this setting, one side of a bipartite graph is known in advance, while vertices on the other side arrive online toget…
Multiway -Cut is fixed-parameter tractable
Tony Huynh, Eun Jung Kim, Sang-il Oum +2
A connectivity function on a finite set is a function that is submodular and symmetric, with . Given a connectivity function via…
An Erdős-Pósa theorem for cycles and faces of distinct lengths
J. Pascal Gollin, Maximilian Gorsky, Meike Hatzel +6
We show that for every , every graph contains vertex-disjoint cycles of different lengths, or there exists a set with $|X| \in \mathcal…
Fast decremental tree sums in forests
Benjamin Aram Berendsohn, Marek Sokołowski
We study two fundamental decremental dynamic graph problems. In both problems, we need to maintain a vertex-weighted forest of size under edge deletions, weight updates, and a…
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…
Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
Sang-il Oum, Marek Sokołowski
We study connectivity functions, that is, integer-valued symmetric submodular functions on a finite ground set attaining on the empty set. For a connectivity function on an…
Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
Adam Karczmarz, Wojciech Nadara, Marek Sokołowski
In this paper, we show new strongly polynomial work-depth tradeoffs for computing single-source shortest paths (SSSP) in non-negatively weighted directed graphs in parallel. Most i…
Fully dynamic biconnectivity in time
Jacob Holm, Wojciech Nadara, Eva Rotenberg +1
We present a deterministic fully-dynamic data structure for maintaining information about the cut-vertices in a graph; i.e. the vertices whose removal would disconnect the graph. O…
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…
Half-integral Erdős-Pósa property for non-null - paths
Vera Chekan, Colin Geniet, Meike Hatzel +4
For a group , a -labelled graph is an undirected graph where every orientation of an edge is assigned an element of so that opposite orientations of the same edge are…
Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
Tuukka Korhonen, Marek Sokołowski
We give an algorithm that given a graph with vertices and edges and an integer , in time either outputs a rank decomposition of of width…
Elementary first-order model checking for sparse graphs
Jakub Gajarský, Michał Pilipczuk, Marek Sokołowski +2
It is known that for subgraph-closed graph classes the first-order model checking problem is fixed-parameter tractable if and only if the class is nowhere dense [Grohe, Kreutzer, S…
Exact Shortest Paths with Rational Weights on the Word RAM
Adam Karczmarz, Wojciech Nadara, Marek Sokołowski
Exact computation of shortest paths in weighted graphs has been traditionally studied in one of two settings. First, one can assume that the edge weights are real numbers and all t…
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…
Sparse Graphs of Twin-width 2 Have Bounded Tree-width
Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guśpiel +3
Twin-width is a structural width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS 2020]. Very briefly, its essence is a gradual reduction (a contraction sequence)…
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…
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…
Simpler and faster algorithms for detours in planar digraphs
Meike Hatzel, Konrad Majewski, Michał Pilipczuk +1
In the directed detour problem one is given a digraph and a pair of vertices and~, and the task is to decide whether there is a directed simple path from to in $…
Flipper games for monadically stable graph classes
Jakub Gajarský, Nikolas Mählmann, Rose McCarty +6
A class of graphs is monadically stable if for any unary expansion of , one cannot interpret, in first-order logic, arbitrarily l…
Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
Konrad Majewski, Tomáš Masařík, Jana Novotná +4
We revisit recent developments for the Maximum Weight Independent Set problem in graphs excluding a subdivided claw as an induced subgraph [Chudnovsky, Pilipczuk, Pilip…
Graphs of bounded twin-width are quasi-polynomially -bounded
Michał Pilipczuk, Marek Sokołowski
We prove that for every there is a constant such that every graph with twin-width at most and clique number has chromatic number bounded by $2^{γ_t…
Compact representation for matrices of bounded twin-width
Michał Pilipczuk, Marek Sokołowski, Anna Zych-Pawlewicz
For every fixed , we design a data structure that represents a binary matrix that is -twin-ordered. The data structure occupies bits, whi…
Maintaining properties on dynamic structures with bounded feedback vertex number
Konrad Majewski, Michał Pilipczuk, Marek Sokołowski
Let be a sentence of (monadic second-order logic with quantification over edge subsets and counting modular predicates) over the signature of graphs. We prese…