A new tractable combinatorial decomposition

Abstract : This paper introduces the umodules, a generalisation of the notion of module in graph theory. The structure to be decomposed, so-called homogeneous relation, captures among other undirected graphs, tournaments, digraphs, and 2-structures. Our resulting decomposition scheme when restricted to undirected graphs generalises the well-studied modular graph decomposition, and meets the recently introduced bi-join decomposition. All other cases up to our knowledge lead to new notions. First some properties of the umodule family are presented. Polynomial-time algorithms for non-trivial umodule existence test and for maximal umodule computation are then provided. When the input structure fulfills 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 in theses two cases is linear in the size of the input structure. Besides, our work here can also be seen as a unification of the bi-join undirected graph decomposition and of a new tournament decomposition. 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 forbiding induced subgraphs, recognition, isomorphism testing, and feedback vertex set computation.
Type de document :
Rapport
RR-07016, 2007
Liste complète des métadonnées

Littérature citée [40 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00157502
Contributeur : Binh-Minh Bui-Xuan <>
Soumis le : lundi 17 décembre 2007 - 09:58:18
Dernière modification le : jeudi 24 mai 2018 - 15:59:21
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 18:36:05

Identifiants

  • HAL Id : lirmm-00157502, version 2

Collections

Citation

Binh-Minh Bui-Xuan, Michel Habib, Vincent Limouzy, Fabien De Montgolfier. A new tractable combinatorial decomposition. RR-07016, 2007. 〈lirmm-00157502v2〉

Partager

Métriques

Consultations de la notice

414

Téléchargements de fichiers

162