Decomposing Berge graphs and detecting balanced skew partitions (Q2464161)

A hole in a graph is an induced cycle of order at least 4. A Berge graph has no odd holes in either itself or its complement. The author shows that the problem of deciding whether a graph has a balanced skew partition is NP-hard, but gives an \(O(n^9)\)-time algorithm for the same problem restricted to Berge graphs. The 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, which also implies that every Berge graph can be decomposed first by using only balanced skew partitions and then by using only 2-joins.