A new tractable combinatorial decomposition - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Reports Year : 2007

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.
Fichier principal
Vignette du fichier
BHLM07_umodules.pdf (366.38 Ko) Télécharger le fichier
Loading...

Dates and versions

lirmm-00157502 , version 1 (26-06-2007)
lirmm-00157502 , version 2 (17-12-2007)

Identifiers

  • HAL Id : lirmm-00157502 , version 2

Cite

Binh-Minh Bui-Xuan, Michel Habib, Vincent Limouzy, Fabien de Montgolfier. A new tractable combinatorial decomposition. RR-07016, 2007. ⟨lirmm-00157502v2⟩
339 View
175 Download

Share

Gmail Facebook X LinkedIn More