Fast algorithms for identifying maximal common connected sets of interval graphs

Given a family of interval graphs F={G1=(V,E1),…,Gk=(V,Ek)}F={G1=(V,E1),…,Gk=(V,Ek)} on the same vertices V  , a set S⊂VS⊂V is a maximal common connected set of F   if the subgraphs of Gi,1⩽i⩽k,Gi,1⩽i⩽k, induced by S   are connected in all GiGi and S is maximal for the inclusion order. The maximal general common connected set for interval graphs problem (gen-CCPI) consists in efficiently computing the partition of V in maximal common connected sets of F  . This problem has many practical applications, notably in computational biology. Let n=|V|n=|V| and m=∑i=1k|Ei|. For k⩾2k⩾2, an algorithm in O((kn+m)logn)O((kn+m)logn) time is presented in Habib et al. [Maximal common connected sets of interval graphs, in: Combinatorial Pattern Matching (CPM), Lecture Notes in Computer Science, vol. 3109, Springer, Berlin, 2004, pp. 359–372]. In this paper, we improve this bound to O(knlogn+m)O(knlogn+m). Moreover, if the interval graphs are given as k sets of n   intervals, which is often the case in bioinformatics, we present a simple O(knlog2n) time algorithm.