Decomposing Berge graphs and detecting balanced skew partitions

Abstract

A hole in a graph is an induced cycle on at least four vertices. A graph is Berge if it has no odd hole and if its complement has no odd hole. In 2002, Chudnovsky, Robertson, Seymour and Thomas proved a decomposition theorem for Berge graphs saying that every Berge graph either is in a well understood basic class, or has some kind of decomposition. Then, Chudnovsky proved stronger theorems. One of them restricts the allowed decompositions to 2-joins and balanced skew partitions. We prove that the problem of deciding whether a graph has a balanced skew partition is NP-hard. We give an $O(n^9)$-time algorithm for the same problem restricted to Berge graphs. Our algorithm is not constructive: it only certifies whether a graph has a balanced skew partition or not. It relies on a new decomposition theorem for Berge graphs that is more precise than the previously known theorems. 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 theorems of Chudnovsky.

Cited by in corpus (7)

• Combinatorial optimization with 2-joins
• Three-in-a-Tree in Near Linear Time
• A Faster Algorithm to Recognize Even-Hole-Free Graphs
• Coloring perfect graphs with no balanced skew-partitions
• Clique-Stable Set separation in perfect graphs with no balanced skew-partitions
• Colouring perfect graphs with bounded clique number
• Structure of classes of graphs defined by forbidding induced subgraphs