research
∙
08/23/2023
Cliquewidth and dimension
We prove that every poset with bounded cliquewidth and with sufficiently...
share
research
∙
07/20/2023
A parameterized approximation scheme for the 2D-Knapsack problem with wide items
We study a natural geometric variant of the classic Knapsack problem cal...
research
∙
07/14/2023
Sparse induced subgraphs in P_6-free graphs
We prove that a number of computational problems that ask for the larges...
research
∙
07/03/2023
Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
Dynamic programming on various graph decompositions is one of the most f...
research
∙
07/01/2023
Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard
Let d be a positive integer. For a finite set X ⊆ℝ^d, we define its inte...
research
∙
05/25/2023
Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
We show that the Maximum Weight Independent Set problem (MWIS) can be so...
research
∙
04/14/2023
Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1
We prove that there is a randomized polynomial-time algorithm that given...
research
∙
04/04/2023
Dynamic treewidth
We present a data structure that for a dynamic graph G that is updated b...
research
∙
02/26/2023
Partitioning edges of a planar graph into linear forests and a matching
We show that the edges of any planar graph of maximum degree at most 9 c...
research
∙
01/31/2023
Flipper games for monadically stable graph classes
A class of graphs 𝒞 is monadically stable if for any unary expansion 𝒞 o...
research
∙
01/06/2023
Simpler and faster algorithms for detours in planar digraphs
In the directed detour problem one is given a digraph G and a pair of ve...
research
∙
12/03/2022
Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments
In the Maximum Weight Independent Set of Rectangles problem (MWISR) we a...
research
∙
11/28/2022
On digraphs without onion star immersions
The t-onion star is the digraph obtained from a star with 2t leaves by r...
research
∙
10/26/2022
Fixed-parameter tractability of Graph Isomorphism in graphs with an excluded minor
We prove that Graph Isomorphism and Canonization in graphs excluding a f...
research
∙
10/26/2022
Highly unbreakable graph with a fixed excluded minor are almost rigid
A set X ⊆ V(G) in a graph G is (q,k)-unbreakable if every separation (A,...
research
∙
08/16/2022
Polynomial kernel for immersion hitting in tournaments
For a fixed simple digraph H without isolated vertices, we consider the ...
research
∙
06/23/2022
On the Complexity of Problems on Tree-structured Graphs
In this paper, we introduce a new class of parameterized problems, which...
research
∙
06/16/2022
Twin-width and types
We study problems connected to first-order logic in graphs of bounded tw...
research
∙
05/30/2022
Independence number of intersection graphs of axis-parallel segments
We prove that for any triangle-free intersection graph of n axis-paralle...
research
∙
05/05/2022
Computing treedepth in polynomial space and linear fpt time
The treedepth of a graph G is the least possible depth of an elimination...
research
∙
05/01/2022
Dynamic data structures for parameterized string problems
We revisit classic string problems considered in the area of parameteriz...
research
∙
03/31/2022
Transducing paths in graph classes with unbounded shrubdepth
Transductions are a general formalism for expressing transformations of ...
research
∙
02/15/2022
Graphs of bounded twin-width are quasi-polynomially χ-bounded
We prove that for every t∈ℕ there is a constant γ_t such that every grap...
research
∙
01/26/2022
Treelike decompositions for transductions of sparse graphs
We give new decomposition theorems for classes of graphs that can be tra...
research
∙
01/23/2022
Bounding generalized coloring numbers of planar graphs using coin models
We study Koebe orderings of planar graphs: vertex orderings obtained by ...
research
∙
11/05/2021
Algorithms and data structures for first-order logic with connectivity under vertex failures
We introduce a new data structure for answering connectivity queries in ...
research
∙
10/15/2021
Compact representation for matrices of bounded twin-width
For every fixed d ∈ℕ, we design a data structure that represents a binar...
research
∙
07/13/2021
Maintaining 𝖢𝖬𝖲𝖮_2 properties on dynamic structures with bounded feedback vertex number
Let φ be a sentence of 𝖢𝖬𝖲𝖮_2 (monadic second-order logic with quantific...
research
∙
07/08/2021
Stable graphs of bounded twin-width
We prove that every class of graphs 𝒞 that is monadically stable and has...
research
∙
05/04/2021
Isolation schemes for problems on decomposable graphs
The Isolation Lemma of Mulmuley, Vazirani and Vazirani [Combinatorica'87...
research
∙
03/31/2021
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths
In the Disjoint Paths problem, the input is an undirected graph G on n v...
research
∙
03/26/2021
On objects dual to tree-cut decompositions
Tree-cut width is a graph parameter introduced by Wollan that is an anal...
research
∙
12/21/2020
Efficient sequential and parallel algorithms for multistage stochastic integer programming using proximity
We consider the problem of solving integer programs of the form min{ c^⊺...
research
∙
11/30/2020
Integer Programming and Incidence Treedepth
Recently a strong connection has been shown between the tractability of ...
research
∙
09/28/2020
Quasi-polynomial-time algorithm for Independent Set in P_t-free graphs via shrinking the space of induced paths
In a recent breakthrough work, Gartland and Lokshtanov [FOCS 2020] showe...
research
∙
07/15/2020
Rankwidth meets stability
We study two notions of being well-structured for classes of graphs that...
research
∙
05/31/2020
Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
We present a data structure that in a dynamic graph of treedepth at most...
research
∙
04/20/2020
Finding large H-colorable subgraphs in hereditary graph classes
We study the Max Partial H-Coloring problem: given a graph G, find the l...
research
∙
03/31/2020
VC density of set systems defnable in tree-like graphs
We study set systems definable in graphs using variants of logic with di...
research
∙
03/27/2020
Covering minimal separators and potential maximal cliques in P_t-free graphs
A graph is called P_t-free if it does not contain a t-vertex path as an ...
research
∙
03/07/2020
Clustering powers of sparse graphs
We prove that if G is a sparse graph — it belongs to a fixed class of bo...
research
∙
02/11/2020
Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space
For many algorithmic problems on graphs of treewidth t, a standard dynam...
research
∙
02/10/2020
On the effect of symmetry requirement for rendezvous on the complete graph
We consider a classic rendezvous game where two players try to meet each...
research
∙
12/03/2019
Jones' Conjecture in subcubic graphs
We confirm Jones' Conjecture for subcubic graphs. Namely, if a subcubic ...
research
∙
10/02/2019
Subexponential-time algorithms for finding large induced sparse subgraphs
Let C and D be hereditary graph classes. Consider the following problem:...
research
∙
10/01/2019
Graphs of bounded cliquewidth are polynomially χ-bounded
We prove that if C is a hereditary class of graphs that is polynomially ...
research
∙
08/09/2019
Shorter Labeling Schemes for Planar Graphs
An adjacency labeling scheme for a given class of graphs is an algorithm...
research
∙
07/10/2019
Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
In the Maximum Independent Set problem we are asked to find a set of pai...
research
∙
05/02/2019
Efficient approximation schemes for uniform-cost clustering problems in planar graphs
We consider the k-Median problem on planar graphs: given an edge-weighte...
research
∙
04/24/2019