16 citations · 188 across the 122 of their papers we have counts for
17 papers · 1 filter
First-Order Model Checking on Monadically Stable Graph Classes
Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann +3
A graph class is called monadically stable if one cannot interpret, in first-order logic, arbitrary large linear orders in colored graphs from . We prove…
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…
Simple and tight complexity lower bounds for solving Rabin games
Antonio Casares, Marcin Pilipczuk, Michał Pilipczuk +2
We give a simple proof that assuming the Exponential Time Hypothesis (ETH), determining the winner of a Rabin game cannot be done in time , where $k…
A polynomial-time -approximation algorithm for maximum independent set of connected subgraphs in a planar graph
Jana Cslovjecsek, Michał Pilipczuk, Karol Węgrzycki
In the Maximum Independent Set of Objects problem, we are given an -vertex planar graph and a family of objects, where each object is a connected subgraph…
Cliquewidth and dimension
Gwenaël Joret, Piotr Micek, Michał Pilipczuk +1
We prove that every poset with bounded cliquewidth and with sufficiently large dimension contains the standard example of dimension as a subposet. This applies in particular to…
Prime and polynomial distances in colourings of the plane
James Davies, Rose McCarty, Michał Pilipczuk
We give two extensions of the recent theorem of the first author that the odd distance graph has unbounded chromatic number. The first is that for any non-constant polynomial w…
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…
Partitioning edges of a planar graph into linear forests and a matching
Marthe Bonamy, Jadwiga Czyżewska, Łukasz Kowalik +1
We show that the edges of any planar graph of maximum degree at most can be partitioned into linear forests and a matching. Combined with known results, this implies that t…
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…