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) k 1 / 2 for { ⊏, ≬ } -structured patterns, and (iii) O ( k log k ) for { <, ⊏, ≬ } -structured patterns, where k is the size of the optimal solution and ℋ ( k ) = ∑ i = 1 k 1 / i is the k th harmonic number. Also, we provide combinatorial results concerning different types of structured patterns that are of independent interest in their own right.

Authors

• Guillaume Fertin
• Danny Hermelin
• Romeo Rizzi
• Stéphane Vialette

Keywords

• Linear graphs
• Approximation