Computing H-Joins with Application to 2-Modular Decomposition

Michel Habib (1, 2) , Antoine Mamcarz (2, 1) , Fabien de Montgolfier (1, 2)

1 LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications
2 GANG - Networks, Graphs and Algorithms

We present here a general framework to design algorithms that compute H-join. For a given bipartite graph H, we say that a graph G admits a H-join decomposition or simply a H-join, if the vertices of G can be partitioned in |H| parts connected as in H. This graph H is a kind of pattern, that we want to discover in G. This framework allows us to present fastest known algorithms for the computation of P 4-join (aka N-join), P 5-join (aka W-join), C 6-join (aka 6-join). We also generalize this method to find a homogeneous pair (also known as 2-module), a pair {M 1,M 2} such that for every vertex x∉(M 1∪M 2) and i∈{1,2}, x is either adjacent to all vertices in M i or to none of them. First used in the context of perfect graphs (Chvátal and Sbihi in Graphs Comb. 3:127-139, 1987), it is a generalization of splits (a.k.a. 1-joins) and of modules. The algorithmics to compute them appears quite involved. In this paper, we describe an O(mn 2)-time algorithm computing all maximal homogeneous pairs of a graph, which not only improves a previous bound of O(mn 3) for finding only one pair (Everett et al. in Discrete Appl. Math. 72:209-218, 1997), but also uses a nice structural property of homogenous pairs, allowing to compute a canonical decomposition tree for sesquiprime graphs (i.e., graphs G having no module and such that for every vertex v∈G, G−v also has no module).

Mots clés: Algorithms; Graph; Graph decompositions; H-Join; Homogeneous pairs

Domaines: Algorithme et structure de données [cs.DS]

Michel Habib, Antoine Mamcarz, Fabien de Montgolfier. Computing H-Joins with Application to 2-Modular Decomposition. Algorithmica, 2014, 70 (2), pp.245-266. ⟨10.1007/s00453-013-9820-1⟩. ⟨hal-00921775⟩