Finding common structured patterns in linear graphs

A 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 (≬). Given a family of linear graphs, and a non-empty subset R⊆{<,⊏,≬}, we are interested in the Maximum Common Structured Pattern (MCSP) problem: find 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 structure-prediction problems that arise in computational molecular biology.We give tight hardness results for the MCSP problem for {<,≬}-structured patterns and {⊏,≬}-structured patterns. Furthermore, we prove that the problem is approximable within ratios: (i) 2ℋ(k) for {<,≬}-structured patterns, (ii) k1/2 for {⊏,≬}-structured patterns, and (iii) for {<,⊏,≬}-structured patterns, where k is the size of the optimal solution and is the kth harmonic number. Also, we provide combinatorial results concerning different types of structured patterns that are of independent interest in their own right.