4 citations · 5 across the 6 of their papers we have counts for
9 papers
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…
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…
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 $…
Treedepth vs circumference
Marcin Briański, Gwenaël Joret, Konrad Majewski +3
The circumference of a graph is the length of a longest cycle in , or if has no cycle. Birmelé (2003) showed that the treewidth of a graph is at most its c…
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…
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…
The Asymmetric Travelling Salesman Problem in Sparse Digraphs
Łukasz Kowalik, Konrad Majewski
Asymmetric Travelling Salesman Problem (ATSP) and its special case Directed Hamiltonicity are among the most fundamental problems in computer science. The dynamic programming algor…