Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth

Treewidth is a graph paramater which measures how close a graph is to being a tree. Graphs with treewidth equal to one are forests, and a graph has treewidth at most two if and only if it is a series-parallel graph, or equivalently it is a subgraph of a graph that can be obtained from a triangle by gluing triangles along edges in a tree-like fashion. The notion of treewidth is linked to fundamental results in graph minor theory, in particular, the Graph Structure Theorem, and it is also of substantial importance in computer science as graphs with bounded treewidth admit efficient dynamic programming algorithms for many NP-hard problems. The latter is formally captured by Courcelle’s Theorem, which asserts that every graph property expressible in monadic second order logic can be tested in linear time for graphs with bounded treewidth.

Since the property of having treewidth at most a fixed integer $k$ is a minor closed graph property, the Robertson-Seymour Theorem implies that graphs with treewidth at most $k$ can be characterized by a finite list of forbidden minors. This paper is concerned with the interplay between treewidth and forbidden subgraphs. Note that the property of having treewidth at most $k$ cannot be characterized by a finite list of forbidden (induced) subgraphs. However, the main result of the paper asserts that graphs avoiding a triangle and a theta graph (three internally disjoint paths between a pair of vertices) as an induced subgraph have treewidth bounded by a function logarithmic in their number of vertices (the logarithmic dependence is the best possible as shown by a lower bound construction due to Sintiari and Trotignon). More generally, the same holds for graphs avoiding a fixed complete graph and three-path configurations (a theta graph, a pyramid, a prism or a pinched prism). This in particular implies that a large range of NP-hard problems (e.g., dominating set, independent set, vertex coloring, and vertex cover) can be solvable by efficient algorithms for input graphs that belong to such classes.