
Isolation schemes for problems on decomposable graphs
The Isolation Lemma of Mulmuley, Vazirani and Vazirani [Combinatorica'87...
read it

An Exponential Time Parameterized Algorithm for Planar Disjoint Paths
In the Disjoint Paths problem, the input is an undirected graph G on n v...
read it

On objects dual to treecut decompositions
Treecut width is a graph parameter introduced by Wollan that is an anal...
read it

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^⊺...
read it

Integer Programming and Incidence Treedepth
Recently a strong connection has been shown between the tractability of ...
read it

Quasipolynomialtime algorithm for Independent Set in P_tfree graphs via shrinking the space of induced paths
In a recent breakthrough work, Gartland and Lokshtanov [FOCS 2020] showe...
read it

Rankwidth meets stability
We study two notions of being wellstructured for classes of graphs that...
read it

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...
read it

Finding large Hcolorable subgraphs in hereditary graph classes
We study the Max Partial HColoring problem: given a graph G, find the l...
read it

VC density of set systems defnable in treelike graphs
We study set systems definable in graphs using variants of logic with di...
read it

Covering minimal separators and potential maximal cliques in P_tfree graphs
A graph is called P_tfree if it does not contain a tvertex path as an ...
read it

Clustering powers of sparse graphs
We prove that if G is a sparse graph — it belongs to a fixed class of bo...
read it

Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space
For many algorithmic problems on graphs of treewidth t, a standard dynam...
read it

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...
read it

Jones' Conjecture in subcubic graphs
We confirm Jones' Conjecture for subcubic graphs. Namely, if a subcubic ...
read it

Subexponentialtime algorithms for finding large induced sparse subgraphs
Let C and D be hereditary graph classes. Consider the following problem:...
read it

Graphs of bounded cliquewidth are polynomially χbounded
We prove that if C is a hereditary class of graphs that is polynomially ...
read it

Shorter Labeling Schemes for Planar Graphs
An adjacency labeling scheme for a given class of graphs is an algorithm...
read it

Quasipolynomial time approximation schemes for the Maximum Weight Independent Set Problem in Hfree graphs
In the Maximum Independent Set problem we are asked to find a set of pai...
read it

Efficient approximation schemes for uniformcost clustering problems in planar graphs
We consider the kMedian problem on planar graphs: given an edgeweighte...
read it

A PolynomialTime Approximation Scheme for Facility Location on Planar Graphs
We consider the classic Facility Location problem on planar graphs (non...
read it

On the Maximum Weight Independent Set Problem in graphs without induced cycles of length at least five
A hole in a graph is an induced cycle of length at least 4, and an antih...
read it

ModelChecking on Ordered Structures
We study the modelchecking problem for first and monadic secondorder ...
read it

Progressive Algorithms for Domination and Independence
We consider a generic algorithmic paradigm that we call progressive expl...
read it

Tight complexity lower bounds for integer linear programming with few constraints
We consider the ILP Feasibility problem: given an integer linear program...
read it

Randomized contractions meet lean decompositions
The randomized contractions technique, introduced by Chitnis et al. in 2...
read it

Firstorder interpretations of bounded expansion classes
The notion of bounded expansion captures uniform sparsity of graph class...
read it

Kernelization and approximation of distancer independent sets on nowhere dense graphs
For a positive integer r, a distancer independent set in an undirected ...
read it

Quasipolynomial time approximation schemes for packing and covering problems in planar graphs
We consider two optimization problems in planar graphs. In Maximum Weigh...
read it

Polynomial bounds for centered colorings on proper minorclosed graph classes
For p∈N, a coloring λ of the vertices of a graph G is pcentered if for ...
read it

Parameterized circuit complexity of model checking firstorder logic on sparse structures
We prove that for every class C of graphs with effectively bounded expan...
read it

Definable decompositions for graphs of bounded linear cliquewidth
We prove that for every positive integer k, there exists an MSO_1transd...
read it

On Directed Feedback Vertex Set parameterized by treewidth
We study the Directed Feedback Vertex Set problem parameterized by the t...
read it
Michał Pilipczuk
is this you? claim profile