Skip to Main content Skip to Navigation
Reports

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.
Complete list of metadatas

Cited literature [40 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00157502
Contributor : Binh-Minh Bui-Xuan <>
Submitted on : Monday, December 17, 2007 - 9:58:18 AM
Last modification on : Friday, March 27, 2020 - 4:01:46 AM
Long-term archiving on: : Friday, November 25, 2016 - 6:36:05 PM

Identifiers

  • HAL Id : lirmm-00157502, version 2

Citation

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

Share

Metrics

Record views

670

Files downloads

220