Technical Report PHD-2015-10

Title: Algorithms for Parameterized Graph Problems with Applications to Biological Network Queries
Authors: Meirav Zehavi
Supervisors: Ron Y. Pinter, Hadas Shachnai
Abstract: There is a growing, 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 techniques, known as ``color coding-related techniques'', led to the design of breakthrough parameterized algorithms. These techniques are non-standard in the extent in which they connect such seemingly disparate branches of Computer Science and Mathematics as matroid theory, linear algebra, graph theory and combinatorial optimization.

The original color coding method was proposed by Alon et al. in 1994. Roughly speaking, it 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, 3-Set k-Packing and Max (k,n-k)-Cut, 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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2015
To the main CS technical reports page

Computer science department, Technion