BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

(Theta, wheel)-free graphs Vuskovic, Kristina


A theta is a subdivision of $K_{2,3}$, and a wheel is a graph that consist of a chorldless cycle of length at least 4 and a vertex that has at least 3 neighbors on the cycle. In recently completed joint work with Trotignon and Radovanovic we obtained a structure theorem for graphs that do not contain thetas and wheels as induced subgraphs (i.e. (theta, wheel)-free graphs) and several of its algorithmic consequences.

We decompose (theta, wheel)-free graphs using clique cutsets and 2-joins into graphs that are essentially formed of a line graph of a triangle-free chordless graph plus a (possibly empty) clique (that attaches to the rest of the graph in a particular way). A 2-join is an edge cutset that appears in decomposition theorems for several complex hereditary classes, such as perfect graphs, even-hole-free graphs and others. In these decomposition theorems 2-joins are used together with vertex cutsets that are stronger than clique cutsets, such as star cutsets and their generalizations (which are much harder to use in algorithms). This is a first example of a decomposition theorem that uses just the combination of clique cutsets and 2-joins. This has several consequences.

First, we can easily transform our decomposition theorem into a complete structure theorem for (theta, wheel)-free graphs, i.e. we show how every graph in the class can be built starting from basic graphs that can be explicitly constructed, and gluing them together by prescribed composition operations, and all graphs built this way are in the class. Such structure theorems are rare for hereditary graph classes, only a few examples are known.

Next, we construct a polynomial-time decomposition-based recognition algorithm. Recognizing classes of graphs defined by excluding different combinations of Truemper configurations (i.e. wheels, thetas, prisms and pyramids) is a much studied problem. For some combinations the problem is known to be polynomial (e.g. recognizing pyramids and thetas), whereas for others it is NP-complete (e.g. recognizing prisms and wheels). The class of (theta, wheel)-free graphs was the last of these types of recognition problems that was open, and we now resolve.

We then use the decomposition theorem to obtain polynomial-time algorithms for weighted stable set, weighted clique and vertex coloring problems. For the weighted stable set problem, it was essential to decompose the graph using a sequence of non-crossing 2-joins. The weighted clique problem we solve by first showing the existence of a bisimplicial vertex (a vertex whose neighborhood partitions into 2 cliques). This is done elegantly by using the existence of an extreme 2-join (a 2-join whose one block of decomposition does not have a 2-join). We also prove that every (theta, wheel)-free graph with maximum clique size $\omega$ admits a coloring with at most max$\{\omega ,3\}$ colors.

Finally, we obtain a polynomial-time algorithm for the induced version of the $k$-linkage problem (for fixed $k$): given $k$ distinct pairs of vertices $(s_i,t_i)$ of a graph $G$, decide whether there are $k$ vertex-disjoint paths $P_i=s_i \ldots t_i$, $i=1, \ldots ,k$, such that there are no edges between the vertices of these paths.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International