Finding Common Structured Patterns in Linear Graphs

International audienceA linear graph is a graph whose vertices are linearly ordered. This linear ordering allows pairs of disjoint edges to be either preceding (<), nesting (@) or crossing (G). Given a family of linear graphs, and a non-empty subset R f<;@; Gg, we are interested in the Maximum Common Structured Pattern (MCSP) problem: nd a maximum size edge-disjoint graph, with edge-pairs all comparable by one of the relations in R, that occurs as a subgraph in each of the linear graphs of the family. The MCSP problem generalizes many structure-comparison and structureprediction problems that arise in computational molecular biology. We give tight hardness results for the MCSP problem for f<; Gg-structured patterns and f@; Gg-structured patterns. Furthermore, we prove that the problem is approximable within ratios: (i) 2H (k) for f<; Gg-structured patterns, (ii) k1=2 for f@; Gg-structured patterns, and (iii) O( p k log k) for f<;@; Gg-structured patterns, where k is the size of the optimal solution and H (k) = Pk i=1 1=i is the k-th harmonic number. Also, we provide combinatorial results concerning the dierent types of structured patterns that are of independent interest in their own right