Zobrazeno 1 - 10
of 452
pro vyhledávání: '"PILIPCZUK, MICHAŁ"'
We give an algorithm that, given graphs $G$ and $H$, tests whether $H$ is a minor of $G$ in time ${\cal O}_H(n^{1+o(1)})$; here, $n$ is the number of vertices of $G$ and the ${\cal O}_H(\cdot)$-notation hides factors that depend on $H$ and are comput
Externí odkaz:
http://arxiv.org/abs/2404.03958
Autor:
Kowalska, Katarzyna, Pilipczuk, Michał
We study parameterized and approximation algorithms for a variant of Set Cover, where the universe of elements to be covered consists of points in the plane and the sets with which the points should be covered are segments. We call this problem Segme
Externí odkaz:
http://arxiv.org/abs/2402.16466
We design a randomized data structure that, for a fully dynamic graph $G$ updated by edge insertions and deletions and integers $k, d$ fixed upon initialization, maintains the answer to the Split Completion problem: whether one can add $k$ edges to $
Externí odkaz:
http://arxiv.org/abs/2402.08816
It is known that for subgraph-closed graph classes the first-order model checking problem is fixed-parameter tractable if and only if the class is nowhere dense [Grohe, Kreutzer, Siebertz, STOC 2014]. However, the dependency on the formula size is no
Externí odkaz:
http://arxiv.org/abs/2401.16230
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{b}_i\textrm{ for all }i=1,\ldots,n\}$, where $A_i$ and $D_i$ are boun
Externí odkaz:
http://arxiv.org/abs/2311.01890
Autor:
Casares, Antonio, Pilipczuk, Marcin, Pilipczuk, Michał, Souza, Uéverton S., Thejaswini, K. S.
We give a simple proof that assuming the Exponential Time Hypothesis (ETH), determining the winner of a Rabin game cannot be done in time $2^{o(k \log k)} \cdot n^{O(1)}$, where $k$ is the number of pairs of vertex subsets involved in the winning con
Externí odkaz:
http://arxiv.org/abs/2310.20433
In the Maximum Independent Set of Objects problem, we are given an $n$-vertex planar graph $G$ and a family $\mathcal{D}$ of $N$ objects, where each object is a connected subgraph of $G$. The task is to find a subfamily $\mathcal{F} \subseteq \mathca
Externí odkaz:
http://arxiv.org/abs/2310.20325
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 it has been applied in a myriad of different variants and settings thr
Externí odkaz:
http://arxiv.org/abs/2310.20623
We prove that every poset with bounded cliquewidth and with sufficiently large dimension contains the standard example of dimension $k$ as a subposet. This applies in particular to posets whose cover graphs have bounded treewidth, as the cliquewidth
Externí odkaz:
http://arxiv.org/abs/2308.11950
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 $f$ with integer coefficients and positive leading coefficient, every finit
Externí odkaz:
http://arxiv.org/abs/2308.02483