Ph.D Thesis

Ph.D StudentZehavi Meirav
SubjectAlgorithms for Parameterized Graph Problems with
Applications to Biological Network Queries
DepartmentDepartment of Computer Science
Supervisors PROF. Ron Pinter
PROF. Hadas Shachnai
Full Thesis textFull thesis text - English Version


There is a vital need for fast algorithms for problems that are unlikely to admit efficient solutions, based on classical computational complexity theory. Parameterized Complexity is an exciting paradigm for coping with computationally hard problems, which is amazingly doable mathematically on a routine basis. In a nutshell, this paradigm aims to reduce the running times of algorithms for NP-hard problems, by confining the combinatorial explosion to a parameter k. In the past decade, three ``color coding-related techniques'' led to the design of breakthrough parameterized algorithms. These techniques are non-standard in the extent in which they connect seemingly disparate branches of Computer Science and Mathematics.

The color coding method, proposed by Alon et al. in 1994, consists of several iterations where one randomly colors elements that may be part of a solution. With high probability, we encounter an iteration where the elements of a solution have distinct colors, in which case they can be discovered via dynamic programming. Color coding can be derandomized and is suitable for developing algorithms for weighted problems. Divide-and-color, introduced by Chen et al. in 2006, improved upon color coding. It is a recursive technique, where each stage can be viewed as an application of color coding with only two colors. Multilinear detection and narrow sieves are tightly linked algebraic techniques, introduced in 2008 and 2010 by Koutis et al. and Bjorklund et al., respectively. These techniques are suitable for developing extremely fast randomized algorithms for unweighted problems. Recently, Fomin et al. obtained a powerful computation of representative sets, which enables development of deterministic algorithms for weighted problems that are faster than those based on divide-and-color, though not as those based on narrow sieves.

This thesis presents general schemes for mixing and improving upon color coding-related techniques, namely, divide-and-color, multilinear detection/narrow sieves and representative sets. On a high level, to create wholes greater than the sums of their parts, we propose strategies whose components combine different color coding-related techniques. For example, we introduce a strategy consisting of two narrow sieves-based procedures and a divide-and-color step. On a lower level, we examine improved methods for applying each color coding-related technique individually. This includes a unified tradeoff-based approach for computing representative sets, an application of the multlinear detection technique that integrates proper colorings of graphs, and a tool called guiding trees utilized for finding trees of unknown topologies.

We develop specific algorithms for classical problems such as k-Path, k-Internal Out-Branching and 3-Set k-Packing, as well as problems motivated by real-world applications to network queries, which are of major importance to systems biology. In particular, we initiate the study of the Partial Information Network Query problem. Roughly speaking, in a network query we seek a given pattern in a node-labeled graph. In network biology, such queries can be used to study the function, preservation and evolution of certain biological entities. Generalizing previous variants of network query problems, the Partial Information Network Query problem fits the scenario where only partial information is available on the topology of the pattern.