Detecting 2-joins faster

Abstract

2-joins are edge cutsets that naturally appear in the decomposition of several classes of graphs closed under taking induced subgraphs, such as balanced bipartite graphs, even-hole-free graphs, perfect graphs and claw-free graphs. Their detection is needed in several algorithms, and is the slowest step for some of them. The classical method to detect a 2-join takes $O(n^{3}m)$ time where $n$ is the number of vertices of the input graph and $m$ the number of its edges. To detect \emph{non-path} 2-joins (special kinds of 2-joins that are needed in all of the known algorithms that use 2-joins), the fastest known method takes time $O(n^{4}m)$. Here, we give an $O(n^{2}m)$-time algorithm for both of these problems. A consequence is a speed up of several known algorithms.

References in corpus (2)

• Combinatorial optimization with 2-joins
• Decomposing Berge graphs and detecting balanced skew partitions

Cited by in corpus (9)

• Combinatorial optimization with 2-joins
• Three-in-a-Tree in Near Linear Time
• A Faster Algorithm to Recognize Even-Hole-Free Graphs
• Perfect graphs: a survey
• Coloring perfect graphs with no balanced skew-partitions
• The (theta, wheel)-free graphs Part I: only-prism and only-pyramid graphs
• The (theta, wheel)-free graphs Part IV: induced paths and cycles
• Colouring perfect graphs with bounded clique number
• The (theta, wheel)-free graphs Part III: cliques, stable sets and coloring