Saket Saurabh - Publications#

Prof. Saurabh is the co-author of two influential books:

Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket (2015). Parameterized Algorithms. Springer. ISBN 978-3-319-21274-6.

Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav (2019). Kernelization:
Theory of Parameterized Preprocessing. Cambridge University Press. ISBN 9781107415157.

Prof. Saurabh is responsible for several breakthroughs in Theory of Algorithms:

Algorithmic Lower Bounds:

One of the main concepts in the complexity theory is NP- completeness, which distinguishes between computational problems that have relatively efficient solutions and those that are intractable. The recent trend in Computer Science is the “fine-grained” complexity, a successful attempt to refine this qualitative distinction into a quantitative by identifying the exact time required to solve problems. Saket was among the first pioneers establishing the lower bounds on exact running times of parameterized

problems under the assumptions of on the running times of algorithms solving satisfiability. The most significant are his tight lower bounds on the running time of algorithms for graphs of bounded treewidth, bounded cliquewidth and the framework for deriving superexponential lower bounds on the form of the running time of parameterized algorithms, which were published in SODA and SIAM J. Computing. These results paved the ground for other researchers to enter this area. The influential survey of Saket and his collaborators with an overview of the recent developments is published in the complexity theory column of EATCS Bulletin.

Kernelization and Approximation:

A subarea of parameterized complexity where large part of Saket’s research has focused is known as “preprocessing complexity” or kernelization. Preprocessing (data reduction or kernelization) as a strategy of coping with hard problems is universally used in almost every implementation. A natural question in this regard is how to measure the quality of preprocessing rules proposed for a specific problem. This issue is naturally framed in the parameterized complexity setting, leading to a systematic, mathematically sophisticated investigation of preprocessing subroutines.

Saket made several significant contributions in this emerging research area. First, he is known for a novel approach to establish several very general results (meta-theorems) about kernels on sparse graphs for various problems. The approach is based on fusing ideas from Logic, Topological Graph Theory and Algorithms. These meta theorems uncover the deep relationship between logic and combinatorial structures, an issue fundamental to computational complexity. Prior to his work, it was believed that kernelization algorithms are strongly problem dependent and these results were unexpected. This line of research was published in Journal of the ACM, and FOCS/SODA conferences. His other fundamental contributions in the field of kernelization include separation between Karp and Turing kernels (STACS and Transactions in Algorithms), and devising a generic methodology to show lower bounds on kernelization (ICALP and ACM Trans. Algorithms).

His contributions to the field of kernelization have acted as a catalyst in the rapid developments of the field. The main technical object he devised for the meta theorems for kernels, called protrusions, coupled with a new notion of sublinear treewidth also gave meta-theorems in the field of approximation algorithms. Especially, on sparse graphs such as planar graphs, graphs excluding a fixed minor and geometric graphs. These relation to approximation algorithms appeared in 2 SODA papers and now has been accepted to Journal of the ACM. Other result include a FOCS 2012 paper that gave an approximation algorithm, an optimal parameterized algorithm and a kernelization algorithm that unified, generalized, and improve a multitude of results in the literature.

Algorithmic combinatorics:

Here Saket is responsible for (a very clever) adaptation of classical combinatorial objects like sets and matroids for algorithmic applications. For example, he obtained efficient algorithmic proofs of the classical theorems from extremal combinatorics of Bollob ́as and Lov ́asz about representative sets. This algorithm has turned out to be a powerful tool for designing single-exponential parameterized and exact exponential time algorithms. These results were published in (SODA, ESA and Journal of the ACM and ACM Trans. Algorithms). The doctoral thesis of Fahad Panolan and Meirav Zehavi are devoted to further applications of Saket’s results.

Exact Algorithms:

One of the most recent breakthroughs of Saket, was reported in STOC 2016 (final version in Journal of the ACM), is a new general approach for designing exact exponential-time algorithms for subset problems. The approach is based on “monotone local search”, where the goal is to extend a partial solution to a solution by adding as few elements as possible. These results demonstrate an exciting and very concrete connection between parameterized algorithms and exponential-time algorithms.

New Directions:

Saket has initiated systematic study of parameterized problems on colored graphs, parameterized analysis of local search, matroids and matrices. One thing that deserves a special mention is his recent proposal for “lossy kernels”, where he proposed a new framework for analyzing the performance of preprocessing algorithms. The framework builds on the notion of kernelization from parameterized complexity. However, as opposed to the original notion of kernelization, the new definitions combine well with approximation algorithms and heuristics. This framework opens completely new research directions and our expectations are that within time this framework will develop in one of the main directions of research in parameterized complexity. A project proposal on this topic is currently funded by by ERC via Consolidator grant.

Versatility of research:

Saket is responsible for solving several important open problems in different areas. Some of these problems remained open for more than 20 years. He has established the fixed-parameter tractability of Bisection, Treewidth Graph Isomorphism, Distortion, Cochromatic Number on perfect graphs. Furthermore, he developed a polynomial space algorithm for Steiner Tree, as well as sub-exponential parameterized algorithms for Planar Directed Path, Rectilinear Steiner Tree. The beautiful work of Saket on fixed-parameter tractability of the first order oder checking on posets of bounded width as well as his contribution to the design of linear time algorithms is also worth mentioning. Thus his work spans many areas including logic, graph theory, combinatorial optimization and computational geometry.