Algorithms for Some H-Join Decompositions

A

homogeneous pair

(also known as a

2-module

) of a graph is a pair {

M

1

,

M

2

} of disjoint vertex subsets 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 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 (if any) a homogeneous pair, which not only improves a previous bound of

O

(

mn

3

) [Everett, Klein and Reed 1997], but also uses a nice structural property of homogenous pairs. Our result can be extended to compute the whole homogeneous pair decomposition tree, within the same complexity. Using similar ideas, we present an

O

(

nm

2

)-time algorithm to compute a

N

-join decomposition of a graph, improving a previous

O

(

n

6

) algorithm [Feder

et al.

2005]. These two decompositions are special case of

H-joins

[Bui-Xuan, Telle and Vatshelle 2010] to which our techniques apply.