13 citations · 42 across the 7 of their papers we have counts for
12 papers
Twin-width and generalized coloring numbers
Jan Dreier, Jakub Gajarsky, Yiting Jiang +2
In this paper, we prove that a graph with no -subgraph and twin-width has -admissibility and -coloring numbers bounded from above by an exponential function…
First-order interpretations of bounded expansion classes
Jakub Gajarský, Stephan Kreutzer, Jaroslav Nešetřil +4
The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-che…
A New Perspective on FO Model Checking of Dense Graph Classes
Jakub Gajarský, Petr Hliněný, Daniel Lokshtanov +2
We study the first-order (FO) model checking problem of dense graphs, namely those which have FO interpretations in (or are FO transductions of) some sparse graph classes. We give…
Recovering sparse graphs
Jakub Gajarsky, Daniel Kral
We construct a fixed parameter algorithm parameterized by d and k that takes as an input a graph G' obtained from a d-degenerate graph G by complementing on at most k arbitrary sub…
Parameterized Shifted Combinatorial Optimization
Jakub Gajarský, Petr Hliněný, Martin Koutecký +1
Shifted combinatorial optimization is a new nonlinear optimization framework which is a broad extension of standard combinatorial optimization, involving the choice of several feas…
Parameterized Extension Complexity of Independent Set and Related Problems
Jakub Gajarský, Petr Hliněný, Hans Raj Tiwary
Let be a graph on vertices and be the convex hull of characteristic vectors of its independent sets of size at most . We study extension complexity…
FO Model Checking on Posets of Bounded Width
Jakub Gajarský, Petr Hliněný, Daniel Lokshtanov +4
Over the past two decades the main focus of research into first-order (FO) model checking algorithms have been sparse relational structures-culminating in the FPT-algorithm by Groh…
First order limits of sparse graphs: Plane trees and path-width
Jakub Gajarsky, Petr Hlineny, Tomas Kaiser +5
Nesetril and Ossona de Mendez introduced the notion of first order convergence as an attempt to unify the notions of convergence for sparse and dense graphs. It is known that there…
Faster Existential FO Model Checking on Posets
Jakub Gajarský, Petr Hliněný, Jan Obdržálek +1
We prove that the model checking problem for the existential fragment of first-order (FO) logic on partially ordered sets is fixed-parameter tractable (FPT) with respect to the for…
Parameterized Algorithms for Modular-Width
Jakub Gajarský, Michael Lampis, Sebastian Ordyniak
It is known that a number of natural graph problems which are FPT parameterized by treewidth become W-hard when parameterized by clique-width. It is therefore desirable to find a d…
Kernelization Using Structural Parameters on Sparse Graph Classes
Jakub Gajarský, Petr Hliněný, Jan Obdržálek +5
Meta-theorems for polynomial (linear) kernels have been the subject of intensive research in parameterized complexity. Heretofore, meta-theorems for linear kernels exist on graphs…
Kernelizing MSO Properties of Trees of Fixed Height, and Some Consequences
Jakub Gajarsky, Petr Hlineny
Fix an integer h>=1. In the universe of coloured trees of height at most h, we prove that for any graph decision problem defined by an MSO formula with r quantifiers, there exists…