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
Sort By
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
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
Preview abstract
In this paper we consider two above lower bound parameterizations of Node Multiway Cut — above maximum separating cut and above a natural LP-relaxation — and prove them to be fixed-parameter tractable. Our results imply O(4^k) algorithms for Vertex Cover above Maximum Matching and Almost 2-SAT as well as a O*(2^k) algorithm for Node Multiway Cut with a standard parameterization by the solution size, improving previous bounds for these
problems.
View details
Preview abstract
The classical Feedback Vertex Set problem asks, for a given undirected graph G and an integer k, to find a set of at most k vertices that hits all the cycles in the graph G.
Feedback Vertex Set has attracted a large amount of research in the parameterized setting, and subsequent kernelization and fixed-parameter algorithms have been a rich source of ideas in the field.
In this paper we consider a more general and difficult version of the problem, named Subset Feedback Vertex Set (SFVS in short) where an instance comes additionally with a set S of vertices, and we ask for a set of at most k vertices that hits all simple cycles passing through S.
Because of its applications in circuit testing and genetic linkage analysis SFVS was studied from the approximation algorithms perspective by Even et al. [SICOMP'00, SIDMA'00].
The question whether the SFVS problem is fixed parameter tractable was posed independently by Kawarabayashi and Saurabh in 2009. We answer this question affirmatively. We begin by showing that this problem is fixed-parameter tractable when parametrized by |S|. Next we present an algorithm which reduces the size of S to O(k^3) in 2^{O(k\log k)}n^{O(1)} time using kernelization techniques such as the 2-Expansion Lemma, Menger's theorem and Gallai's theorem. These two facts allow us to give a 2^{O(k\log k)} n^{O(1)} time algorithm solving the SFVS problem, proving that it is indeed fixed parameter
tractable.
View details
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 flow 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 flow from sources to sinks, such that each link in N has capacity k; the flow 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 fields, 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
Preview abstract
In the SCHED problem we are given a set of n jobs, together with their processing times and precedence constraints. The task is to order the jobs so that their total completion time is minimized. SCHED is a special case of the Traveling Repairman Problem with precedences. A natural dynamic programming algorithm solves both these problems in 2^n n^O(1) time, and whether there exists an algorithms solving
SCHED in O(c^n) time for some constant c < 2 was an open problem posted in 2004 by Woeginger. In this paper we answer this question positively.
View details
