Unifying two Graph Decompositions with Modular Decomposition$^0$
\normalsize{Binh-Minh Bui-Xuan}$^1$
\normalsize{Michel Habib}$^2$
\normalsize{Vincent Limouzy}$^2$
\normalsize{Fabien de Montgolfier}$^2$
We introduces the umodules, a generalisation of the notion of graph module. The theory we develop captures among others undirected graphs, tournaments, digraphs, and $2-$structures. We show that, under some axioms, a unique decomposition tree exists for umodules. Polynomial-time algorithms are provided for: non-trivial umodule test, maximal umodule computation, and decomposition tree computation when the tree exists. Our results unify many known decomposition like modular and bi-join decomposition of graphs, and a new decomposition of tournaments. % when restricted to undirected graphs generalises the well-studied modular graph decomposition, and meets the recently introduced bi-join decomposition. Applied to tournaments, %All other cases up to our knowledge lead to new notions. %First some properties of the umodule family are presented. FM : on s'en doute !! %Polynomial-time algorithms for non-trivial umodule existence test and for maximal umodule computation are provided. %When the input structure fulfils some natural axioms, the umodule family is shown to own a unique decomposition tree. %We provide various algorithms to compute this tree in polynomial time: their exact performance depends on some size assumption. %Among other our theory applies to two particular cases: undirected graphs and tournaments. %First, the latter tree-decomposition time is linear in the size of the input structure. %Besides, in theses two cases our work can also be seen as a unification of the bi-join undirected graph decomposition and of a new tournament decomposition. %FM :enleve : A plus ! %From this viewpoint, we address the total decomposability of those structures, and obtain strong structural relationship between the so-called cographs and round tournaments. %We then show how our theory provides a very natural manner to obtain several results on the so-called round tournaments, including characterisation by forbidding induced subgraphs, recognition, isomorphism testing, and feedback vertex set computation.
ShortUmodule.tex
\documentclass[twoside]{article}
\usepackage{ShortUmodule}

\title{Unifying two Graph Decompositions with Modular Decomposition$^0$}
\author{
\normalsize{Binh-Minh Bui-Xuan}$^1$
\and
\normalsize{Michel Habib}$^2$
\and
\normalsize{Vincent Limouzy}$^2$
\and
\normalsize{Fabien de Montgolfier}$^2$
}
% 


% \institute{\textsc{LIRMM}, Universit\'e Montpellier 2, France. \texttt{buixuan@lirmm.fr} \and 
% \textsc{LIAFA}, Universit\'e Paris 7, France.
% \texttt{\{habib,limouzy,fm\}@liafa.jussieu.fr}}
\newcommand{\TODO}[1]{{\large \bf #1 }}

\setlength{\itemsep}{0cm}
\setlength{\parsep}{0cm}
\addtolength{\leftmargin}{-0.1cm}
\begin{document}
\setcounter{footnote}{0}
\footnotetext{Research supported by the French ANR project ``Graph Decompositions and Algorithms (GRAAL)''}
\setcounter{footnote}{1}
\footnotetext{LIRMM, Univ. Montpellier \texttt{buixuan@lirmmfr}}
\setcounter{footnote}{2}
\footnotetext{LIAFA, Univ. Paris Diderot. \texttt{\{habib,limouzy,fm\}@liafa.jussieu.fr}}
\date{}
\maketitle
% \TODO{Modifier l'abstract pour que ce soit coherent avec le contenu}
\vspace{-0.75cm}
\begin{abstract}
We introduces the \emph{umodules}, a generalisation of the notion of graph module.
The theory we develop captures among others undirected graphs, tournaments, digraphs, and $2-$structures.
We show that, under some axioms, a unique decomposition tree exists for umodules.
Polynomial-time algorithms are provided for:  non-trivial umodule test, maximal umodule computation, and decomposition tree computation when the tree exists.
Our results unify many known decomposition like modular and bi-join decomposition of graphs, and a new decomposition of tournaments.



% when restricted to undirected graphs generalises the well-studied modular graph decomposition, and meets the recently introduced bi-join decomposition. Applied to tournaments, 
%All other cases up to our knowledge lead to new notions.

%First some properties of the umodule family are presented. FM : on s'en doute !!
%Polynomial-time algorithms for non-trivial umodule existence test and for maximal umodule computation are provided.
%When the input structure fulfils some natural axioms, the umodule family is shown to own a unique decomposition tree.
%We provide various algorithms to compute this tree in polynomial time: their exact performance depends on some size assumption.

%Among other our theory applies to two particular cases: undirected graphs and tournaments.
%First, the latter tree-decomposition time is linear in the size of the input structure.
%Besides, in theses two cases our work can also be seen as a unification of the bi-join undirected graph decomposition and of a new tournament decomposition.

%FM :enleve : A plus !
%From this viewpoint, we address the total decomposability of those structures, and obtain strong structural relationship between the so-called cographs and round tournaments.
%We then show how our theory provides a very natural manner to obtain several results on the so-called round tournaments, including characterisation by forbidding induced subgraphs, recognition, isomorphism testing, and feedback vertex set computation.
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
In graph theory modular decomposition is now a well-studied notion~\cite{Gal67,CHM81,MR84,ER90,EhrenfeuchtHR99}, as well as some of its generalisations~\cite{Cun73,HMC03,MontgolfierRaoICGT2005}.
As having been rediscovered in other fields, the notion also appears under various names, including intervals, externally related sets, autonomous sets, partitive sets, and clans.
Direct applications of modular decomposition include tractable constraint satisfaction problems,% vire par Fab~\cite{CohenCJ06}, % (on tournaments).
computational biology,% vire par Fab~\cite{GagneurKBC04}, % (on undirected graphs),
graph clustering for network analysis, and graph drawing.

Besides, in the area of social networks, several vertex partitioning have been introduced in order to catch the idea of putting in the same part vertices acknowledging similar behaviour, in other words finding regularities~\cite{WhiteR83}.
Modular decomposition  provides such a partitioning, yet seemingly too restrictive for real life applications.
The concept of a role~\cite{EverettB91} on the other hand seems promising, however its computation unfortunately is $NP-$hard~\cite{FP03}.
As a natural consequence, there is need for the search of \emph{relaxed}, but \emph{tractable}, variations of the modular decomposition scheme.
A step following this direction has generalised graph modules to those of larger combinatorial structures, so-called homogeneous relations~\cite{BuixuanHLdM06,wg06,odsa2006}.
This paper follows the same research stream, and weakens the definition of module in order to further decompose. 
Fortunately we obtain a new tractable variation of modular decomposition, that we now introduce.

Modular decomposition is based on \emph{modules}, a vertex subset with no \emph{splitter}. In graphs, a splitter of a vertex subset is linked with some, but not all, vertices of this subset. We shall see how this definition can be extended to homogeneous relations.
The ``outside'' of a module constitutes therefore, for all vertices of the module, the same ordered partition.
For instance, all vertices of an undirected graph module have the same neighbourhood.
We here address unordered-modules, so-called \textit{umodules} for short: the outside of a umodule constitutes for all vertices of the umodule the same unordered partition.
For graph, the umodules are the \emph{bijoins} (see Fig.~\ref{fig_mod_umod_1} and Section~\ref{sec_appli}).
As there are clearly more umodules than modules, this allows deeper decomposition.
We shall see that this decomposition is tractable.


%For undirected graphs, if $N$ is the ``outsider'' neighbourhood of a vertex of a umodule, then $N$ either is the outsider neighbourhood, or the outsider non-neighbourhood, of all vertices of the umodules.
%Then same holds if $N$ is the outsider non-neighbourhood of the first vertex (see Fig. ~\ref{fig_mod_umod_1}).
%A umodule thus can be seen as a vertex subset without \emph{interior splitters}: there are no two vertices inside the umodule that do not have the same unordered exterior partition.


After comparing umodule to previous notions in the topic, we display its tractability by giving an $O(|X|^4\log|X|)$ time computation of the maximal umodules of a given homogeneous relation over a finite set $X$, and show how this can also be used as a non-trivial umodule existence test.
The structure of the family of umodules is then investigated under different scenarios.
We focus on a particular case, and provide a potent tractability theorem which makes use of the so-called \emph{Seidel-switching} graph operation~\cite{Seidel76}.
Fortunately enough, undirected graphs and tournaments fit into the latter formalism.
We then deepen the study and address total decomposability issues, namely when any ``large enough'' sub-structure is decomposable.
Surprisingly enough, this shows how our theory provides a very natural manner to obtain several results on \emph{round tournaments}
, including characterisation, recognition, and isomorphism testing (see e.g.~\cite{BJG01} for more detailed information), as well as further computational results, such as the \emph{feedback vertex set} computation.
% 
% 
% 
% 
% 
% 
% 

% We show that compact (polynomial-size) representation of the family exists in the case of \emph{local congruence 2}.
%% Furthermore, if the input structure satisfies some local configuration axiom, so-called \emph{the four elements condition}, a decomposition scheme is provided, which generalises the``decomposition frame with the intersection and transitivity properties'' of Cunningham~\cite{Cun73}.
% 
%% Notice that Cunningham's theory has also been reconsidered under the formalism of ``bipartitive families'' \cite{M03} and ``unrooted set families'' \cite{HMC03}.
%% This has important structural consequences, both theoretical and algorithmic.
%% For instance in this case a compact tree representation of the umodule family with $|X|$ leaves is available.
%% This tree can be computed in $O(|X|^4\log|X|)$ time using the previous algorithm. 
%% Moreover, when the input structure also satisfies a second axiom, so-called \emph{the local congruence $2$ condition}, this computation can be quickened to be in $O(|X|^2)$ time.
% 
%% The  undirected graphs and the tournaments both satisfy the \emph{four elements} and also the \emph{local congruence $2$} conditions.
%% As a consequence, there umodules form a well structured family. The umodules of an undirected graph are the \emph{bijoins}, a recently introduced generalisation of modular decomposition~\cite{MontgolfierRaoICGT2005}.
%% The decomposition scheme for tournaments up to our knowledge is novel.
%% In both cases, a nice transformation can be made in order to reduce the umodular decomposition problem to a general modular decomposition problem (as studied in~\cite{BuixuanHLdM06,wg06,odsa2006}).
%% This transformation is inspired from the so-called \emph{Seidel-switch}, which is an important non-trivial transformation on graphs \cite{Seidel76}.
%% Following the transformation, we obtain linear time umodular graph and tournament decomposition algorithms.
% 
%% We deepen the study and address the total umodular decomposability of undirected graphs and of tournaments, namely when any ``large enough'' sub-structure is umodular decomposable.
%% Surprisingly enough, this results to strong structural relationship between the important graph class of cographs (see e.g.~\cite{BLS99}) and the tournament class of locally transitive tournaments, which also is known as round tournaments, a sub-class of locally semicomplete digraphs (refer to~\cite{BJG01} for more details).
%% %We then show how the \emph{Seidel-switching} allows to retrieve in a very natural way several results on round tournaments, including characterisation by forbidding induced subgraphs, recognition, isomorphism testing, and feedback vertex set computation.
%% We then show how our theory provides a very natural manner to obtain several results on round tournaments, including characterisation by forbidding induced subgraphs, recognition, isomorphism testing, and feedback vertex set computation.
% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Umodule, an enlarged notion of module}
Let $X$ be a finite set.
The family of all subsets of $X$ is denoted by $\mP(X)$.
A \emph{reflectless} triple is $(x,y,z)\subseteq X^3$ with $x\ne y$ and $x\ne z$, which will be denoted by $(x|yz)$ instead of $(x,y,z)$ since the first element plays a particular role.
Let $H$ be a boolean relation over the reflectless triples of $X$.
Then, $H_x$ denotes the binary relation on $X\setminus\{x\}$ such that $H_x(y,z)\Leftrightarrow H(x|yz)$.
\begin{definition}[Homogeneous Relation and Module]\label{def1}\cite{BuixuanHLdM06,wg06,odsa2006}
$H$ is a \emph{homogeneous relation on $X$} if, for all $x\in X$, $H_x$ is an equivalence relation on $X\setminus\{x\}$
%(i.e. it fulfils the symmetry, reflexivity and transitivity properties).
A subset $M\subseteq X$ is a \emph{module} of $H$ if $H(x|mm')$ for all $m,m' \in M$ and $x\in X\setminus M$.
\end{definition}

Equivalently, a homogeneous relation $H$ can be seen as a mapping from each $x\in X$ to a partition of $X\setminus\{x\}$, namely the equivalence classes of $H_x$.
This generalises graphs and \emph{2-structures}, where modular decomposition still applies under the different but equivalent name of \emph{clan decomposition}~\cite{EhrenfeuchtHR99,ER90}.
Roughly, a $2-$structure $G=(X,C)$ is a ground set $X$ and an edge colouration $C:X^2\rightarrow\mathbb{N}$ \cite{EhrenfeuchtHR99,ER90}.
Thus, a digraph is a $2-$structure using two colours, denoting the existing (when $C(x,y)=1$) and absent arcs (when $C(x,y)=0$).
There is no need of the concept of \emph{adjacency} nor \emph{neighbourhood} nor \emph{incidence} in a homogeneous relation!
But a homogeneous relation is canonically  derived from graphs and $2-$structures as follows.
\begin{definition}[Standard Homogeneous Relation]\label{def:standard}\cite{BuixuanHLdM06,wg06,odsa2006}
The \emph{standard homogeneous relation} $H(G)$ of a 2-structure $G=(X,C)$ is \hspace{2cm}
$H(G)(x|uv) \ \iff \ \  C(x,u)=C(x,v)\ \mathrm{and}\ C(u,x)=C(v,x).$


%digraph $G=(X,A)$ is defined such that, for all $x,u,v\in X$, $H(G)(x|uv)$ is true if and only if the two following conditions hold:\\
%1. either both $u$ and $v$ or none of them are in-neighbours of $x$, and\\
%2. either both $u$ and $v$ or none of them are out-neighbours of $x$.

%This also holds for undirected graphs, tournaments, oriented graphs, and can be extended to a $2-$structure $(G,C)$: $H(G)(x|uv)$ is true if and only if $C(x,u)=C(x,v)$ and $C(u,x)=C(v,x)$.

\end{definition}
\begin{proposition}\label{propo:standard}
Let $G$ be a graph, or a tournament, or an oriented graph, or a directed graph, or a $2-$structure.
The modules of  $H(G)$ exactly are the modules of $G$ in the usual sense (see definitions  in~\cite{Gal67,MR84,EhrenfeuchtHR99}).
\end{proposition}

We now introduce the central notion of this paper which, thanks to Proposition~\ref{prop_triviale} (below), can be seen at the same time as a proper generalisation of the classical modules/clans (in the sense of~\cite{Gal67,MR84,EhrenfeuchtHR99}), and a dual notion to the generalised modules (in the sense of~\cite{BuixuanHLdM06,wg06,odsa2006}).
\begin{definition}[Umodules]\label{def:umodul}
A subset $U$ of $X$ is a \emph{umodule} of $H$ if\\
\centerline{$\forall u,u' \in U, \ \ \forall x,x'\in X\setminus U, \ \ H(u|xx') \Longleftrightarrow H(u'|xx').$}
\end{definition}
% %
\begin{figure}[t]
\begin{center}
	\subfigure[Undirected graphs]{\includegraphics[scale=0.35]{ExempleUlmodPasModule}\label{fig_mod_umod_1}}
\hspace{1.5cm}
	\subfigure[Homogeneous relation]{\includegraphics[scale=0.9]{ModuleNotUmodule_bis}\label{fig_mod_umod_2}}
\caption{{\bf(a)} Modules and umodules in a graph: $\{a,b\}$ is a module and also a umodule, $\{1,2\}$ is a umodule but is not a module. {\bf(b)} A homogeneous relation with a module which is not a umodule.
$\{a,b\}$ is a module: they belong to the same equivalence class in both $H_c$ and $H_d$.
$\{a,b\}$ is not a umodule: $c$ and $d$ belong to the same class in $H_a$, and to different classes in $H_b$.}
\label{fig_mod_umod}
\end{center}
\vspace{-.5cm}
\end{figure}
%
Roughly, elements of a umodule come from the same ``school of thinking'':
%\TODO{celui qui a ecrit ca, il a fum\'e de la bonne !! --FM}
 if one element of a umodule differentiates, resp. mixes together, some exterior elements, so does every element of the umodule (Fig.~\ref{fig_mod_umod}).
A umodule $U$ is \emph{trivial} if $|U|\le 1$ or if $|U|\ge|X|-1$.
The family of umodules of $H$ is denoted by $\mU_H$, and $\mU$ when no confusion occurs.
$H$ is \emph{umodular prime} if all umodules of $H$ are trivial.
%If $\neg H(x|mm')$ we say that $x$ is a \emph{splitter} of $\{m,m'\}$.
%A module $M$ is \emph{trivial} if $|M|\le 1$ or $M=X$.
%The family of modules of $H$ is denoted by $\mM_H$, and $\mM$ when no confusion occurs.
%$H$ is \emph{modular prime}, or \emph{M-prime}, if $\mM_H$ is reduced to the trivial modules.
The following  proposition links umodules to the $1$-intersecting families framework as defined in~\cite{HM85}.
The subsequent one tells how far umodules may generalise modules.
\begin{proposition}\label{propu}
For any two umodules $U,U'$ of a homogeneous relation $H$, if $U\cap U'\ne\emptyset$ then $U\cup U'$ is also a umodule of $H$.
\end{proposition}
\begin{proposition}\label{prop_triviale}
If $H$ is a standard homogeneous relation (see Definition~\ref{def:standard}), then any module of $H$ is a umodule of $H$.
If $H$ is an arbitrary homogeneous relation over a finite set $X$, then any module $M$ of $H$ is such that $X\setminus M$ is a umodule of $H$.
\end{proposition}

In case of graphs, a natural question arises~\cite{DC07}: for which graphs the notions of module and umodule coincide?
The following result, which can also be seen as a relaxed converse of Proposition~\ref{prop_triviale}, solves this problem.
As with modules, let the umodules of a graph refer to those of its standard homogeneous relation.
Notice here in a graph that the complementary of a umodule also is a umodule.
A \emph{threshold graph} is one that can be constructed from the single vertex by repeated additions of a single isolated or dominating vertex.
%Equivalently, a threshold graph is a graph with no induced $P_4$, $C_4$, nor co-$C_4$, where $P_4$ denotes the four vertex path, $C_4$ the four vertex cycle, and co-$C_4$ the dual graph of $C_4$.
\begin{proposition}%[Characterisation of threshold graphs]
\label{prop_threshold}
$G$ is a threshold graph if and only if in all induced subgraph of $G$, every umodule is either a module or the complementary of a module (or both).
\end{proposition}

Threshold graphs are known to be one of the smallest graph classes (see e.g.~\cite{BLS99}).
Therefore for most graphs umodules and modules differ, and Section~\ref{sec_appli} is devoted to the umodular graph decomposition.
However, before deepening decomposition issues, let us first display umodule tractability.
% 
%Umodule tractability will be the concern of the upcoming section, with among others an $O(|X|^4\log|X|)$ time computation of the maximal umodules of a given homogeneous relation over a finite set $X$.
%
%In the remaining of the paper, we first propose a polynomial algorithm that computes the maximal umodules and a polynomial primality test.
%Then we focus on self-complemented families  and prove that they admit a unique decomposition tree.
%Finally we study homogeneous relations $H$ having at most 2 equivalence classes for each element. 
%A general correspondence between umodules of $H$  and modules of a Seidel switch  of $H$ is then provided.
%Applying these results to tournaments provides a new interesting combinatorial decomposition together with a linear time algorithm.
%When applied to undirected graphs, it yields the already known bi-join decomposition \cite{MontgolfierRaoICGT2005}. 
% 
% 
% 
% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Algorithmic Tractability for the general case}\label{sec_quotient}
As far as we are aware, %\TODO{quelle sont les limites de la conscience humaine ??}
 there is no evidence of a decomposition scheme for arbitrary umodules.
The first valuable objects to compute thus seem to be the maximal umodules with respect to some cut.
Using this, we also provide a polynomial time algorithm computing the \emph{strong} umodules (see definition afterwards).

\subsection{Maximal Umodules with respect to a cut}
Partitions will be ordered with respect to the usual partition lattice: $\mP=\{P_1,\dots,P_p\}$ is \emph{coarser} than $\mQ=\{Q_1,\dots,Q_q\}$, and $\mQ$ is \emph{thinner} than $\mP$, if every part $Q_i$ is contained in some $P_j$.
It is noted $\mQ\leq\mP$ and $\mQ<\mP$ if the partitions are different.
Let $S$ be a subset of $X$.
As the umodule family $\mU$ is closed under union of intersecting members (Proposition~\ref{propu}), the inclusionwise maximal umodules included in either $S$ or $X\setminus S$ form a partition of $X$, denoted by $MU(S)=MU(X\setminus S)$.
In other words, this is the coarsest partition of $X$ into umodules of $H$, which is thinner than $\{S, X\setminus S\}$.
Roughly, it gives an indication on how the umodules are structured with respect to $S$:
a umodule either is included in a umodule of $MU(S)$,
or properly intersects $S$,
or properly intersects $X\setminus S$,
or trivial.
\begin{definition}
Let $H$ be a homogeneous relation over $X$.
Let $C\subseteq X$.
The relation $R_C$ on $C$ is defined as:
\centerline{$ \forall x,y \in C,R_C(x,y) \ if \ \forall a,b \in (X\setminus C)  \ \  H(x|ab)  \Longleftrightarrow H(y|ab).$}
\end{definition}

This clearly is an equivalence relation on $C$.
Furthermore, $C$ is a umodule if and only if $R_C$ only has one equivalence class.
Let us define a \emph{refinement} operation, the main algorithmic tool for constructing $MU(S)$.
\begin{definition} 
Let $\mP$ be a partition of $X$ and $C$ a part of $\mP$. Let
$C_1,\ldots,C_k$ be the equivalence classes of $R_C$. $Refine(\mP,C)$ is the 
partition  obtained from  $\mP$, by replacing part $C$  by the  parts $C_1,\ldots,C_k$.
A partition $\mP$ is \emph{refinable} by $C$ if $Refine(\mP,C)\ne \mP$. 
$\mP$ is \emph{unrefinable} if for every part $C$ of $\mP$, we have $\mP=Refine(\mP,C)$.
\end{definition}
\begin{lemma}\label{lemf2}
Let $H$ be a homogeneous relation over $X$, $U$ a umodule of $H$, and $\mP$ a partition of $X$.
If $U$ is included in a part of $\mP$, then for any part $C$ of $\mP$, $U$ is included in a part of $Refine(\mP,C)$.
Moreover, a part $C$ of $\mP$ is a umodule if and only if $\mP$ is not refinable by $C$.
\end{lemma}

 
\begin{algorithm}[H]
\dontprintsemicolon
%\KwData{$S \subseteq X$} \;
%\KwResult{�$MU(S)$} \;
$\mP  \gets \{S,X\setminus S\}$ \;
\While{there exists an unmarked part $C$in $\mP$}{
	\lIf{$\mP=Refine(\mP,C)$}{
		mark $C$ \;
	}\lElse{
		$\mP\gets Refine(\mP,C)$ \;
	}
}
\caption{Refinement algorithm computing $MU(S)$ given homogeneous relation $H$ over $X$ and $S \subseteq X$}
\label{algo:Refinement}
\end{algorithm}

\bigskip

Correctness of Algorithm~\ref{algo:Refinement} follows from Lemma~\ref{lemf2} and the invariant: \textit{There is no umodule partition $\mQ$ such that $\mP < \mQ < \{S, X\setminus S\}$}.
So, starting from $\{S, X\setminus S\}$ the algorithm constructs a strictly decreasing chain of partitions of $X$ ending at $MU(S)$.
Let us see how to implement it efficiently.
%\TODO{j'ai vire la prop : inutile de prouver deux complexite dans un article de 10 pages, on garde la meilleure !}
%
%In this standard partition refinement algorithm, each part of the current partition may be \emph{marked}, which means ``processed''.
%When $\mP$ is replaced by $Refine(\mP,C)$, the marked parts of $Refine(\mP,C)$ are exactly the marked parts of $\mP$.
%
%% \begin{proposition}\label{thmu}
%% Given $S \subseteq X$, Algorithm 1 computes Partition $MU(S)$.
%% \end{proposition}
%% \begin{proof}
%% From the invariant: \textit{There is no umodule partition $\mQ$ such that $\mP < \mQ < \{S, X\setminus S\}$}, we deduce that, starting from $\{S, X\setminus S\}$ the algorithm constructs a strictly decreasing chain of partitions of $X$ ending at $MU(S)$.
%% % Let us examine the correctness of the algorithm. From first point of Lemma~\ref{lemf1}, if a part $C$ is marked, then $C$ is a 
%% % umodule. Consequently, when the algorithm terminates, $\mP$ is unrefinable. 
%% % In order to prove that $\mP$, when the algorithm terminates, is indeed 
%% % $MU(S)$, one can notice that lemma~\ref{lemf2} implies the following invariant:
%% % 
%% For time complexity, at each step of the ``while'' loop of the algorithm,
%%  either a part is marked (and will never be unmarked, or split),
%%  or a part is broken by $Refine$ into at least two new parts.
%%  As the number of part of $\mP$ is bounded by $|X|$, each of the events above 
%%  can happen at most $|X|$ time and the ``while'' loop runs $O(|X|)$ times. 
%%  According to Lemma~\ref{lemf2}, $Refine$ can be implemented in $O(|X|^2)$ 
%%  time. Using a stack or any other data structure, it is not hard to find an 
%%  unmarked part in constant time. As the ``while'' loop performs $O(1)$-time 
%%  computations plus one call to $Refine$, the overall algorithm complexity is 
%%  $O(|X|^3)$.
%% \end{proof}
\begin{lemma}\label{lemf3}
It is possible to compute  $Refine(\mP,C)$ in  $O(|X|^2)$ time. 
\end{lemma}
\begin{proof}
We first show how to test for $R_C(x,y)$.
Compute, for every element $x$ of $C$, a partition
$\mH(x,C)=\{P_x^1,\ldots,P_x^{k(x)}\}$ of $X\setminus C$. It is the
restriction of $H_x$ to $X\setminus C$, i.e $P_x^i=H_x^i \setminus C$. It
is easy to build in $O(|X|)$ time for each element of $C$.  Then we
have $R_C(x,y)$ if and only if $H(x,C)$ is exactly the same partition than
$H(y,C)$.  It can be tested in $O(|X|)$ time, but performing this for
each couple of elements of $C$ would lead to an $O(|X|^3)$ time
implementation of $Refine(\mP,C)$.
Let us instead consider  $\mH(x,C)$ as a $b$ bit vectors (with $b=|X\setminus
C|=O(|X|)$).  Looking for duplicates among these vectors can be
performed easily, by bucket sorting them on their first bit, then the
second, and so on. A scan of all vectors (i.e. of all elements of $C$)
compute the pairwise equal vectors, i.e the $R_C$ equivalent elements
of $C$. It is then easy to split $C$ and to update $\mP$, in  $O(|X|^2)$ time.
\qed
\end{proof}

The lemma above leads to an  $O(|X|^3)$ time implementation of Algorithm~\ref{algo:Refinement}. However,
\begin{theorem}\label{ThMU} 
For every $S \subseteq X$, $MU(S)$, the coarsest umodule partition  thinner than $\{S, X-S\}$  can be computed  in $O(|X|^2 \log|X|)$ time.
\end{theorem}
\begin{proof}
Using the well-known  Hopcroft's partition refinement rule it is possible to improve the above algorithm. The idea is to avoid at each step to consider the biggest part, see \cite{MR917035}.
Thus, to compute $MU(S)$ assuming that $|S| \leq |X-S|$, we first partition $X-A$ using the "neighbourhoods lists" of  all $a \in A$. If we assume a data structure which links each edge $ay$ to its opposite edge $ya$.
We can associate in the meantime to each element $a \in A$ a bitvector representing how $X-A$ sees $a$. These $|A|$ bitvectors of size $|X-A|$ can be sorted in $O(|X|.|X-A|) \in O(|X|^2)$.
Using Hopcroft's rule, a vertex $a$ can only be explored at most $O(\log|X|)$ time, which yields the announced complexity.
\qed
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Bin's post it                      %
% dire aussi comment calculer les max en temps n4log n %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Strong Umodules: Maximal Umodules Computation and Primality Test}
A umodule is \emph{strong} if it overlap no other umodules, where two subsets overlap if none of the intersection and differences are empty.
%\TODO{what is overlapping ?}
As two strong umodules are either disjoint, or one contains another, they can be ordered by inclusion into a tree (see e.g. laminar families in~\cite{Schrijver03}). 
\begin{theorem}\label{thprim}
There exists an $O(|X|^4 \log|X|)$ algorithm to compute the inclusion tree of strong umodules.
\end{theorem}
\begin{proof}
Consider a non-trivial strong umodule $M$. For each pairwise distinct
$x,y\notin M$ (at least two of them exists since $M$ is not trivial),
$M$ is contained in exactly one set of $MU(\{x,y\})$. The intersection
of all these sets is exactly $M$. Indeed if it where $M'$ such that
$M\subsetneq M'$ then there would exist $x\in M'\setminus M$. For $y
\notin M$, $MU(\{x,y\})$ contains a umodule $M''$ smaller than $M'$
but containing $M$, a contradiction.
Then the algorithm is as follow. For every pair $\{x,y\}$ compute
$MU(\{x,y\})$ in $O(|X|^2 \log|X|)$ time (Theorem~\ref{ThMU}). That
gives a family of at most $|X|^3$ umodules. Add the trivial modules to
the family.  Greedily compute the intersection of overlapping
umodules of the family. It is possible in $O(|X|^4 \log|X|)$ time:
for each triple $(a,b,c)$ look for the umodules containing exactly two
of them, they overlap.  Then we have all strong umodules. We finally
just have to order them into a tree.
\end{proof}

This answers both maximal umodule computation and primality test since a non-trivial umodule exists if and only if a non-trivial strong umodule exists.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Two Decomposition Scenarios}
Of course, the number of umodules may be as large as $2^{|X|}$. But we
shall now focus on certain umodule families having a compact
(polynomial-size) representation. Umodules of local congruence 2
relations, on the first hand, and self-complemented umodules families,
on the second hand, have such properties. They can be stored in
$O(|X|^2)$ and $O(|X|)$ space, respectively.

\subsection{Local Congruence and Crossing Families}\label{sectlc2} 
\begin{definition}[Local congruence]
Let $H$ be a homogeneous relation on $X$. For $x\in X$, the
\emph{congruence} of $x$ is the maximal number of elements that $x$
pairwise distinguishes.  In other words, it is the number of
equivalence classes of $H_x$. The \emph{local congruence} of $H$ is
the maximum congruence of the elements of $X$.
\end{definition}
\begin{Rq}
The standard homogeneous relation of an undirected graph  or a tournament has local congruence 2.
This value is 3 for an antisymmetric directed graph or a directed acyclic graph.
The value is 4 for digraphs.
\end{Rq}

When the local congruence of $H$ is $2$, so-call \emph{LC2 condition} for short, we obtain the following structural property on its umodule family.
%% Arbre de taille n^2 (pour le moment)
\begin{definition}[Crossing family]
$\mathcal{F}\subseteq2^X$ is a crossing family if, for any $A, B \in \mathcal{F}$, that $A \cap B \neq \emptyset$ and $A \cup B \neq X$
implies $A�\cap B \in \mathcal{F}$ and $A�\cup B \in \mathcal{F}$ (see e.g.~\cite{Schrijver03} for further details).
\end{definition}

Crossing families commonly arise as the minimisers of a submodular function.
For instance, the minimum $s,t-$cuts of a network form a crossing family.
Gabow proved that a crossing  family admits a compact representation in $O(|X|^2)$ space using a tree representation~\cite{Gabow93}.
%
\begin{proposition}
The umodules of a homogeneous relation with local congruence $2$ form a crossing family, and can thus be stored in  $O(|X|^2)$ space.
\end{proposition}
%
% \begin{proof}
% Without any assumption on the relation, the union of two overlapping umodules is
% also a umodule. Now let us consider two overlapping sets $A, B \in�\mathcal{F}$, with 
% $A \cap B \neq \emptyset$ and $A \cup B \neq X$, by hypothesis $A \setminus B$ and 
% $B \setminus A$ are non-empty, $a \in A\setminus B$ and $b \in B \setminus B$. Moreover
% to be relevant $A \cap B$ must contain at least two elements otherwise 
% the intersection is obviously a umodules. So $y,z \in A \cap B$. And finally 
% $x \in X \setminus A\cup B$. By hypothesis we have $H(a|xb) \Leftrightarrow H(y|xb) \Leftrightarrow H(z|xb)$ 
% and $H(b|xa)\Leftrightarrow H(y|xa) \Leftrightarrow H(z|xa)$ and as there are only two possible classes 
% we have $H(y|ab) \Leftrightarrow H(z|ab)$.
% \end{proof}

%%%%%%%%%%%%%%%%%
% Bin's post it %
% developper    %
%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Self-complementarity and Bipartitive Families}\label{sec_self}
A consequence of previous proposition is that  standard homogeneous relations of graphs and tournaments have crossing umodules families.
But they have stronger properties, which we will use to show a linear-space structure coding the umodule family.
\begin{definition}[Four elements condition]\label{four}
$H$ fulfils the \emph{four elements
  condition} if \vspace{-.3cm}
\begin{eqnarray*}
\forall~m,m',x,x'\in X,~~
\left\{\begin{array}{l}
H(m|xx')\wedge  H(m'|xx')\wedge   H(x|mm') \Rightarrow H(x'|mm') \\
\neg H(m|xx') \wedge  \neg H(m'|xx')\wedge \neg H(x|mm') \Rightarrow \neg H(x'|mm')
\end{array}\right..
\end{eqnarray*}
%
\end{definition}
\begin{proposition}\label{prop_stand_4EC}
Standard homogeneous relations of undirected graphs and tournaments satisfy the four elements condition.
\end{proposition}

This is a light regularity condition, allowing to avoid examples similar to that of Fig.~\ref{fig_mod_umod_2}.
Surprisingly enough, it suffices to make the umodule family behave in a very tractable manner (Proposition~\ref{propo_4_self} and Corollary~\ref{coro_SC} below).
\begin{definition}[Self-complementary condition]
A family $\mF$ of subsets of $X$ is \emph{self-complemented} if for every subset $A$, $A\in\mF$ implies $X\setminus A\in\mF$.
\end{definition}
\begin{proposition}\label{propo_4_self}
If a homogeneous relation $H$ fulfils the four elements condition then the family $\mU$ of umodules of $H$ is self-complemented. 
\end{proposition}
% \begin{proof}
% Let us assume that $U$ is a umodule and $X \setminus U$ is not, i.e. there are two elements $x$ and $x'$ of $X\setminus U$, and two elements $m$ and $m'$ of $X$ such that $H(x|mm')$ but $\neg H(x'|mm')$.
% As $U$ is a umodule, either both $m$ and $m'$ distinguish
% $x$ from $x'$ (i.e.  $\neg H(m|xx')$ and $\neg H(m'|xx')$) or none of
% $m$ and $m'$ distinguish $x$ from $x'$ (i.e.  $H(m|xx')$ and $H(m'|xx')$). The first case is forbidden by the first implication of the four elements condition,
% and the second case is forbidden by the second implication.  \qed
% \end{proof}

The \emph{four elements condition} is quite convenient since it allows to shrink a umodule, hence apply the divide and conquer paradigm to solve optimisation problems.
%\emph{ Such techniques will be used in section 7 to solve the minimum feedback set problem on decomposable tournaments. (\`a enlever ?)}
However, as far as umodules are concerned, the \emph{self-complementary} relaxation is sufficient to describe a tree-decomposition theorem as can be seen in the following section.
Finally, notice that the converse of Proposition~\ref{propo_4_self} does not necessarily hold.
The characterisation of relations having a self-complemented umodule
family by a local axiom, such as the four elements condition, actually
appears to be more difficult.

\subsubsection{Tree Decomposition Theorem}
The following results on bipartitions can be found in \cite{Cun73} under the name of ``decomposition frame with the intersection and transitivity properties'',
in \cite{M03} under the name of ``bipartitive families'' (the formalism used in this paper),
and in \cite{HMC03} under the name of ``unrooted set families''.

We call $\{X_i^1,X_i^2\}$ a \emph{bipartition} of $X$ if $X_i^1\cup X_i^2=X$ and $X_i^1\cap X_i^2=\emptyset$.
Two bipartitions $\{X_i^1,X_i^2\}$ and $\{X_j^1,X_j^2\}$ \emph{overlap} if for all $a,b=1,2$ the four intersections $X_i^a\cap X_j^b$ are not empty.
A bipartition is \emph{trivial} if one of the two parts is of size $1$.
Let $\mB=\{\{X_i^1,X_i^2\}_{i\in 1,\ldots,k}\}$ be a family of $k$ bipartitions of $X$.
The \emph{strong} bipartitions of $\mB$ are those that do not overlap any other bipartition of $\mB$.
For instance, the trivial bipartitions of $\mB$ are strong bipartitions of $\mB$.
\begin{proposition}
If $\mB$ contains all trivial bipartitions of $X$, then there exists a unique tree $T(\mB)$ \vspace{-.3cm}
\begin{itemize}
\item with $|X|$ leaves, each leaf being labelled by an element of $X$.
\item such that each edge $e$ of  $T(\mB)$ correspond to a strong bipartition 
of $\mB$: the leaf labels of the two connected components of $T-e$ are exactly 
the two parts of a strong bipartition, and the converse also holds.
\end{itemize}
\end{proposition}

Let $N$ be a node of  $T(\mB)$ of degree $k$.
The labels of the leaves of the connected components of $T-N$ form a partition 
$X_1,\ldots,X_k$ of $X$. For $I\subseteq\{1,\ldots,k\}$ with $1<|I|<k$, the 
bipartition $B(I)$ is $\{\cup_{i\in I} X_i, X\setminus \cup_{i\in I}X_i\}$. \vspace{-.4cm}
\begin{definition}[Bipartitive Family]
A family of bipartitions is a \emph{bipartitive family} if it contains
all the trivial bipartitions and if, for two overlapping bipartitions
$\{X_i^1,X_i^2\}$ and $\{X_j^1,X_j^2\}$, the four bipartitions
$\{X_i^a\cup X_j^b, X\setminus (X_i^a\cup X_j^b)\}$ (for all
$a,b=1,2$) belong to $\mB$.
\end{definition}
\begin{theorem}\label{thbip}\cite{M03}
If $\mB$ is a bipartitive family, the nodes of $T(\mB)$ can be labelled \emph{complete}, \emph{circular}
or \emph{prime}, and the children of the \emph{circular} nodes can be ordered in such a way that: \vspace{-.3cm}
\begin{itemize}
\item If $N$ is a complete node, for any $I\subseteq \{1,\ldots,k\}$ such that   $1<|I|<k$, $B(I)\in\mB$.
\item If $N$ is a circular node, for any interval $I=[a,\ldots,b]$ of $\{1,\ldots,k\}$ such that   $1<|b-a|<k$,  $B(I)\in\mB$.
\item If $N$ is a prime node, for any element $I=\{a\}$ of $\{1,\ldots,k\}$ $B(I)\in\mB$.
\item There are no more bipartitions in $\mB$ than the ones described above.
\end{itemize}
\end{theorem}

For a bipartitive family $\mB$, the labelled tree $T(\mB)$ is an $O(|X|)$-sized representation of $\mB$, while the family can have up to $2^{|X|-1}-1$ bipartitions of $|X|$ elements each.
This allows to efficiently perform algorithmic operations on $\mB$.
Notice that any self-complemented subset family can be seen as a family of bipartitions.
% vire par Fabien : lourd
%The self-complemented umodule families fit in this formalism.
%Indeed if we define the \emph{bipartition closure} of the umodule family of $H$ as $\mU'(H)=\{\{U,X\setminus U\} \ | \ U$ is a umodule of $H\}$, then
\begin{proposition}\label{theorem_SC}
The members of a self-complemented umodule family form a bipartitive family.
\end{proposition}
% \begin{proof}
% As $\mU'(H)$ is  self-complemented each part of a bipartition belonging to $\mU'(H)$ is a umodule. Furthermore if the bipartitions $\{U,X\setminus U\}$ and $\{V,X\setminus V\}$ overlap (in the bipartition sense) then $U$ and $V$ overlap (in the set sense). According to Proposition~\ref{propu} if  $U$ and $V$ overlap $U\cup V$ is a umodule, and therefore $\{U\cup V, X\setminus (U\cup V)\in \mU'(H)\}$. The self-complementary condition gives the results  needed for the three other bipartitions.
% \qed
% \end{proof}
\begin{corollary}[Umodular Decomposition Theorem]\label{coro_SC}
There is a unique $O(|X|)$-sized tree that gives a description of all possible umodules of a homogeneous relation $H$ fulfilling the self-complementary condition.
This tree is henceforth
called \emph{umodular decomposition tree}. Notice that it is an unrooted
tree, unlike the modular decomposition tree.
\end{corollary}
% 
%Instead of a collection of subsets of $X$, we have to consider a self-complemented family as collection of bipartitions.
% vire par Fabien : ne pas dire que c'est lineaire juste avant un algo en n^4 log n !!
%The computation of this tree can be done in polynomial time using results of Section~\ref{sec_quotient} as we are to describe next.
%However, it would be nice to find more efficient algorithms.
% 
\subsubsection{Tree Decomposition Algorithm}
Let $H$ be a self-complemented homogeneous relation, $T(H)$ its umodular decomposition tree, and $U$ a nontrivial strong umodule (if any).
Let us examine some consequences of Theorem~\ref{thbip}. Notice
that two umodules overlap if and only if they are incident to the same node of
$T(H)$.  As $H$ is self-complemented the union of two overlapping
umodules is a umodule (Proposition~\ref{propu}) but also their
intersection.  The strong umodule $U$ is an edge in $T(H)$ incident
with two nodes $A$ and $B$. \vspace{-.3cm}
\begin{itemize}
\item If one of them,
say $A$, is labelled prime then for any $x,y\notin U$ such that the
least common ancestor of them in $T(H)$ is $A$, then $U\in
MU(\{x,y\})$.
\item If one of them, say $A$, is labelled circular then for any $x$ belonging 
to the subtree rooted in the successor of $U$ in the ordered circular list of 
$A$, and for any  $y$ belonging to the subtree rooted in the predecessor of 
$U$, then $U\in MU(\{x,y\})$.
\item  If one of them, say $A$, is labelled complete then the intersection, 
for all $x,y\notin U$ whose least common ancestor is $A$, the intersection of 
all parts of  $MU(\{x,y\})$ containing $U$ is exactly $U$.
\end{itemize}

Theorem~\ref{thprim} then can be used to compute the strong umodule inclusion tree.
After this, typing the nodes and ordering their sons according to the above definition is straightforward.
Hence,
\begin{theorem}
There exists an $O(|X|^4 \log(|X|))$ algorithm to compute the unique decomposition tree 
for a self complemented umodule family.
\end{theorem}
%\begin{proof}
%\end{proof}
% 
\section{Seidel-switching Theorem, a potent Tractability}
Standard homogeneous relations of graphs and tournaments are of local congruence 2, and their umodule families are self-complemented.
Firstly this means we can either decompose those families using the crossing families decomposition or using the bipartitive decomposition.
Moreover, relations that satisfy both the self-complementary and \emph{LC2} properties seem to own stronger potential.
In particular, let us show a nice local transformation from the umodules of such a relation  to the modules of another relation.
This operation was first introduced in J. Seidel in \cite{Seidel76} on undirected graphs.
It was later studied by several authors interested in some computational aspects \cite{ColbournC80,KratochvilNZ92} and structural properties 
\cite{Hayward96,Hertz99} and recently in \cite{MontgolfierRaoICGT2005}.
The operation is referred to as \emph{Seidel switch} in \cite{Hertz99}, and we will adopt this terminology.
We generalise it to homogeneous relations but take a restricted case of switch, with the slight difference  
that we remove from the transformation an element (see Fig.~\ref{fig:SeidelSwitchExemple}).
% virer par Fabien : trop long et pas assez de trucs dedans
%% Roughly speaking, for an undirected graph $G=(V,E)$, and 
%% $W \subseteq V$,  the Seidel switch on $G,W$ 
%% is obtained by  taking the complement of the edges between $G_{[W]}$ and $G_{[V\setminus W]}$ 
%% (but it should be noticed that $G_{[W]}$ and $G_{[V\setminus W]}$ remain unchanged).
%% Actually we only use a particular case of this powerful operation, when 
%% applied to homogeneous relation, we identify the set $W$ as one of the part of 
%% an element $x \in X$. For instance, on graphs the set $W$ will be chosen as 
%% the neighbourhood of vertex. Moreover there is also a slight difference with 
%% the original operation, that is we remove from the transformation the element 
%% $w$ such that $H_w^i = W$ (see Fig.~\ref{fig:SeidelSwitchExemple}).
%% % The Seidel switch at a given vertex $x$ was defined in \cite{Seidel76} for graphs as
%% % exchanging (or complementing) edges and non-edges between the neighbourhood of $x$ and
%% % its non-neighbourhood. This can be extended to local congruence 2
%% % homogeneous relations.
For convenience, if $H$ is a homogeneous relation on $X$ and $s\in X$,
we also refer to the equivalence classes of $H_s$ as $H_s^1,\dots,H_s^k$.
%
\begin{definition}[Seidel switch]
\label{def:SeidelSwitch}
Let $H$ be a homogeneous relation of local congruence $2$ on $X$,
and $s$ an element of $X$.
The \emph{Seidel switch} at $s$ transforms $H$ into the homogeneous relation $H(s)$ on $X\setminus\{s\}$ defined as follows.
$$\forall x\in X\setminus\{s\}, H(s)^1_x=(H_x^1\Delta H_s^j)\setminus\{s\} \ and \  H(s)^2_x=(H_x^2\Delta H_s^j)\setminus\{s\}$$
with $j$ such that $x \notin H_{s}^{j}$. 
where $A\Delta B$ denotes the symmetric difference of $A$ and $B$.
\end{definition}
%
% \begin{figure}
% 	\begin{center}
% 		\includegraphics[scale=1]{PointedSeidelSwitch}
% 		\caption{An example of a Seidel switch on an undirected graph}
% 		\label{fig:SeidelSwitchExemple}
% 	\end{center}
% \end{figure}
%
\begin{figure}[h]
	\begin{center}
		\subfigure[An example of a Seidel switch on an undirected graph]{\includegraphics[scale=.7]{PointedSeidelSwitch} \label{fig:SeidelSwitchExemple}}
\hspace{0.5cm}
		\subfigure[1. A bi-join (i.e. umodule) in an undirected graph, 2. a umodule in a tournament]{\includegraphics[scale=.7]{BijoinGraphandTournament} \label{figbij}}
\vspace{-0.3cm}
		\caption{(a) Seidel switching, (b) umodules on undirected graphs}
	\end{center}
\end{figure}
%
\begin{theorem}[Seidel-switching Theorem]\label{thmain}
Let $H$ be a homogeneous relation of local congruence $2$ on $X$ such that $\mU_H$ is self-complemented.
Let $s$ be a member of $X$, and $U\subseteq X$ a subset containing $s$.
Then, $U$ is a umodule of $H$ if and only if $M=X\setminus U$ is a module of the Seidel switch $H(s)$.
\end{theorem}
% \begin{proof}
% Let $C=H_s^1\cap M$ and $D=H_s^2\cap M$.
% Since $H$ is of local congruence $2$, $\{C,D\}$ is a partition of $M$.
% Let $a\in U\setminus\{s\}$.
% Suppose that $U$ is a umodule of $H$.
% Then, for all $y,z\notin U$, $H(a|yz)$ if and only if $H(s|yz)$.
% In other words, $C$ is included in one class among $H_a^1$ and $H_a^2$ while $D$ is included in the other class.
% As $C\subseteq H_s^1$ and $D\cap H_s^1=\emptyset$, $C\cup D$ is included in one among the two classes $H(s)_a^i=H_a^i\Delta H_s^{j}$ ($i\in\{1,2\}$ and $j$ as in Definition \ref{def:SeidelSwitch}).
% Hence, $M=C\cup D$ is a module of $H(s)$.
% 
% Conversely, if $M$ is a module of $H(s)$, then $C\cup D$ is included in either $H(s)_a^1$ or $H(s)_a^2$.
% Moreover, the definition of the Seidel switch can also be written as $H_a^i=H(s)_a^i\Delta H_s^j$ for $i\in\{1,2\}$
% and $j$ as in Definition \ref{def:SeidelSwitch}.
% Therefore, $C$ is included in one class among $H_a^1$ and $H_a^2$ while $D$ is included in the other class.
% In other words, for all $a\in U\setminus\{s\}$, and $y,z\notin U$, $H(a|yz)$ if and only if $H(s|yz)$.
% This implies for all $a,b\in U$, and $y,z\notin U$, $H(a|yz)$ if and only if $H(b|yz)$ and $U$ is therefore a umodule.
% \qed
% \end{proof}

% Tout ca zigouilled par Fabien
%% Modular decomposition trees have well-known properties
%% \cite{CHM81,MR84}. They are rooted trees whose leaves are in
%% one-to-one correspondence with elements of $X$. A node of the modular
%% decomposition tree is exactly a strong module, a module that overlap
%% (in the set sense) no other modules. 
%% For a node $N$ let $F_1,\ldots,F_k$ be
%% the leaf-sets of its $k$ children in the tree. When the family of umodules of $H$
%% is bipartitive as it is the case in Theorem~\ref{thmain}, the family of modules of any Seidel switch of $H$ is a partitive set family
%% \cite{CHM81}, also known as \emph{rooted set family} \cite{HMC03}. The following theorem from \cite{CHM81} describes the structure of partitive set families.
%% %
%% \begin{theorem}~\cite{CHM81}
%% The nodes of a modular decomposition tree $T$ can be labelled
%% \emph{complete}, \emph{linear} or \emph{prime}, and the children of the \emph{linear} nodes can be ordered in such a way that:
%% \begin{itemize}
%% \item If $N$ is a complete node, for any $I\subset \{1,\ldots,k\}$ such that   $1<|I|<k$, $\bigcup_{i\in I} F_i$ is a module.
%% \item If $N$ is a linear node, for any interval $I=[a,\ldots,b]$ of $\{1,\ldots,k\}$ such that   $1<|b-a|<k$, $\bigcup_{i\in I} F_i$ is a module.
%% \item If $N$ is a prime node, for any element $I=\{a\}$ of $\{1,\ldots,k\}$ $\bigcup_{i\in I} F_i$ is a module.
%% \item There are no more modules than the ones described above.
%% \end{itemize}
%% \end{theorem}

%% The relationships between the umodular decomposition tree of $H$ and the modular decomposition tree of $H(v)$ are very tight:
%% %
%% \begin{proposition}\label{superprop}
%% Let $H$ be a homogeneous relation of local congruence $2$ on $X$ such that $\mU_H$ is self-complemented.
%% Let $s$ be an element of $X$.
%% The umodular decomposition tree $\mT_H$ of $H$ and
%% the modular decomposition tree $\mT_H(s)$ of the Seidel switch $H(s)$
%% of $H$ at $s$ have the following properties:
%% \begin{itemize}
%% \item the two trees are exactly the same (same nodes and edges)
%% excepted that the leaf with label $s$ is missing in
%% $\mT_H(s)$ but present in $\mT_H$.
%% \item The node of $\mT_H$ that is adjacent to the leaf $s$ corresponds to the
%% root of $\mT_H(s)$ (while $\mT_H$ is unrooted).
%% \item A circular node of $\mT_U$ corresponds to a linear node of
%% $\mT_M(s)$. The orderings of the children are the same. The prime and complete nodes are the same in both trees.
%% \end{itemize}
%% \end{proposition}

% \begin{proof}
% This is a consequence of Theorem~\ref{thmain}. Every strong module of
% $H(s)$ gives a strong bipartition of $\mT_H$, and the converse is
% true. Then for a node $N$ of the modular decomposition tree, for any
% union $\bigcup_{i\in I} F_i$ of leaf-sets of children there is a
% bipartition $\{\bigcup_{i\in I} F_i,X\setminus (\bigcup_{i\in I}
% F_i)=B(I)$ using the notations defined above. For each bipartition of
% umodules of $H$, the part that contain $s$ is dropped and the other part
% is put is the family of modules of $H(s)$. \qed
% \end{proof}
%

%% A similar result (with more details)
%% can be found in \cite{HMC03}. That article indeed describes the
%% relationship between the consecutive-ones ordering and the
%% circular-ones ordering of a boolean matrix, but the results (described
%% in \cite{HMC03} as the transformation of a PQ-tree into a PC-tree) are
%% the same.
\begin{corollary}\label{corX}
The umodular decomposition tree of a self-complemented homogeneous relation of local congruence $2$ on $X$ can be computed in $O(|X|^2)$ time.
\end{corollary}
\begin{proof}
Using a Seidel switch on any element will result in a relation having the so-called \emph{modular quotient} property~\cite{BuixuanHLdM06}: every module of the relation also is a umodule.
Then, the $O(|X|^2)$-time modular decomposition algorithm for modular quotient relations depicted in~\cite{BuixuanHLdM06}. As two complemented strong umodules $M, X\setminus M$ of $H$, for $s\notin M$, correspond to a strong module $M$ of $H(s)$, then 
the strong umodules of $H$ can be found trivially from the strong modules of $H(s)$. Typing and ordering their sons is then easy. 
\end{proof}

Notice that the modular
 decomposition tree of $H$ can be trivial, 
while the one of its Seidel switch at $s$ may be not.
Besides, there is no real need to type and order the sons of a node, as
so-called \emph{linear} nodes of the modular decomposition tree give
circular nodes of the umodular decomposition tree with the same
ordering of their sons, complete nodes of $H(s)$ give complete nodes
of $H$ and prime nodes of $H(s)$ give prime nodes of $H$. The
correspondence is straightforward but modular decomposition of
homogeneous relations will not be discussed here, the reader should
refer to~\cite{BuixuanHLdM06}.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Umodular Decomposition of Graphs and Tournaments}\label{sec_appli}
Let us now apply umodular decomposition to two well-known
combinatorial objects: undirected graphs and tournaments. In this
section we always implicitly refer to their standard homogeneous
relations, for instance ``the umodules of the graph $G$'' stands for
``the umodules of the standard homogeneous relation $H(G)$ of the graph
$G$'' and so on. And ``graph'' stands for ``undirected graph''. As we
have seen, graphs and tournaments fulfil the four elements
conditions, are of local congruence two, and their umodule family is
self-complemented. 


\subsection{Bijoin decomposition}
Let us call \emph{bijoin} a umodule of a graph or of a tournament.
From definition, one can see what bijoins are (Fig.\ref{figbij}).
In a graph, $B$ is a bijoin if $X\setminus B$ can be partitioned in two sets $C$ and $D$ such that for each $x\in B$, either $N(x)\cap C = \emptyset$ and $D\subseteq N(x)$, or  $N(x)\cap D = \emptyset$ and $C\subseteq N(x)$.
For a tournament, same definition with  $C\subseteq N^+(x)$ and  $D\subseteq N^-(x)$, or  $D\subseteq N^+(x)$ and  $C\subseteq N^-(x)$.


Bijoins of graphs where studied in \cite{MontgolfierRaoICGT2005}
as a new graph decomposition, generalising modular decomposition.  The
Seidel switch was used to derive most of the properties claimed,
especially a decomposition tree (with no \emph{circular} nodes), a
linear-time decomposition algorithm, a characterisation of the two
kinds of \emph{complete} nodes, and characterisation of \emph{totally
decomposable} graphs (see below).

Bijoins of tournaments form a new decomposition. The first important property is:
\begin{proposition}
The umodular (bijoin) decomposition tree computation time of a tournament is $O(|X|^2)$.
\end{proposition}

The tree exists thanks to Corollary~\ref{coro_SC}, since the bijoins form a self-complemented $LC2$ family. The computation algorithm is from  Corollary~\ref{corX}.
 \begin{proposition}
 The umodular (bijoin) decomposition tree of a tournament has no \emph{complete node}. And there exists a circular ordering of the vertices of the tournament
 such that every umodule of the tournament is a factor (interval) of this
 circular ordering.
 \end{proposition}

The first assumption can be checked by reader: it is impossible to
build tournaments with more than four elements such that every vertex
subset is a bijoin. The second is a consequence of the first, and of
definitions in Theorem~\ref{thbip}.  As a consequence, there are
$O(|X|^2)$ bijoins in a tournament (the exponential growth of a
bipartitive family comes from \emph{complete} nodes).

% Among the consequences exposed in  \cite{MontgolfierRaoICGT2005}, bi-join (thus umodular) decomposition trees have no \emph{circular} nodes.
% \begin{theorem}\label{th:BijoinuniqueTreeDecomposition}
% There is a unique unrooted decomposition tree $T$ associated to an undirected graph $G$.
% All the nodes are labelled degenerate or prime. There is exactly two kind of degenerate
% nodes: The clique nodes $K_n$ and the complete bipartite node $K_{n,m}$.

\subsection{Total Decomposability}
Given a graph decomposition scheme, is often worth to consider the totally decomposable graphs with respect to that scheme, namely the graphs in which every "large enough" subgraph admits a non trivial decomposition.
In general this leads to the definition of very interesting class of graphs, such as cographs with modular decomposition or distance hereditary graphs with split decomposition.
Let us now see how the graphs and tournaments totally decomposable with respect to bijoin decomposition behave.

\begin{theorem}\cite{MontgolfierRaoICGT2005}
The totally decomposable graph with respect to bijoin decomposition are the ($C_5$,bull,gem,co-gem)-free
graphs, and also exactly the graphs that can be obtained from a single
vertex by a sequence of (twin,antitwin)-extensions.
\end{theorem}

\begin{definition}
A \emph{diamond} is one of the induced 
subgraph described in Figure~\ref{fig:PrimeConfTour}.
A tournament $T$ is \emph{locally transitive}
if
for each vertex $x \in V(T)$, $T_{[N^{+}{(x)}]}$ and $T_{[N^{-}{(x)}]}$ are transitive 
 tournaments.
Two vertices $x$ and $y$ of a tournaments are \emph{twins} if $N^+(x)\setminus\{y\} = N^+(y)\setminus\{x\}$ and \emph{antitwins} if $N^+(x)\setminus\{y\} = N^-(y)\setminus\{x\}$.
An \emph{extension} of a vertex $x$ of $T$ by a twin (resp. antitwin) $y$ consists in adding a new vertex $y$ to $T$ and making $y$ twin (resp. antitwin) of $x$.
 \end{definition}

\begin{theorem}
Let $T$ be a tournament. The following propositions are equivalent:
\begin{enumerate}
\item $T$ is diamond-free (no induced subgraph is a diamond)
\item $T$ is locally transitive
\item  $T$ is totally decomposable with respect to bijoin decomposition
\item $T$ can be obtained from a  single
vertex by a sequence of (twin,antitwin)-extensions.
\end{enumerate}
\end{theorem}
\begin{proof}
%\TODO{non Fab, dans le teaser de l'intro on a dit qu'on donne une preuve simple de l'equiv 1 et 2} Niet ! --Fab
As the in- and out-diamond are prime with respect to umodular decomposition, and total decomposability is an hereditary property, Point 3 implies Point 1. 
Let us sketch the proof that Point 2 implies Point 3. If $T$ is locally transitive then a Seidel switch of $T$ at any vertex $s$ produces a transitive tournament $T(s)$. Every subgraph of a transitive tournament contains a module. So, according to Theorem~\ref{thmain}, every subgraph of $T$ contains a umodule: $T$ is totally decomposable.
Besides, the equivalence between Point 3 and Point 4 comes from the fact that, if $T$ is totally decomposable, then it contains a umodule of two vertices. Such umodules are made either with two twins or with two antitwins.
Equivalence between 1 and 2 can be found in \cite{BJG01}.
\end{proof}
% 
% 
% 
% 
 \begin{figure}[h!]
 	\begin{center}
 		\includegraphics[scale=.55]{PrimeTournamentsA}
 		\hspace{2cm}
 		\includegraphics[scale=.55]{PrimeTournamentsB}
 	\end{center}
 	\caption{ Forbidden 
 subgraphs of a totally decomposable tournament with respect to umodular decomposition: the in-diamond(left) and the out-diamond(right). }
 \label{fig:PrimeConfTour}
 \end{figure}

It is not hard to check that, as the umodular decomposition tree of a totally decomposable tournament may have no \emph{prime} node, and since two \emph{circular} node may not be adjacent, then the umodular decomposition tree  of a totally decomposable tournament has only a single \emph{circular} node. The ordering of the vertices along this node is known as \emph{circular ordering}. This ordering is such that, for each vertex $x$, the vertices of $N^+(x)$ follow consecutively; and  so do vertices from $N^-(x)$.
This, combined to the above theorem, could be seen as a sketched proof of the characterisation of \emph{round tournaments} by local transitivity (see e.g.~\cite{BJG01} for further information).

In the extended version \cite{BuixuanHLdM07a}, we present an  $O(n^2)$ recognition algorithm, 
 making an intensive use of this ordering property, and computing this ordering. It allows us to solve the 
isomorphism problem for the class of such tournament in  $O(n^2)$ time, like in \cite{Clarou96}.
We also propose the first linear-time algorithm for the feedback
vertex set problems (NP-complete for tournaments).  The 
basic idea  is to find a vertex of highest outgoing degree, and output
the tournament composed of this vertex and its outgoing neighbourhood. 

% \subsubsection{Bi-join decomposition of undirected graphs}\label{sectbi}
% %%  The same
% %% is true for undirected graphs.
% %% \TODO{Bin: pas tr\`es pr\'ecis ? quel ``same'' ? en tout cas j'ai peur de pas tr\`es bien comprendre... Fab: pareil !}
% Let us now apply the umodular decomposition framework to graphs, or
%  more exactly to the standard homogeneous relation of a graph.
%  The resulting decomposition was already
% published in \cite{MontgolfierRaoICGT2005}. We summarise here the main
% results of that paper and establish the link with umodules.
% 
% 
% \begin{definition}[bi-join]
% A \emph{bi-join} of a graph $G=(X,E)$ is a bipartition $\{X^1,X^2\}$ of
% the vertex-set such that the edges between $X^1$ and $X^2$ form at
% most two disjoint complete bipartite graphs, and that for each
% $i,j=1,2$ every vertex of $X^i$ is adjacent to a vertex of $X^j$.
% \end{definition}
% 
% 
% \begin{figure}
%  \begin{center}
% 	\includegraphics[scale=0.55]{RelationBonVoisinnage}
% 	\caption{\label{fig:RelBonVois} Forbidden arc configuration between 
% neighbourhoods}
%  \end{center}
% \end{figure}
% 
% \begin{figure}
%  \begin{center}
%   	\includegraphics[width=0.4\textwidth]{2join}
% 	\caption{\label{fig:BiJoinSample}Example of a bi-join of a graph}
%  \end{center}
% \end{figure}
% 
% 
% \begin{proposition}\label{propsens1}
% If  $\{X^1,X^2\}$ is a bi-join of a graph then both  $X^1$  and $X^2$ are 
% umodules of $G$.
% \end{proposition}
% % \begin{proof}
% % Let $A$ (resp. $C$) be the vertices of $X^1$ (resp. $X^2$) incident
% % with the first complete bipartite graph, and $B$ (resp. $D$) be the
% % other vertices of $X^1$ (resp. $X^2$). Any vertex of $X^1$
% % distinguishes a vertex of $C$ from a vertex of $D$, but can not
% % distinguish two vertices from $C$, nor two vertices from $D$. $X^1$ is
% % thus a umodule, and a similar proof holds for $X^2$. \qed
% % \end{proof}
% 
% In \cite{MontgolfierRaoICGT2005} the Seidel switch was used to derive most of 
% the properties:
% \begin{proposition}
% Let $G$ be a graph. $\{X^1,X^2\}$ is a bi-join of $G$ if and only if for every $v\in X^1$ 
% (resp. $X^2$) $X^2$ (resp. $X^1$) is a module of the Seidel switch $G(v)$.
% \end{proposition} 
% 
% It may be used to prove the converse of Proposition~\ref{propsens1}:
% \begin{proposition}
% If $U$ is a umodule of a graph $G=(X,E)$ then $\{M,X\setminus U\}$ is a 
% bi-join of $G$.
% \end{proposition}
% This is because the homogeneous relation of a tournament has local congruence 
% 2 and is self-complemented (see Section~\ref{sectlc2}).
% 
% \begin{corollary}
% The umodular decomposition of a graph equipped with its standard homogeneous 
% relation is exactly its bi-join decomposition.
% \end{corollary}
% 
% 
% Among the consequences exposed in  \cite{MontgolfierRaoICGT2005}, bi-join (thus umodular) decomposition trees have no \emph{circular} nodes.
% \begin{theorem}\label{th:BijoinuniqueTreeDecomposition}
% There is a unique unrooted decomposition tree $T$ associated to an undirected graph $G$.
% All the nodes are labelled degenerate or prime. There is exactly two kind of degenerate
% nodes: The clique nodes $K_n$ and the complete bipartite node $K_{n,m}$.
% \end{theorem}
% 
% 
% 
% 
% 
% \subsubsection{Isomorphism of  ($C_5$,bull,gem,co-gem)-free
% graphs}
% In this section, we prove that the isomorphism testing testing between
% two graphs totally decomposable w.r.t bi-join decomposition can be
% tested in linear time. This class of graph is studied by
% \cite{MontgolfierR05}. It is exactly the ($C_5$,bull,gem,co-gem)-free
% graphs  (see Figure \ref{fig:ForbiddenBijoins}), and also exactly the graphs that can be obtained from a single
% vertex by a sequence of (twin,antitwin)-extensions.
% 
% 
% \begin{figure}
% 	\begin{center}
% 		\includegraphics[scale=0.75]{BiJoin-forbidden-graphs}
% 	\end{center}
% 	\caption{Forbidden induced subgraphs for Completely Bi-join Decomposable Graphs}
% 	\label{fig:ForbiddenBijoins}
% \end{figure}
% 
% It follows from definition that the decomposition tree has no \emph{prime} nodes; furthermore, the decomposition tree alone is an $O(n)$-sized encoding of the graph (like the cotree is an $O(n)$-sized encoding of a cograph). We are then reduced to a tree isomorphism problem, as proven below.
% 
% \begin{theorem}
% Let $G_1$ and $G_2$ be graphs totally decomposable w.r.t. bi-join
%  decomposition.  Isomorphism between $G_1$ and $G_2$
% can be tested in linear time.
% \end{theorem}
% 
% 
% % \begin{proof}
% % %It is a direct consequence of theorem \ref{th:BijoinuniqueTreeDecomposition}.
% % From Theorem \ref{th:BijoinuniqueTreeDecomposition} and \cite{MontgolfierR05}, the decomposition tree of a graph is uniquely defined, and a 
% % decomposition tree with no prime nodes corresponds to exactly one graph.
% % It is then 
% % sufficient to test for decomposition trees isomorphism.
% % 
% % 
% % It is possible to compute the decomposition trees of $G_1$ and $G_2$
% % in $O(n+m)$ (see \cite{MontgolfierR05}). Then the tree isomorphism is
% % achieved in linear time \cite{AhoHU74}. Notice that decomposition
% % trees are unrooted, and that the internal node labelling with a K or S
% % is already known.
% % \end{proof}
% 
% %% \TODO{Bin: marvelous. ca commence \`a pouvoir convaincre. bravo. claps. cheers. Fab: thx bin!}
% 
% \subsubsection{A New Tournament Decomposition}\label{sectto}
% 
% We have investigated in Section~\ref{sectbi} the umodules of
% undirected graphs, and noticed that they lead to a nice decomposition.
% Similarly for tournaments our theory applies and we present a new tournament decomposition: the
% umodular decomposition. It is indeed the umodular decomposition of the
% standard homogeneous relation of the tournament. Actually this
% decomposition is more powerful than the general modular decomposition of
% \cite{BuixuanHLdM06,wg06,odsa2006}, because every module of a tournament is a umodule, while
% umodular decomposition is able to decompose M-prime tournaments -- those
% without nontrivial modules (Figure~\ref{fig:ExampleTournament}). 
% \begin{figure}[h!]
%  	\begin{center}
%  		\includegraphics[scale=0.45]{TournamentTotallyDecomposabel}
%  	\end{center}
%  		\caption{An example of a M-prime tournament which is not U-prime. 
% The umodular decomposition tree is drawn on the right.}
% \label{fig:ExampleTournament}
%  \end{figure}
% 
% 
% We can deduce from Proposition~\ref{superprop} some very interesting
% properties of the umodular decomposition of tournaments.
% 
% \begin{corollary}
% The umodular decomposition tree of a tournament has no \emph{complete node}. And there exists a circular ordering of the vertices of the tournament
% such that every umodule of the tournament is a factor (interval) of this
% circular ordering.
% \end{corollary}
% % \begin{proof}The first observation is obvious using Theorem \ref{thmain}.
% % Furthermore any traversal of the umodular decomposition tree, respecting the order
% % of the sons of a circular node, orders the leaf labels into the
% % desired circular ordering.
% % \qed
% % \end{proof}
% 
% This result was already known for modular decomposition \cite{M03}:
% there exists a (not circular) permutation of the vertices whose every
% module of the tournament is a factor. It is called \emph{factorising
% permutation}.
% 
% \begin{proposition}
% The umodular decomposition tree of a tournament can be computed in $O(|X|^2)$ 
% time.
% \end{proposition}
% % \begin{proof}
% % Again Theorem~\ref{thmain} says that one just has to perform a Seidel switch 
% % on a arbitrarily chosen vertex, then to compute the modular decomposition of 
% % the tournament. This can be done in linear (in fact $O(|X|^2)$) time using the 
% % algorithm from \cite{McCFM05}. Proposition~\ref{superprop} tells how to cast 
% % the modular decomposition tree into the umodular one.  \qed
% % \end{proof}
% 
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \subsection{Locally transitive tournaments}
% \label{secttd}
% In this section, we focus on tournaments that are totally
% decomposable w.r.t. umodular decomposition. We first show
% that they correspond to an already known class of tournaments, under the name of
% \emph{diamond-free} tournaments, or of \emph{locally transitive} tournaments. We propose different
% characterisations of this class, compact encodings and a recognition
% algorithm.
%  It is well-known  that:
% 
% \begin{proposition}\label{propzz}
% \noindent
% \begin{itemize}
% \item If $T$ is an $M$-prime tournament then $T$ contains an induced cycle 
% with 3 vertices.
% \item  $T$ is totally decomposable w.r.t. modular 
% decomposition if and only if it contains no  induced cycle with 3 vertices (it is a 
% transitive tournament).
% \end{itemize}
% \end{proposition}
% 
% \subsubsection{Characterisation theorems}
% We have:
% 
% \begin{theorem}\label{diamondfree}
%  If $T$ is an $U$-prime tournament then $T$ contains a \emph{diamond} (one of the induced 
% subgraph described in Figure~\ref{fig:PrimeConfTour}). $T$ is totally 
% decomposable w.r.t. umodular decomposition if and only if it is diamond-free.
% \end{theorem}
% 
% 
% \begin{figure}[h!]
% 	\begin{center}
% 		\includegraphics[scale=.75]{PrimeTournamentsA}
% 		\hspace{2cm}
% 		\includegraphics[scale=.75]{PrimeTournamentsB}
% 	\end{center}
% 	\caption{Minimal U-Prime Configurations in tournaments = forbidden 
% subgraphs of a tournament totally decomposable w.r.t. umodular decomposition}
% \label{fig:PrimeConfTour}
% \end{figure}
% 
% % \begin{proof}
% % Thanks to Theorem~\ref{thmain}, $T$ is $U$-prime if and only if for any vertex $v$
% % a Seidel switch at $v$ gives an $M$-prime tournament. Thanks to
% % Proposition~\ref{propzz}, one just has to check all the four-vertices
% % tournaments where a Seidel switch on a vertex produces the cycle with 3
% % vertices. It is tedious but no hard.
% % \qed
% % \end{proof}
% 
% Another characterisation is possible:
% 
% \begin{definition}
% A tournament $T$ is \emph{locally transitive}  if
% for each vertex $x \in V(T)$, $T_{[N^{+}{(x)}]}$ and $T_{[N^{-}{(x)}]}$ are transitive 
% tournaments.
% \end{definition}
% 
% It is not hard to see the equivalence between the two classes, a classical result:
% \begin{proposition}
%  \label{prop:CNSTournamentTotDecVois}
% A tournament $T$ is diamond-free if and only if it is locally transitive
% \end{proposition}
% 
% 
% \subsubsection{Recognition algorithm}
% Thanks to Theorem~\ref{diamondfree}  the class membership can be checked
% in $O(|X|^4)$ time, and thanks to
% Proposition~\ref{prop:CNSTournamentTotDecVois} in
% $O(|X|^3)$ time. The following condition provides however a faster test by checking only one vertex of the graph.
% 
% Another linear-time recognition algorithm was given by \cite{Clarou}. As far as we know, this french thesis was never published in english. We present here another linear-time recognition algorithm, based on the factorising permutation instead of so-called \emph{circular ordering} (see below). Our algorithm is furthermore \emph{certyfing}: it outputs a diamond if the graph is not diamond-free, i.e. not locally transitive. 
% 
% 
% \begin{proposition}
%  \label{prop:TheVinceTest}
% Let $T$ be a tournament and $x$ an arbitrary vertex. $T$ is locally transitive if and only if 
% \begin{enumerate}
% \item $T_{[N^+(x)]}$ and  $T_{[N^-(x)]}$ are transitive tournaments, and
% \item if a vertex $a\in N^+(x)$ has an out-neighbour $b \in N^-(x)$ and an 
% in-neighbour $c \in N^-(x)$ then  $(b,c) \in T$.
% \item if a vertex $a\in N^-(x)$ has an out-neighbour $b \in N^+(x)$ and an 
% in-neighbour $c \in N^+(x)$ then  $(b,c) \in T$.
% \end{enumerate}
% \end{proposition}
% % \begin{proof}
% % Let us suppose $T$ is totally decomposable. According to
% % Proposition~\ref{prop:CNSTournamentTotDecVois}, (i)  holds. If
% % (ii)  does not hold for some vertices $a$, $b$ and $c$, i.e. if
% % there is an arc $(c,b)$ instead of $(b,c)$, then $\{a,b,c,x\}$ induce
% % a forbidden configuration of  Figure~\ref{fig:PrimeConfTour}. Same if (iii) 
% % does not hold.
% % 
% % Conversely let us suppose that the three conditions hold. We shall prove that 
% % for every vertex, its in- and out-neighbourhoods are transitive. Then 
% % Proposition~\ref{prop:CNSTournamentTotDecVois} tells $T$ is  totally 
% % decomposable w.r.t. umodular decomposition. For $x$, this is true thanks to 
% % (i) . Let $t$ be a vertex of  $N^+(x)$. If $T_{[N^+(t)]}$ is not transitive 
% % then it contains a circuit $(u,v,w)$ (with arcs, w.l.o.g., $(u,v)$ and $(v,w)$ 
% % and $(w,u)$.) As both $T_{[N^+(x)]}$ and  $T_{[N^-(x)]}$ are transitive, the 
% % circuit overlaps them. Suppose w.l.o.g $u\in N^+(x)$ and $w\in N^-(x)$. Then 
% % (iii) is  not true: take $a=w$ and $b=u$ and $c=t$. \\
% % If we suppose  $T_{[N^+(t)]}$ is not transitive, it contains a circuit $(u,v,w)$ 
% % with an arc $(u,w)$,  $u\in N^+(x)$ and $w\in N^-(x)$. (iii) is also 
% % violated: take $a=w$ and $b=t$ and $c=u$.
% % 
% % Now let $t$ be a vertex of $N^-(x)$. If $T_{[N^+(t)]}$ is not transitive then 
% % it contains a circuit $(u,v,w)$ with an arc $(u,w)$,  $u\in N^+(x)$ and 
% % $w\in N^-(x)$. (ii)  is violated with $a=u$ and $b=w$ and $c=t$. And if 
% % $T_{[N^-(t)]}$ is not transitive then it contains a circuit $(u,v,w)$ with an 
% % arc $(u,w)$,  $u\in N^-(x)$ and $w\in N^+(x)$. (ii)  is violated with $a=u$ 
% % and $b=t$ and $c=w$.
% % \qed
% % \end{proof}
% 
% \begin{theorem}
% There exists an  $O(|X|^2)$-time certifying  algorithm to recognize  if  a tournament is locally transitive.
% \end{theorem}
% % \begin{proof}
% % Condition (i) of the Proposition~\ref{prop:TheVinceTest} can be tested in $O(|X|^2)$
% % time. Number $a_0 \ldots a_k$ the vertices of $N^+(x)$ in increasing
% % order along the transitive tournament $T_{[N^+(x)]}$, and $b_0 \ldots b_l$ the
% % vertices of $N^-(x)$ in increasing order. If $a_i$ fulfills (ii),
% % then its out-neighbourhood contains $b_0 \ldots b_{f(i)}$ and its
% % in-neighbourhood $b_{f(i)+1} \ldots b_l$. This can be tested in $O(|X|)$
% % time.  A similar test in $O(|X|)$ time is performed for each $a_i$ and
% % $b_j$, leading to an $O(|X|^2)$-time algorithm.
% %  \qed
% % \end{proof}
% Algorithm~\ref{algo:TotallyDecomposableRecognition} presents a
% certifying implementation of this proof.
% 
% \begin{algorithm}
% \dontprintsemicolon
% \SetKw{Y}{Yes}
% \SetKw{N}{No}
% 
% \SetKw{A}{A}
% \SetKw{B}{B}
% \SetKw{Cy}{3-Circuit}
% \SetKw{Dv}{Dominating vertex}
% \SetKw{Av}{Anti-Dominating vertex}
% \SetKw{Fail}{Failure: certificate is}
% \KwData{A Tournament $T=(V,A)$}
% \KwResult{
% \\
% \hspace{0.5cm} \Y: A circular factorising permutation $\sigma$ of $T$.\\
% \hspace{0.5cm} \N: An obstruction.
% }
% 
% \Begin{
% Pick a vertex $x \in V$ \;
% \A $\leftarrow~ N^{+}(x)$ \;
% \B $\leftarrow~ N^{-}(x)$ \;
% 
% 
% \If{$T_{[\A]}$ is not a transitive tournament}
% {
% \Fail{A dominated 3-circuit} \;
% } 
% \If{$T_{[\B]}$ is not a transitive tournament}
% {
% \Fail{A anti-dominated 3-circuit} \;
% }
% \For{ $i~ \gets 1$ \KwTo $k$}
% {
% 	\If{there exists $j \in \{0,\ldots,l\}$ such that}{
% 	$\forall~p \leq j$ $b_p \in N_{\B}^{+}(a_i)$ \;
% 	$\forall~q > j $ $b_q \in N_{\B}^{-}(a_i)$�\;
% 	}
% 	\Else{
% 		Find  $\alpha$ and $\beta$ such that $\alpha < \beta$ \;
%  		with $b_{\alpha} \in N_{\B}^{-}(a_i)$ and  
% 	$b_{\beta} \in N_{\B}^{+}(a_i)$ \;
% 		\Cy $\gets (a_i, b_{\beta},x)$ \;
%  		\Dv $\gets b_{\alpha}$ \;
% 		\Fail{(\Dv,\Cy)}
% 	}
% }
% 
% \For{ $i~ \gets 1$ \KwTo $l$}
% {
% 	\If{there exists $j \in \{0,\ldots,k\}$ such that}{
% 	$\forall~p \leq j$ $a_p \in N_{\A}^{+}(b_i)$ \;
% 	$\forall~q > j $ $a_q \in N_{\A}^{-}(b_i)$�\;
% 	}
% 	\Else{
% 		Find  $\alpha$ and $\beta$ such that $\alpha < \beta$ \;
%  		with $a_{\alpha} \in N_{\A}^{-}(b_i)$ and  
% 	$a_{\beta} \in N_{\A}^{+}(b_i)$ \;
% 		\Cy $\gets (a_{\alpha},b_i,x)$ \;
%  		\Av $\gets a_{\beta}$ \;
% 		\Fail{(\Av,\Cy)}
% 	}	
% }
% 
% Pick a vertex $x$ \;
% Compute a Seidel switch on $x$ \;
% $\sigma \gets Seidel(x) \cup x$\;
% \Return{$\sigma(V)$ a circular factorising permutation.}
% }
% 
% \caption{Certifying recognition of a  totally $U$-decomposable tournament. The certificate output on failure is a diamond; on success is a circular factorising permutation (the set of intervals of this permutation is exactly the set of umodules)}
% \label{algo:TotallyDecomposableRecognition}
% \end{algorithm}
% 
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 
% \subsubsection{Umodular decomposition tree of a locally transitive tournament}
% \begin{theorem}[Umodular decomposition tree of locally transitive tournaments]\label{thnod}
% The umodular decomposition tree of a locally transitive has only one 
% single node. Moreover this node is a circular node.
% \end{theorem}
% 
% % \begin{proof}
% % According to Theorem~\ref{thmain} for any $x$ the Seidel switch at vertex $x$ 
% % of a tournament $T$ totally decomposable w.r.t. umodular decomposition gives 
% % a tournament $T(x)$ totally decomposable w.r.t. modular decomposition. According 
% % to Proposition~\ref{propzz} $T(x)$ is transitive: its modular decomposition tree 
% % has a single linear node. According to  Proposition~\ref{superprop} the 
% % umodular decomposition tree of $T$ only has a circular node.\qed
% % \end{proof}
% 
% It is well known that for encoding  a cograph, it is enough to store its modular decomposition tree. 
% Unfortunately, for a locally transitive tournament, the decomposition tree is not enough since it does not encode 
% adjacencies between vertices.
% 
% The circular ordering of the vertices along this unique
% \emph{circular} node is called a \emph{circular factorising
%   permutation}, since every umodule of $G$ is an interval of this
% circular permutation, and the converse also holds, by definition of a
% circular node.
% 
%  Further results on locally transitive tournaments
% are known:
% 
% % But it is possible to take advantage of the circular ordering of the 
% % nodes to define the following compact encoding.
% 
% \subsubsection{Circular structure of locally transitive tournaments}\label{sectcircu}
% A circular structure result of Locally transitive tournament is known from Lopez and Rauzy, we recall it here.
% %% Thanks to theorem~\ref{diamondfree} we can give a shorter proof of a
% %% well-known result~\cite{LR92}
% %% \begin{lemma}\label{lemyy}
% %% A nontrivial     module  $M$ of a locally transitive tournament induces a transitive tournament.
% %% \end{lemma}
% %% \begin{proof}
% %% If not, it contains a cycle $(a,b,c)$. As the module is not $V$, there
% %% is another vertex $d\notin M$ and we have $M\subseteq N^+(d)$ or
% %% $M\subseteq N^-(d)$. In either case, these four vertex are a diamond,
% %% forbidden by Theorem~\ref{diamondfree}.
% %% \end{proof}
% 
% %According to~\ref{??}, as a tournament has local congruence 2, then every module of a tournament is a umodule.
% 
% %% \begin{definition}
% %% The \emph{maximal strong modules} of a tournament $G=(V,E)$ are the modules which are smaller than $V$, do not overlap any other module
% %% and are maximal w.r.t. inclusion for these two properties.
% 
% %% \end{definition}
% 
% %% Let $Q$ be a subset of $V$ such that each maximal strong module has exactly one vertex in $Q$. $G[Q]$ is called a \emph{quotient} of $G$. It is well-known that:
% 
% %% \begin{proposition}\label{propxx}
% %% \begin{enumerate}
% %% \item The maximal strong module of a tournament form a uniquely defined partition.
% %% \item The quotient of $G$ does not depend on the choice of $Q$ (i.e. all quotient are isomorphic).
% %% \item The quotient of a tournament is either a transitive tournament or a M-prime tournament
% %% \end{enumerate}
% %% \end{proposition}
% 
% 
% \begin{definition}
% A tournament $G=(V,E)$ is a \emph{complete circuit} if the vertices
% can be numbered from 0 to $2k$ and if for every vertex numbered $i$,
% its out-neighbourhood is the vertices numbered from $i+1$ to $i+k$ inclusively (modulo $2k+1$).
% \end{definition}
% 
% 
% \begin{figure}
% \begin{center}
%  \includegraphics[scale=0.55]{completecircuit}
% \end{center}
% \caption{The complete circuit of 7 vertices ($k=3$).}
% \end{figure}
% 
% 
% %% \begin{theorem}\cite{LR92}
% %% The M-prime locally transitive tournaments are exactly the complete circuits
% %% \end{theorem}
% %% \begin{corollary}
% %% The quotient of a locally transitive tournament is either a transitive tournament or a complete circuit
% %% \end{corollary}
% 
% 
% \begin{theorem}\label{cordechasse}\cite{LR92}
% Let $G=(V,E)$ be a locally transitive tournament. 
%  $V$ can be partionned into $V_0 \ldots V_{2k}$,
% $k\ge 0$, and
% \begin{itemize}
% \item for each $0\le i\le 2k$ $G[V_i]$ is a transitive tournament
% \item for $x\in V_i$ and $y\in V_j$, if there exists $a\le k$ such that $i = a+j$ modulo $2k+1$ then $(x,y)$ is an arc of $G$, otherwise $(y,x)$ is an arc of $G$
% \end{itemize}
% \end{theorem}
% 
% Notice than every $V_i$ is a module of the graph, furthermore these modules are maximal wrt inclusion (the only module containing $V_i$ is $V$).
% 
%  \begin{corollary}\label{lemyy}
%  A nontrivial     module  $M$ of a locally transitive tournament induces a transitive tournament.
%  \end{corollary}
% 
% %% \begin{proof}
% %% As every maximal strong module is a transitive tournament, one just
% %% has to substitute a transitive tournament to each of the $2k+1$
% %% vertices of a complete circuit to get all locally transitive tournaments.
% %% \end{proof}
% 
% 
% \begin{figure}
% \begin{center}
%  \includegraphics[scale=0.75]{cycleTournament3}
% \end{center}
% \caption{Example of locally transitive graph of 9 vertices: the complete circuit of 5 vertices where each vertex is substututed with a transitive tournament. A circular ordering is $(\{a\},\{b,c,d\},\{e\},\{f,g\},\{h,i\})$ while a factorizing permutation is $(a,e,i,h,d,c,b,g,f)$ (see Section~\ref{sectcircu})
% }
% \label{figfigfig}
% \end{figure}
% 
% %% \TODO{et hop! Trois pages compressees en une demi! Mais ce
% %%   theoreme 14 existe quelque part au moins ?}
% 
% 
% 
% %% \subsection{Circular arc ordering of a TTDU}
% %% \begin{definition}
% %% \begin{itemize}
% %% \item
% %%   A \emph{circular ordering} of a finite set $V$ is a binary relation $R$ over $V$ such that the graph $(V,R)$ is a circuit (connected 2-regular graph).
% %% \item
% %% An \emph{interval} of $R$ is a subset $F$ of $V$ such that $(V,R)[F]$ is connected.
% %% \item
% %%  A \emph{numbering function} of $V$ compatible with $R$ is a function  $f_R:V\mapsto \{1,..|V|\}$ such that
% %% if $x$ and $y$ are adjacent in $R$ then $|f_R(x)-f_R(y)|=1$ or  $|f_R(x)-f_R(y)|=|V|-1$.
% %% \item
% %% A \emph{circular arc ordering} of a tournament $G=(V,E)$ of $n$ vertices is a circular ordering $R$ of $V$ such that, for any vertex $x$,  $N^+(x)$ and $N^-(x)$ are intervals of $R$.
% 
% %% \item A \emph{clockwise numbering function} of a tournament $G=(V,E)$
% %% with a circular arc ordering $R$ is a numbering function compatible with $R$ such that for
% %% all $i$ taken modulo $|V|$, $(f(i),f(i+1))$ is an arc of $G$.
% %% \end{itemize}
% %% \end{definition}
% 
% %% \TODO{dessins}
% 
% %% As stated by Theorem~\ref{thnod}, the ordering of the unique circular node of a TTDU is a circular ordering. We shall prove that it is indeed a circular \emph{arc} ordering. This section is devoted prove to the following theorem.
% 
% 
% %% \begin{theorem}\label{thcirc}
% %% A tournament admits a circular arc ordering if and only if it is TTDU. The circular arc ordering, if it exists, is unique.
% %% \end{theorem}
% 
% %% %For instance, a transitive tournament admits a circular arc ordering. 
% %% If a numbering function exists, then the successor of $x$, denoted $succ(x)$, is the vertex $y$ such that $f(y)=1+f_R(x)$ modulo $|V|$, and $x=pred(y)$ is $y$ predecessor. 
% 
% %% We shall prove theorem~\ref{thcirc} first for transitive tournaments, and then for other TTDU. The first part is the easy one: a transitive tournament is a TTDU, and clearly admits a circular arc ordering. Just order the vertices following the total ordering induced by the tournament. Of course transitive tournaments do not admit a clockwise numbering function. Now we shall focus on non-transitive TTDU.
% 
% 
% %% \begin{lemma}\label{lemord}
% %% If a non-transitive tournament admits a circular arc ordering $R$, then $R$ admits a clockwise numbering function.
% %% \end{lemma}
% %% \begin{proof}
% %% Let $x$ be a vertex and $y$ and $z$ its two neighbours. Let us consider the arcs between $x$ and its neighbours.
% %% \begin{itemize}
% %% \item if $(x,y)$ and $(x,z)$ are arcs, then $N^+(x)=V\setminus \{x\}$: $v$ is a sink. A Seidel switch at $x$ gives a transitive tournament. $G[N^+(x)]$ is thus a transitive tournament and finally $G$ is a transitive tournament.
% %%  \item if $(y,x)$ and $(z,x)$ are arcs, then $N^-(x)=V\setminus \{x\}$ and, there also,  $G$ is a transitive tournament.
% %% \end{itemize}
% %% Let us take a numbering function $f_R$ such that $(f(1),f(2))$ is an arc (there always exists such a numbering function). Then $(f(2),f(3))$ is also an arc, or $f(2)$ would be a sink. Recursively for all $i$ taken modulo $|V|$, $(f(i),f(i+1))$ is an arc. $f_R$ is therefore a clockwise numbering.
% %% \end{proof}
% 
% %% Notice that $x$ is always at one boundary of the intervals  $N^+(x)$ and  $N^-(x)$.  
% 
% %% \begin{lemma}\label{yalemma}
% %% If a tournament admits a circular arc ordering $R$ and a clockwise numbering function $f_R$, then for any vertex $x$, $N^+(x)$ and  $N^-(x)$ are transitive tournaments.
% %% \end{lemma}
% %% \begin{proof}
% %% Let us suppose $N^+(x)$ is not transitive for some vertex $x$. It then
% %% contains a cycle of three vertices $a$, $b$ and $c$ with, w.l.o.g,
% %% arcs $(a,b)$, $(b,c)$ and $(c,a)$. Let us suppose, without loss of
% %% generality, that in $f_R$ we have $(...x...a...b...c...)$, i.e. $a$ is
% %% between $x$ and $b$, and so on. Let $d$ be the successor of $c$ in
% %% $f_R$. As $(c,d)\in E$ and $(x,c)\in E$, $d\ne x$. Then $N^+(c)$ is
% %% not an interval, since it contains $d$ and $a$ but $x$ is between them.
% %% \end{proof}
% 
% %% We can now prove the first implication of Theorem~\ref{thcirc}: if a tournament admits a circular arc ordering,
% %% \begin{itemize}
% %% \item either it admits  a clockwise numbering function, and by Lemma~\ref{yalemma} has a property implying it is a TTDU, by Proposition~\ref{prop:CNSTournamentTotDecVois}.
% %% \item or it is a transitive tournaments, by Lemma~\ref{lemord}, and clearly is a TTDU
% %% \end{itemize}
% 
% %% Now we shall prove the converse: if a tournament is TTDU, then it
% %% admits a circular arc ordering.
% 
% %% \begin{lemma}
% %% A circular factorising
% %% permutation (as computed by Algorithm~\ref{algo:TotallyDecomposableRecognition}, for instance) of a TTDU
% %% is a circular arc ordering.
% %% \end{lemma}
% %% \begin{proof}
% %% Let $R$ be such a circular permutation.  Let
% %% us suppose that for some vertex $x$, $N^+(x)$ or $N^-(x)$ is not an interval of
% %% $R$. W.l.o.g say that $N^+(x)$ is not. Then in $R$ we have $...x...a...b...c...$ with $a,c\in N^+(x)$ and $b\in N^-(x)$.
% 
% %% As $R$ is a circular factorising permutation, every interval of $R$ is
% %% a umodule. As there exists a umodule containing $x$ and $a$, but not $b$ nor $c$, and $x$ distinguishes $b$ from $c$, then $a$ also distinguishes $b$ from $c$, i.e. either $(a,b)\in E$ and $(c,a)\in E$, or  $(b,a)\in E$ and $(a,c)\in E$.
% %% In second case, $N^-(a)$ is not an interval (it contains $x$ and $b$ but not $c$) so  $(a,b)\in E$ and $(c,a)\in E$. 
% 
% %% As there exists another umodule containing $x$ and $c$, but not $a$ nor $b$, the same reasoning give that $(a,c)\in E$ and $(c,b)\in E$, in contradiction with 
% %%  $(a,b)\in E$. 
% 
% %% $N^+(x)$ is thus an interval.
% %% \end{proof}
% 
% %% We have proven the first sentence of Theorem~\ref{thcirc}. We can go further and state uniqueness of circular ordering:
% 
% %% \begin{lemma}
% %% Let $G=(V,E)$ be a TTDU and $x$ a vertex. After a Seidel switch at $x$, the neighbours of $x$ are the sink and the source of the transitive tournament $G(x)$
% %% \end{lemma}
% %% \begin{proof}
% %% Let $s$ be the sink of $G(x)$.
% %% Since $V\setminus\{s\}$ is a module of $G(x)$, $\{x,s\}$ is a umodule of $G$ so $x$ and $s$ follow consecutively in $R$. Same for the source of $G(x)$.
% %% \end{proof}
% 
% %% This lemma has a direct consequence. Since $G(x)$ is uniquely defined, the neighbours of any vertex $x$ in any circular arc ordering are the same and thus:
% %% \begin{lemma}\label{lembij}
% %% If a tournament admits two circular arc orderings $R$ and $R'$ then $R=R'$.
% %% \end{lemma}
% %% This lemma proves the second sentence of  Theorem~\ref{thcirc}.
% 
% 
% %% \subsection{Complete Circuit of Transitive Tournaments}
% %% We can further refine Theorem~\ref{thcirc}. 
% %% According to~\ref{??}, as a tournament has local congruence 2, then every module of a tournament is a umodule.
% 
% %% \begin{definition}
% %% The \emph{maximal strong modules} of a tournament $G=(V,E)$ are the modules who
% %% \begin{itemize}
% %% \item are smaller than $V$
% %% \item do not overlap any other module
% %% \item are maximal w.r.t. inclusion for these two properties
% %% \end{itemize}
% %% \end{definition}
% 
% %% Let $Q$ be a subset of $V$ such that each maximal strong module has exactly one vertex in $Q$. $G[Q]$ is called a \emph{quotient} of $G$. It is well-known \cite{??} that:
% 
% %% \begin{proposition}\label{propxx}
% %% \begin{enumerate}
% %% \item The maximal strong module of a tournament form a uniquely defined partition.
% %% \item The quotient of $G$ does not depend on the choice of $Q$ (i.e. all quotient are isomorphic).
% %% \item The quotient of a tournament is either a transitive tournament or a M-prime tournament
% %% \end{enumerate}
% %% \end{proposition}
% 
% %%  Of course, in the circular arc ordering of a TTDU, a maximal strong module is an interval. So we can partition the circular arc ordering of a TTDU into maximal strong modules.
% 
% %% \begin{lemma}\label{lemyy}
% %% A maximal strong modules $M$ of a TTDU is a transitive tournament.
% %% \end{lemma}
% %% \begin{proof}
% %% If not, it contains a cycle $(a,b,c)$. As the module is not $V$, there is another vertex $d\notin M$ and we have $M\subseteq N^+(d)$ or  $M\subseteq N^-(d)$. In either case, these four vertex are a forbidden configuration of TTDU (see Figure~\ref{fig:PrimeConfTour}).
% %% \end{proof}
% 
% 
% %% %% According to \cite{??}, a tournament is either
% %% %% Let $G$ be a TTDU. Let us consider the maximal nontrivial modules of $G$, i.e. the module with less than $|V|$ vertices who are not contained in 
% 
% 
% %% %% In the following, $G=(V,E)$ is a tournament that admits a circular arc ordering $R$, and $f_R$ is a given numbering function (a clockwise one if $G$ is not transitive) and $lnh()$ always refers to  $f_R$ numbering.  
% %% %%  $lnh^{-1}(x)$ is the set $\{y|lnh(y)=x\}$. 
% %% %% \begin{lemma}
% %% %% For all $x$, $lnh^{-1}(x)$ is a module and is an interval of $R$.
% %% %% \end{lemma}
% %% %% \TODO{prouver}
% 
% 
% %% \begin{definition}
% %% A tournament $G=(V,E)$ is a \emph{complete circuit} if the vertices
% %% can be numbered from 0 to $2k$ and if for every vertex numbered $i$,
% %% its out-neighbourhood is the vertices numbered from $i+1$ to $i+k$ inclusively (modulo $2k+1$).
% %% \end{definition}
% 
% %% \TODO{dessin}
% 
% %% \begin{lemma}\label{lemzz}
% %% The quotient of a CCTU $G$ is either a transitive tournament or a complete circuit
% %% \end{lemma}
% %% \begin{proof}
% %% As it is an induced subgraph of a CCTU, a CCTU is by definition an
% %% hereditary graph class, the quotient of a CCTU is a CCTU. If $G$ is
% %% transitive, its quotient is exactly $G$ and is transitive. Otherwise,
% %% by Proposition~\ref{propxx} it is a M-prime tournament. We just have
% %% to prove that the M-prime CCTU are exactly the complete circuits.
% 
% %% Let $G$ be a M-prime CCTU and $R$ a circular arc-ordering of $G$. If
% %% it has three vertices the assumption is true. It it has at least four
% %% vertices, then it is not transitive (Proposition~\ref{propxx}) so it
% %% admits a clockwise numbering function $f_R$ (Theorem~\ref{thcirc} plus Lemma~\ref{lemord}).
% 
% %% Let us suppose that,  for two consecutive
% %% (in $R$) vertices $x$ and $y$, we have $lnh(x)=lnh(y)$. Then $\{x,y\}$
% %% is a module, contradiction. As $G$ is $M$-prime $lnh(x)\ne lnh(y)$ for any consecutive $x$ and $y$.
% 
% %% %% $$x=succ(y) \ \ Rightarrow \ \ lnh(x)=succ(lnh(y))$$
% 
% 
% 
% %% Let us suppose that for a vertex $x$ we have $|N^+(x)|\ne|N^-(x)|$ and, w.l.o.g,  $|N^+(x)|<|N^-(x)|$. Then some vertex $y\in  N^-(x)$, $lnh(y)\in  N^-(x)$. 
% %% $x,y,lnh(x)$ and $lnh(y)$ form a forbidden configuration for TTDU: $y$ out-neighborhood contains the three other vertices, who form a cycle.
% 
% %% So for every vertex $x$, $|N^+(x)|=|N^-(x)|$. As $G$ admits a circular
% %% arc ordering, $lnh(x)$ is its opposite vertex in the ordering. So $G$
% %% is a complete circuit.
% %% \end{proof}
% 
% 
% %% \begin{definition}
% %% A tournament $G=(V,E)$ is a \emph{complete circuit of transitive
% %% tournaments} (CCTT) if $V$ can be partionned into $V_0..V_{2k}$,
% %% $k\ge 0$, and
% %% \begin{itemize}
% %% \item for each $0\le i\le 2k$ $G[V_i]$ is a transitive tournament
% %% \item for $x\in V_i$ and $y\in V_j$, if there exists $a\le k$ such that $i = a+j$ modulo $2k+1$ then $(x,y)$ is an arc of $G$, otherwise $(y,x)$ is an arc of $G$
% %% \end{itemize}
% %% \end{definition}
% %% \TODO{Dessin}
% 
% %% %% \begin{lemma}\label{uniqk}
% %% %% If a tournament $G$ admits two partitions $\{V_1..V_{2k+1}\}$ and $\{V'_1..V'_{2l+1}\}$ satisfying the definition above, then $k=l$. Furthermore the two partitions are equivalent up to circular permutation: there exists $a$ such that for all $1\le i\le 2k+1$,  $V_i = 'V_{i+a \ \mathrm{modulo} \ 2k+1}$.
% %% %% \end{lemma}
% %% %% \begin{proof}
% %% %% \TODO{a faire}
% %% %% \end{proof}
% 
% 
% %% \begin{theorem}\label{thcctt}
% %% The CCTT are exactly the tournament totally decomposable with respect to umodular decomposition.
% %% \end{theorem}
% %% \begin{proof}
% %% Direct consequence of Lemmas~\ref{lemyy} and~\ref{lemzz}.
% %% If $G$ is a transitive tournament then the theorem is true, with $k=0$. Otherwise its quotient is a complete circuit of $2k+1$ vertices and $G$ is a CCTT of $2k+1$ transitive tournaments, each one being a strong module. 
% %% \end{proof}
% 
% 
% The circular ordering of the $2k+1$ strong modules, i.e. the circular partition $V_0 \ldots V_{2k}$ as defined in
%   Theorem~\ref{cordechasse}. henceforth called \emph{circular ordering}
% 
% We have seen another ``circular structure'' exists: the circular factorising permutation of the $n$ vertices.
% These two circular orderings are not isomorphic however.
% 
% %% \subsection{Construction of the circular structure}\label{sectcircu}
% %% We have seen two kinds of circular structures in a locally transitive
% %% tournament:
% 
% %% \begin{itemize}
% %% \item The circular factorising permutation of the $n$ vertices
% %% \item The circular ordering of the $2k+1$ strong modules as in
% %%   \cite{??}, i.e. the circular partition $V_0 \ldots V_{2k}$ as defined in
% %%   Theorem~\ref{cordechasse}. henceforth called \emph{circular ordering}
% %% \end{itemize}
% %% %\TODO{remplacer circular par tout nom sympa et consensuel}
% 
% 
% 
% Let $G=([0�\ldots 2k],E)$ be the unique (up to isomorphism) complete
% circuits of $2k+1$ vertices. Then let $\tau$ be the bijection
% $$\tau(i) = ki\ modulo \ 2k+1$$
% 
% Let $\tau'$ be $\tau$ seen as a circular list
% \begin{proposition}
% The intervals of $\tau'$ are exactly the umodules of $G$
% \end{proposition}
% % \begin{proof}
% % Thanks to the property of closure under union of overlapping umodules
% % (Proposition~\ref{propu}) we just have to check that the umodules of
% % tow vertices are exactly the pairs $\{i, i+k\}$ (additions are
% % performed modulo $2k+1$). This is easy to check.
% % \end{proof}
% 
% This proposition can be generalised if $G$ is locally transitive, but not a
% complete circuit. 
% 
% \begin{proposition}\label{propmuch}
% Let $G=(V,E)$ be a locally transitive tournament and $V_0 \ldots V_{2k}$ be its
% circular ordering. Each $V_i$ induce a transitive tournament, i.e its
% vertices form a chain $v_i^1...v_i^{f(i)}$.
% 
% Let $\sigma$ be the circular permutation such that
% \begin{itemize}
% \item Each $V_i$ is a factor (interval) of $\sigma$
% \item The $V_i$ follow consecutively following $\tau'$, ie $V_0$ then
%   $V_k$ then $V_{2k}$ then $V_{3k}$... (subscripts modulo $2k+1$)
% \item Within each $V_i$ the ordering of vertices is the reverse of the
%   ordering of the chain:   $v_i^{f(i)}...v_i^1$.
% \end{itemize}
% 
% 
% The umodules of $G$ are exactly the intervals of $\sigma$
% (i.e. $\sigma$ is a circular factorising permutation of $G$).
% 
% Furthermore,  $\sigma$ is the unique circular factorising permutation
% of $G$.
% \end{proposition}
% Figure~\ref{figfigfig} gives a example of the relationship between the
% circular ordering and the circular factorising permutation.
% 
% This proposition allows to contruct the circular ordering, 
% given the circular factorizing
% permutation computed by
% Algorithm~\ref{algo:TotallyDecomposableRecognition}.
% 
% A first step should identify the $2k+1$ induced tournaments.
% Two vertices $u$ and $v$ are \emph{twins} if
% $N^+(u)\setminus\{v\}=N^+(v)\setminus\{u\}$. They are
% \emph{consecutive twins} for a circular factorising permutation $\sigma$ if
% they follow consecutively in $\sigma$. Let $R$ be the transitive
% closure of the \emph{consecutive twins} relation
% 
% \begin{proposition}\label{proptruc}
% The equivalence classes of $R$ are exactly the induced transitive
% tournaments $V_0 \ldots V_{2k}$ of the circular ordering of a locally transitive
% tournament.
% \end{proposition}
% % \begin{proof}
% % It is not hard to check that, in a tournament, two twins form a module of two vertices, and that the classes of the transitive closure $R$ are thus modules. Then just apply Corollary~\ref{lemyy}. We just have to check that each class $M$ of $R$ is a \emph{maximal} module: if not then there exists $x$ such that $M\cup\{x\}$ is a module, but then either $x$ and $M$ sink, or $x$ and $M$ source, are twins, contradiction.
% % \end{proof}
% 
% %\TODO{dessin qui explique le passage de l'un a l'autre}
% 
% Then we can give another quadratic-time algorithm than the one of \cite{Clarou}
% \begin{theorem}\label{thordo}
% The circular ordering of a tournament can be computed in $O(n^2)$
% \end{theorem}
% % \begin{proof}
% % First Algorithm~\ref{algo:TotallyDecomposableRecognition} computes the
% % circular factorising permutation. Then the relation $R$ of
% % Proposition~\ref{proptruc} can be
% % computed by checking if the $n$ pairs of consective vertices are twins
% % or not. Then the sets $V_0 \ldots V_{2k}$ are re-ordered using the inverse
% % of $\tau$ as in
% % Proposition~\ref{propmuch}.
% % \end{proof}
% 
% 
% 
% 
% %% \subsection{Generation of all TTDU}
% %% We now present an algorithm to generate (at least once) every tournament 
% %% totally decomposable w.r.t. umodular decomposition. To generate a tournament 
% %% with $n$ vertices, we have to check that it does not violate the conditions 
% %% described in Proposition \ref{prop:TheVinceTest}. A very simple manner to 
% %% proceed is to take a transitive tournament $T_{n-1}$ with $n-1$ vertices, and 
% %% then choose a subset $S$ of the vertices of $T_{n-1}$. We add a vertex $x$, 
% %% and decide that $N^+(x)=S$ and $N^-(x)=V(T_{n-1})\setminus S$. Once we have 
% %% $N^+(x)$ and $N^-(x)$ it suffices to reverse every arc between $N+(x)$ and 
% %% $N^-(x)$. In this way we have created a tournament $T_n$ which is totally 
% %% decomposable w.r.t. umodular decomposition.
% 
% 
% 
% \subsubsection{Efficient storage of locally transitive tournaments}
% %\TODO{Bin: j'aime cette section. meme si elle tombe sur l'article comme le coq a l'ane (le coca light ?), Michel avait mentionn\'e de le virer, je vote qu'on le garde. Fab (outr\'e) QUOI ?? On la garde, y'a un OPEN PROBLEM dedans b*rdel !}
% \label{sectenum}
% \begin{definition}
% A \emph{composition} of $n$ is a list of $k$ integer terms such that
% the sum of the terms is $n$. The composition is \emph{odd} if $k$ is odd.
% 
% An \emph{circular odd composition} of $n$ is a circular list of $2k+1$ integer terms such that the sum of the terms is $n$. Notice that a circular list has  reading direction: $\{1,2,3\}$ differs from  $\{3,2,1\}$ but is same than $\{2,3,1\}$.
% \end{definition}
% Brouwer~\cite{brouwer80} computed the number of locally transitive tournaments by establishing a bijection between them and ``\emph{shift registers where the complement of the bit shifted out of the last position is shifted into the first position}''.
% These results can be rephrased as:
% 
% \begin{theorem}\label{thbij}~\cite{brouwer80}
%  There is a bijection between the totally decomposable tournaments of
%  $n$ vertices and the circular odd compositions of $n$
%  elements.\end{theorem}
% %% \begin{proof}
% %% According to Theorem~\ref{diamondfree}, totally decomposable tournaments of
% %% $n$ vertices are exaclty the locally transitive tournament of $n$
% %% vertices. From Corollary~\ref{cordechasse}, a locally transitive tournament
% %% is made with $2k+1$ bags of vertices, each bag being a transitive
% %% tournament. $k$ is uniquely defined. The circular list of bags thus
% %% defines a locally transitive tournament. Of course, two different circular odd
% %% compositions define two distinct locally transitive tournament, while a
% %% locally transitive tournament admits a unique  circular odd composition: it is a bijection.
% %% \end{proof}
% 
% Brouwer gave  the first terms of the sequence, i.e. the number of locally transitive tournaments on $n$ vertices, referred in 
% Sloane encyclopedy \cite{Sloane} as A000016:
% 1, 1, 1, 2, 2, 4, 6, 10, 16, 30, 52, 94, 172, 316, 586, 1096, 2048, 3856, 7286, 13798, 26216, 49940, 95326, 182362, 349536, 671092, 1290556, 2485534, 4793492, 9256396, 17895736.
% He also gave the exact value:
% $$\sum_{d|n} \frac{ 2^{d-1}}{d} \ odd( \frac{d}{n} ) \ \sum_{e|\frac{n}{d}} \frac{\mu(e)}{e} $$
% where $\mu$ is the M\"obius function and $odd(x)$ is 1 if $x$ odd, 0 otherwise.
% 
% %% This theorem can be used to count locally transitive tournament. It is well
% %% known (see \cite{andrews} for instance) that the number of
% %% compositions of $n$ is $2^{n-1}$. The proof is that the number of sums
% %% of $k$ terms summing at $n$ is $\binom{n}{k}$. So the number of
% %% \emph{odd compositions} is the sum
% %% of $\binom{n}{k}$ for odd $k$, and is $2^{n-2}$.  With the exception
% %% that the value number of odd compositions of $n=1$ is $1$.
% 
% %% Let $C(n)$ be the number of circular  odd compositions of $n$.  The
% %% first values of $C$ are $$1,1,2,2,4,6,10,16,29,51 \ldots$$  This integer
% %% sequence is not found in Sloane encyclopedy \cite{Sloane}. But we have:
% 
% %% \begin{theorem}
% %% For $n>1$, $$\frac{2^{n-2}}{n} \le C(n) \le 2^{n-2}$$
% %% \end{theorem}
% %% \begin{proof}
% %% For the second inequality: there are clearly less circular  odd compositions of $n$ than  odd compositions of $n$. For the first one: a circular list of $2k+1$ elements can give up to $2k+1$ lists (but can give less, since some isomorphism occur: for instance circular list $(1,2,1,2)$ gives only two lists $(1,2,1,2)$ and $(2,1,2,1)$ and not four). As $2k+1$, the number of terms, is bounded by $n$, we have our inequalities.
% %% \end{proof}
% 
% %% Notice that the actual number of circular  odd compositions (and thus of locally transitive tournament, thanks to Theorem~\ref{thbij}) is very close to $\frac{2^{n-1}}{n}$, so is in the middle of the two bounds.
% 
% 
% Remark that the number of tournaments 
% totally decomposable w.r.t. umodular decomposition is strictly larger than the 
% number of tournaments totally decomposable w.r.t. to modular decomposition. 
% For modular decomposition there exists indeed only \emph{one} tournament totally 
% decomposable with $n$ vertices!
% 
% 
% \begin{theorem}
% A locally transitive unlabelled (resp. labelled) tournament of $n$ vertices
% can be stored in $O(n)$ (resp. $O(n\log n))$ bits. 
% \end{theorem}
% % \begin{proof}
% % If the tournament is unlabelled, one just has to store the
% % corresponding circular odd integer composition. This can be done using a
% % standard encoding of compositions: a vector of $n-1$
% % bits. If the $k$th term of the composition is $x$, it is stored by $x-1$
% % ones followed by a zero. The last bit is always zero and thus can be omitted. For instance the composition $\{2,3,1,1,3\}$ of
% % 10 is stored as $[1,0,1,1,0,0,0,1,1]$. This is a classical canonical encoding of  compositions~\cite{andrews}.
% % 
% %  If the graph is labelled, the permutation of vertices is must also be
% %  stored, in  $O(n\log n)$ bits. 
% % \end{proof}
% 
% \subsubsection{Minimum Feedback Vertex Set}
% 
% The Minimum Feedback Vertex Set problem is NP-Hard on directed graphs \cite[GT7]{GareyJ79},
% and remains NP-Hard on tournaments  \cite{Speckenmeyer89}.
% 
% In this section show that the Minimum Feedback Vertex Set % (MFSV for short) 
% is polynomial on tournaments totally decomposable w.r.t. umodular decomposition. 
% 
% Let us recall what a feedback vertex set is. A feedback vertex set of directed 
% graph $G=(V,A)$ is a subset $V' \subseteq V$ such that each element of $V'$ 
% belongs to at least  one circuit of $G$. The goal is to minimise the cardinality of $V'$. 
% 
% Another way of considering this problem is to find a  minimum set whose removal will 
% result in an acyclic graph.
% 
% Consequently in tournaments, the problem is equivalent to find the maximum 
% sub-tournament induced, which is transitive. 
% 
% Considering the structure of tournament totally decomposable , it not hard to be 
% convinced that finding the maximum transitive sub-tournament induced can be done in 
% polynomial time. Actually it suffices to find the vertex with the maximum out 
% or in-degree and retrieve its neighbours and then output the complementary set.
% 
% Theses operations can be achieved in $O(n^2)$-time.
% 
% \subsubsection{Isomorphism}
% 
% As far as we know, the status of the isomorphism problem is still unknown for tournaments.
% \cite{BabaiL83,ArvindDM06}. \cite{Clarou} gave a linear-time algorithm for locally transitive tournaments isomorphism. It is not hard to see that, given the compact encoding given in Section~\ref{sectenum}, isomorphism can be tested in $O(n)$ time. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

 

\section{Extensions and further developments}
We have presented the umodules and homogeneous relations focusing on
graph theory field. But umodules may be found in many other objects.
For instance, if we take a commutative ring and define\\
\centerline{$H_\times(x|yz) \ \iff \ xy = xz,$}
then  the principal ideals of the ring are umodules.
% Let us briefly present an example.
% 
% \subsection{Homogeneous relation based on a binary function}
% Let $f$ be a binary function $X\times X\to Y$.  The homogeneous relation 
% \emph{based on} $f$, written $H_f$, is defined as $H_f(s|ab)$ if and only if 
% $f(s,a)=f(s,b)$ and $f(a,s)=f(b,s)$.
% 
% For instance on graphs $f$ is the existence of an edge. On directed
% graph is the existence of an arc.  And on a 2-structures $f(x,y)$ is
% the number of equivalence class of the couple $(x,y)$. It can also be
% seen as a colouring of the edge $(x,y)$.
% 
% 
% Notice that weaker homogeneous relations can be defined from a binary
%  function: the \emph{left} homogeneous relation based on $f$, $H^l_f$,
%  is defined as $H^l_f(s|ab)$ if and only if $f(s,a)=f(s,b)$. And the \emph{right}
%  homogeneous relation based on $f$, $H^r_f$ ,is defined as
%  $H^r_f(s|ab)$ if and only if $f(a,s)=f(b,s)$. But these relation do not have the
%  quotient properties, and have not the same umodules. We have:
% 
% \begin{proposition}
% If $M$ is a umodule for  $H_f^r$ and for  $H_f^l$ then is a umodule for $H_f$.
% \end{proposition}
% The proof is immediate from definition. Notice that the converse is not true. 
% For instance for $X=\{a,b,c,d\}$ if $f(a,c)=f(a,d)$, $f(b,c)=f(b,d)$ and all 
% other couples have  pairwise different values, then $\{a,b\}$ is a umodule for 
% $H_f$ but neither for $H_f^l$ nor for  $H_f^r$. If $f$ is a symmetric function, 
% then the three homogeneous relations of course are the same. This is true for 
% graphs and for symmetric 2-structures, for instance.
% 
% \begin{proposition}
% The principal ideals of a ring are umodules (w.r.t. its multiplication 
% homogeneous relation).
% \end{proposition}
% 
% \subsection{Further work}
% 
In this paper we study umodular decomposition applied to graphs, when the local congruence is 2, the next challenge is now
 to understand  umodular decomposition of directed graphs or directed acyclic graphs, starting with the self-complemented case first.

Our  computation of strong umodules is polynomial, but its asymptotic
complexity of $O(|X|^4. \log(|X|))$ can surely be reduced, especially when applied to particular 
combinatorial objects. 


We have noticed here the great importance of  the Seidel switch operation, and following the notion of vertex minor as defined in \cite{Oum05a},
let us called $H$ a \emph{Seidel minor} of a graph $G$, if $H$ can be obtained from
$G$ by the two following operations: 
\begin{itemize} \vspace{-.1cm}
\item
delete a vertex, 
\item choose a vertex and do a Seidel switch on this vertex
\end{itemize} \vspace{-.1cm}
It could be of interest to study  such Seidel minors.

%Then our results can be rephrased as:
%\begin{enumerate}
%\item
%Let $G$ be an undirected graph, $G$ is totally decomposable via the bi-join decomposition if and only if $G$ has no seidel minor isomorphic to a $P_4$.
%\item
%Let $T$ be a tournament, $G$ is totally decomposable via umodular decomposition if and only if $T$ has no seidel minor isomorphic to a $C_3$.
%\end{enumerate}

% 
% \section{Questions ?}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 
% \begin{algorithm}
% \KwData{A tournament $T=(V,A)$ totally umodular decomposable.}
% \KwResult{The size of minimum feedback arc set of $T$.}
% \dontprintsemicolon
% \SetKw{Min}{Min}
% \SetKw{V}{Vertex}
% \SetKw{ve}{v}
% %%%%%%
% \Begin{
% \Min $\leftarrow~ n(n-1)/2$ \;
% \V $\leftarrow~ \emptyset$\;
% 
% \ForEach{$x \in V$}
% {
% A $\leftarrow~ N^+(X)$ \;
% B $\leftarrow~ N^-(X)$ \;
% 
% \ve $\gets$ $min(|\overrightarrow{AB}|,|\overrightarrow{xA}|+|\overrightarrow{BA}|,
% 	|\overrightarrow{Bx}|+|\overrightarrow{BA}|)$�\;
% 	\If{ \ve $<$ \Min}
% 	{
% 		\Min $\leftarrow~ $ \ve \;
% 		\V $\leftarrow~ x$ \;
% 	}
% 	\Return{(\Min,\V)}\;
% }
% }
% %%%%%%
% \caption{\label{algo:MinimumFeedbackArcSet} minimum feed back arc set ?}
% \end{algorithm}
% Question, la solution obtenue est-elle optimale, si oui/non pourquoi ?
% 
% \cite{Alon06,CharbitTY07}
{
\small
\bibliography{ShortUmodule}
\bibliographystyle{plain}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}

ShortUmodule.bbl
\begin{thebibliography}{10}

\bibitem{BJG01}
J.~Bang-Jensen and G.~Gutin.
\newblock {\em Digraphs: Theory, Algorithms and Applications}.
\newblock Springer Monographs in Mathematics. Springer-Verlag, 2001.

\bibitem{BLS99}
A.~Brandstadt, V.B. Le, and J.P. Spinrad.
\newblock {\em Graph Classes: A Survey}.
\newblock SIAM Monographs on Discrete Mathematics and Applications. Society for
  Industrial and Applied Mathematics, 1999.

\bibitem{BuixuanHLdM06}
B.-M. Bui-Xuan, M.~Habib, V.~Limouzy, and F.~de~Montgolfier.
\newblock Algorithmic aspects of a novel modular decomposition theory.
\newblock Technical report, \url{http://hal.archives-ouvertes.fr/hal-00111235},
  2006.
\newblock Submitted.

\bibitem{wg06}
B.-M. Bui~Xuan, M.~Habib, V.~Limouzy, and F.~de~Montgolfier.
\newblock Homogeneity vs. adjacency: generalising some graph decomposition
  algorithms.
\newblock In {\em 32nd International Workshop on Graph-Theoretic Concepts in
  Computer Science (WG)}, volume 4271 of {\em LNCS}, June 2006.

\bibitem{odsa2006}
B.-M. Bui-Xuan, M.~Habib, V.~Limouzy, and F.~de~Montgolfier.
\newblock On modular decomposition concepts: the case for homogeneous
  relations.
\newblock {\em Electronic Notes in Discrete Mathematics}, 27, 2006.

\bibitem{BuixuanHLdM07a}
B.-M. Bui-Xuan, M.~Habib, V.~Limouzy, and F.~de~Montgolfier.
\newblock A new tractable decomposition.
\newblock Technical report, \url{http://hal-lirmm.ccsd.cnrs.fr/lirmm-00157502},
  2007.

\bibitem{CHM81}
M.~Chein, M.~Habib, and M.~C. Maurer.
\newblock Partitive hypergraphs.
\newblock {\em Discrete Mathematics}, 37(1):35--50, 1981.

\bibitem{Clarou96}
E.~Clarou.
\newblock {\em Une hi\'erarchie de for\c cage pour les tournois
  ind\'ecomposables}.
\newblock PhD thesis, Universit\'e Claude Bernard Lyon I, 1996.

\bibitem{ColbournC80}
C.~J. Colbourn and D.~G. Corneil.
\newblock On deciding switching equivalence of graphs.
\newblock {\em Discrete Applied Mathematics}, 2(3):181--184, 1980.

\bibitem{DC07}
D.~G. Corneil.
\newblock Private communication.
\newblock Dagstuhl, 2007.

\bibitem{Cun73}
W.~H. Cunningham.
\newblock {\em A combinatorial decomposition theory}.
\newblock PhD thesis, University of Waterloo, Waterloo, Ontario, Canada, 1973.

\bibitem{EhrenfeuchtHR99}
A.~Ehrenfeucht, T.~Harju, and G.~Rozenberg.
\newblock {\em The Theory of 2-Structures- A Framework for Decomposition and
  Transformation of Graphs}.
\newblock World Scientific, 1999.

\bibitem{ER90}
A.~Ehrenfeucht and G.~Rozenberg.
\newblock Theory of 2-structures.
\newblock {\em Theoretical Computer Science}, 3(70):277--342, 1990.

\bibitem{EverettB91}
M.~G. Everett and S.~P. Borgatti.
\newblock Role colouring a graph.
\newblock {\em Mathematical Social Sciences}, 21:183--188, 1991.

\bibitem{FP03}
J.~Fiala and D.~Paulusma.
\newblock The computational complexity of the role assignment problem.
\newblock In {\em 30th International Colloquium on Automata, Languages and
  Programming (ICALP)}, pages 817--828, 2003.

\bibitem{Gabow93}
H.~N. Gabow.
\newblock A representation for crossing set families with applications to
  submodular flow problems.
\newblock In {\em Proceedings of the Fourth Annual ACM-SIAM Symposium on
  Discrete Algorithms (SODA)}, pages 202--211. ACM/SIAM, 1993.

\bibitem{Gal67}
T.~Gallai.
\newblock Transitiv orientierbare {G}raphen.
\newblock {\em Acta Math. Acad. Sci. Hungar.}, 18:25--66, 1967.

\bibitem{HM85}
M.~Habib and M.~C. Maurer.
\newblock 1-intersecting families.
\newblock {\em Discrete Mathematics}, 53:91--101, 1985.

\bibitem{Hayward96}
R.~B. Hayward.
\newblock Recognizing{\it } ${\mbox{3}}$-structure: A switching approach.
\newblock {\em Journal of Combinatorial Theory, Serie B}, 66(2):247--262, 1996.

\bibitem{Hertz99}
A.~Hertz.
\newblock On perfect switching classes.
\newblock {\em Discrete Applied Mathematics}, 94(1-3):3--7, 1999.

\bibitem{HMC03}
W.-L. Hsu and R.~M. McConnell.
\newblock {PC}-trees and circular-ones arrangements.
\newblock {\em Theoretical Computer Science}, 296:99--116, 2003.

\bibitem{KratochvilNZ92}
J.~Kratochv{\'{\i}}l, J.~Ne{\v{s}}et{\v{r}}il, and O.~Z{\'y}ka.
\newblock On the computational complexity of {S}eidel's switching.
\newblock In {\em Fourth Czechoslovakian Symposium on Combinatorics, Graphs and
  Complexity (Prachatice, 1990)}, volume~51 of {\em Ann. Discrete Math.}, pages
  161--166. North-Holland, Amsterdam, 1992.

\bibitem{MR84}
R.~H. M\"ohring and F.~J. Radermacher.
\newblock Substitution decomposition for discrete structures and connections
  with combinatorial optimization.
\newblock {\em Annals of Discrete Mathematics}, 19:257--356, 1984.

\bibitem{M03}
F.~de Montgolfier.
\newblock {\em D\'{e}composition modulaire des graphes. Th\'{e}orie, extensions
  et algorithmes}.
\newblock PhD thesis, Universit\'e Montpellier II, 2003.

\bibitem{MontgolfierRaoICGT2005}
F.~de Montgolfier and M.~Rao.
\newblock The bi-join decomposition.
\newblock In {\em ICGT '05, 7th International Colloquium on Graph Theory},
  2005.

\bibitem{Oum05a}
S.-I. Oum.
\newblock Rank-width and vertex-minors.
\newblock {\em Journal of Combinatorial Theory, Series B}, 95(1):79--100, 2005.

\bibitem{MR917035}
R.~Paige and R.~E. Tarjan.
\newblock Three partition refinement algorithms.
\newblock {\em SIAM Journal on Computing}, 16(6):973--989, 1987.

\bibitem{Schrijver03}
A.~Schrijver.
\newblock {\em Combinatorial Optimization - Polyhedra and Efficiency}.
\newblock Springer-Verlag, 2003.

\bibitem{Seidel76}
J.~J. Seidel.
\newblock A survey of two-graphs.
\newblock In {\em Colloquio Internazionale sulle Teorie Combinatorie (Rome,
  1973), Tomo I}, pages 481--511. Atti dei Convegni Lincei, No. 17. Accad. Naz.
  Lincei, Rome, 1976.

\bibitem{WhiteR83}
D.~R. White and K.~P. Reitz.
\newblock Graph and semigroup homomorphisms on networks of relations.
\newblock {\em Social Networks}, 5:193--234, 1983.

\end{thebibliography}
