2014/03/08 by Olawale Hassan, Iyad Kanj, Hassan, Olawale +5
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1403.2009
arxiv created 2014/03/08 · arxiv updated 2014/03/11
In the (parameterized) Ordered List Subgraph Embedding problem (p-OLSE) we are given two graphs G and H, each with a linear order defined on its vertices, a function L that associates with every vertex in G a list of vertices in H, and a parameter k. The question is to decide if we can embed (one-to-one) a subgraph S of G of k vertices into H such that: (1) every vertex of S is mapped to a vertex from its associated list, (2) the linear orders inherited by S and its image under the embedding are respected, and (3) if there is an edge between two vertices in S then there is an edge between their images. If we require the subgraph S to be embedded as an induced subgraph, we obtain the Ordered List Induced Subgraph Embedding problem (p-OLISE). The p-OLSE and p-OLISE problems model various problems in Bioinformatics related to structural comparison/alignment of proteins. We investigate the complexity of p-OLSE and p-OLISE with respect to the following structural parameters: the width ΔL of the function L (size of the largest list), and the maximum degree ΔH of H and ΔG of G. In terms of the structural parameters under consideration, we draw a complete complexity landscape of p-OLSE and p-OLISE (and their optimization versions) with respect to the computational frameworks of classical complexity, parameterized complexity, and approximation.