Prof. Meirav Zehavi

In the PARTIAL INFORMATION NETWORK QUERY (PINQ) problem, we are given a host graph H, and a pattern P whose topology is partially known. We seek a subgraph of H that resembles P. PINQ is a generalization of Subgraph Isomorphism, where the topology of P is known, and Graph Motif, where the topology of P is unknown. This generalization has important applications to bioinformatics, since it addresses the major challenge of analyzing biological networks in the absence of certain topological data. In this paper, we use a non-standard part-algebraic/part-combinatorial hybridization strategy to develop an exact parameterized algorithm as well as an FPT-approximation scheme for PINQ, allowing near resemblance between H and P. We thus unify and significantly improve previous results related to network queries.