16 citations · 188 across the 122 of their papers we have counts for
15 papers · 1 filter
Efficient sequential and parallel algorithms for multistage stochastic integer programming using proximity
Jana Cslovjecsek, Friedrich Eisenbrand, Michał Pilipczuk +2
We consider the problem of solving integer programs of the form , where is a multistage stochastic matrix in the following sens…
Degeneracy of -free and -free graphs with no large complete bipartite subgraphs
Marthe Bonamy, Nicolas Bousquet, Michał Pilipczuk +3
A hereditary class of graphs is \emph{-bounded} if there exists a function such that every graph satisfies , where $χ(G)…
Integer Programming and Incidence Treedepth
Eduard Eiben, Robert Ganian, Dušan Knop +3
Recently a strong connection has been shown between the tractability of integer programming (IP) with bounded coefficients on the one side and the structure of its constraint matri…
Quasi-polynomial-time algorithm for Independent Set in -free graphs via shrinking the space of induced paths
Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski
In a recent breakthrough work, Gartland and Lokshtanov [FOCS 2020] showed a quasi-polynomial-time algorithm for Maximum Weight Independent Set in -free graphs, that is, graphs…
Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
Jiehua Chen, Wojciech Czerwiński, Yann Disser +8
We present a data structure that in a dynamic graph of treedepth at most , which is modified over time by edge insertions and deletions, maintains an optimum-height elimination…
Rankwidth meets stability
Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk +2
We study two notions of being well-structured for classes of graphs that are inspired by classic model theory. A class of graphs is monadically stable if it is impossible to de…
Erdős-Hajnal properties for powers of sparse graphs
Marcin Briański, Piotr Micek, Michał Pilipczuk +1
We prove that for every nowhere dense class of graphs , positive integer , and , the following holds: in every -vertex graph from $\mathcal{C}…
Finding large -colorable subgraphs in hereditary graph classes
Maria Chudnovsky, Jason King, Michał Pilipczuk +2
We study the \textsc{Max Partial -Coloring} problem: given a graph , find the largest induced subgraph of that admits a homomorphism into , where is a fixed patter…
VC density of set systems defnable in tree-like graphs
Adam Paszke, Michał Pilipczuk
We study set systems definable in graphs using variants of logic with different expressive power. Our focus is on the notion of Vapnik-Chervonenkis density: the smallest possible d…
Covering minimal separators and potential maximal cliques in -free graphs
Andrzej Grzesik, Tereza Klimošová, Marcin Pilipczuk +1
A graph is called -free} if it does not contain a -vertex path as an induced subgraph. While -free graphs are exactly cographs, the structure of -free graphs for…
Clustering powers of sparse graphs
Jaroslav Nešetřil, Patrice Ossona de Mendez, Michał Pilipczuk +1
We prove that if is a sparse graph --- it belongs to a fixed class of bounded expansion --- and is fixed, then the th power of can be par…
On polynomial recursive sequences
Michaël Cadilhac, Filip Mazowiecki, Charles Paperman +2
We study the expressive power of polynomial recursive sequences, a nonlinear extension of the well-known class of linear recursive sequences. These sequences arise naturally in the…
The monitoring problem for timed automata
Alejandro Grez, Filip Mazowiecki, Michał Pilipczuk +2
We study a variant of the classical membership problem in automata theory, which consists of deciding whether a given input word is accepted by a given automaton. We do so under a…
On the effect of symmetry requirement for rendezvous on the complete graph
Marthe Bonamy, Michał Pilipczuk, Jean-Sébastien Sereni
We consider a classic rendezvous game where two players try to meet each other on a set of locations. In each round, every player visits one of the locations and the game finis…
Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space
Jesper Nederlof, Michał Pilipczuk, Céline M. F. Swennenhuis +1
For many algorithmic problems on graphs of treewidth , a standard dynamic programming approach gives an algorithm with time and space complexity $2^{\mathcal{O}(t)}\cdot n^{\mat…