# Jakub Onufry Wojtaszczyk

Phd in probability theory and Masters in CS obtained at Warsaw University. Publications in diverse fields of mathematics (functional analysis, probability theory, complexity theory) and CS (moderately exponential algorithms, graph algorithms, CSP)

### Research Areas

Authored Publications

Google Publications

Other Publications

Sort By

Solving the 2-disjoint connected subgraphs problem faster than 2n

Preview
Marek Cygan

Marcin Pilipczuk

Michal Pilipczuk

Proceedings of the 10th Latin American international conference on Theoretical Informatics, Springer-Verlag, Berlin, Heidelberg(2012), pp. 195-206

On multiway cut parameterized above lower bounds

Preview
Marek Cygan

Marcin Pilipczuk

Michal Pilipczuk

Proceedings of the 6th international conference on Parameterized and Exact Computation, Springer-Verlag, Berlin, Heidelberg(2012), pp. 1-12

Approximation Schemes for Capacitated Geometric Network Design

Anna Adamaszek

Artur Czumaj

Andrzej Lingas

ICALP 2011, Rynek Główny 12 (to appear)

Preview abstract
We study a capacitated network design problem in geometric setting. We assume that the input consists of an integral link capacity k and two sets of points on a plane, sources and sinks, each source/sink having an associated integral demand (amount of ﬂow to be shipped from/to). The capacitated geometric network design problem is to construct a minimum-length network N that allows to route the requested ﬂow from sources to sinks, such that each link in N has capacity k; the ﬂow is splittable and parallel links are allowed in N.
The capacitated geometric network design problem generalizes, among others, the geometric Steiner tree problem, and as such it is NP-hard. We show that if the demands are polynomially bounded and the link capacity k
is not too large, the single-sink capacitated geometric network design problem admits a polynomial-time approximation scheme. If the capacity is arbitrarily large,
then we design a quasi-polynomial time approximation scheme for the capacitated
geometric network design problem allowing for arbitrary number of sinks. Our results rely on a derivation of an upper bound on the number of vertices different from sources and sinks (the so called Steiner vertices) in an optimal network. The bound is polynomial in the total demand of the sources.
View details

Solving connectivity problems parameterized by treewidth in single exponential time

Marek Cygan

Jesper Nederlof

Marcin Pilipczuk

Michał Pilipczuk

Johann M. M. van Rooij

Foundations of Computer Science 2011, Rynek Główny 12 (to appear)

Preview abstract
For the vast majority of local problems on graphs of small treewidth (where by local we mean that a solution can be verified by checking separately the neighbourhood of each vertex), standard dynamic programming techniques give c^tw
|V|^O(1) time algorithms, where tw is the treewidth of the input graph, G = (V; E) and c is a constant. On the other hand, for problems with a global requirement (usually connectivity) the best–known algorithms were naive dynamic programming schemes running in at least tw^tw time.
We breach this gap by introducing a technique we named Cut&Count that allows to produce c^tw |V|^O(1) time Monte Carlo algorithms for most connectivity-type problems, including HAMILTONIAN PATH, STEINER TREE, FEEDBACK VERTEX SET and CONNECTED DOMINATING SET. These results have numerous consequences in various ﬁelds, like parameterized complexity, exact and approximate algorithms on planar and H-minor-free graphs and exact algorithms on graphs of bounded degree. The constant c in our algorithms is in all cases small, and in several cases we are able to show that improving those constants would cause the Strong Exponential Time Hypothesis to fail.
In contrast to the problems aiming to minimize the number
of connected components that we solve using Cut&Count as
mentioned above, we show that, assuming the Exponential Time
Hypothesis, the aforementioned gap cannot be breached for some problems that aim to maximize the number of connected components like CYCLE PACKING.
View details

No Results Found