Jakub Onufry Wojtaszczyk

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)
Authored Publications
Sort By
  • Title
  • Title, descending
  • Year
  • Year, descending
    On multiway cut parameterized above lower bounds
    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
    Preview
    Solving the 2-disjoint connected subgraphs problem faster than 2n
    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
    On Multiway Cut paramterized above lower bounds
    Marek Cygan
    Marcin Pilipczuk
    Michał Pilipczuk
    IPEC 2011 (to appear)
    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
    Scheduling partially ordered jobs faster than 2^n
    Marek Cygan
    Marcin Pilipczuk
    Michał Pilipczuk
    ESA (2011) (to appear)
    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
    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
    Subset Feedback Vertex Set is fixed parameter tractable
    Marek Cygan
    Marcin Pilipczuk
    Michał Pilipczuk
    ICALP 2011 (to appear)
    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