Ph.D Thesis | |

Ph.D Student | Zehavi Meirav |
---|---|

Subject | Algorithms for Parameterized Graph Problems with Applications to Biological Network Queries |

Department | Department of Computer Science |

Supervisors | PROF. Ron Pinter |

PROF. Hadas Shachnai | |

Full Thesis text |

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.