Combinatorial optimization with 2-joins

Abstract

A 2-join is an edge cutset that naturally appears in decomposition of several classes of graphs closed under taking induced subgraphs, such as perfect graphs and claw-free graphs. In this paper we construct combinatorial polynomial time algorithms for finding a maximum weighted clique, a maximum weighted stable set and an optimal coloring for a class of perfect graphs decomposable by 2-joins: the class of perfect graphs that do not have a balanced skew partition, a 2-join in the complement, nor a homogeneous pair. The techniques we develop are general enough to be easily applied to finding a maximum weighted stable set for another class of graphs known to be decomposable by 2-joins, namely the class of even-hole-free graphs that do not have a star cutset. We also give a simple class of graphs decomposable by 2-joins into bipartite graphs and line graphs, and for which finding a maximum stable set is NP-hard. This shows that having holes all of the same parity gives essential properties for the use of 2-joins in computing stable sets.

References in corpus (3)

• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Decomposing Berge graphs and detecting balanced skew partitions
• Odd pairs of cliques

Cited by in corpus (11)

• Parameterized algorithm for weighted independent set problem in bull-free graphs
• 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
• The (theta, wheel)-free graphs Part IV: induced paths and cycles
• The (theta, wheel)-free graphs Part III: cliques, stable sets and coloring
• Coloring even-hole-free graphs with no star cutset
• Stable sets in {ISK4,wheel}-free graphs
• Linear balanceable and subcubic balanceable graphs
• On the Linear Extension Complexity of Stable Set Polytopes for Perfect Graphs
• Structure of classes of graphs defined by forbidding induced subgraphs