Decomposing Berge graphs and detecting balanced skew partitions

Nicolas Trotignon ()
Additional contact information
Nicolas Trotignon: CES - Centre d'économie de la Sorbonne - UP1 - Université Paris 1 Panthéon-Sorbonne - CNRS - Centre National de la Recherche Scientifique

Post-Print from HAL

Abstract: We prove that the problem of deciding whether a graph has a balanced skew partition is NP-hard. We give an O(n9)-time algorithm for the same problem restricted to Berge graphs. Our algorithm is not constructive: it certifies that a graph has a balanced skew partition if it has one. It relies on a new decomposition theorem for Berge graphs, that is more precise than the previously known theorems and implies them easily. Our theorem also implies that every Berge graph can be decomposed in a first step by using only balanced skew partitions, and in a second step by using only 2-joins. Our proof of this new theorem uses at an essential step one of the decomposition theorems of Chudnovsky.

Keywords: Berge graph; Perfect graph; 2-join; detection; recognition; balanced skew partition; decomposition; graphe de Berge; décomposition; reconnaissance; détection; Graphe parfait (search for similar items in EconPapers)
Date: 2006-04
Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-00115625
References: View complete reference list from CitEc
Citations:

Published in 2006

Downloads: (external link)
https://shs.hal.science/halshs-00115625/document (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:halshs-00115625

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().