This talk deals with induced minor obstructions to treewidth. The natural setup for this problem is to consider the class of graphs excluding some planar graph, and some complete bipartite graph as induced minors, and some complete graph as a subgraph. Unfortunately, such classes still contain graphs of arbitrarily large treewidth. Moreover, a result of Alecu, Bonnet, Bureo Villafana and Trotignon and its extensions suggest that there is no elegant characterization of families of bounded treewidth in terms of induced obstructions.
On the other hand, it is conjectured that graphs in the classes as above have treewidth bounded by a poly-logarithmic function of their number of vertices. If true, this will imply the existence of quasi-polynomial time algorithms for a host of problems on such classes that are NP-complete in the general setting.
While this conjecture remains open, in joint work with Julien Codsi, David Fischer and Daniel Lokshtanov, we were able to prove the existence of a sub-polynomial bound on treewidth in terms of the number of vertices. This in turn leads to sub-exponential algorithmic behavior.
In this talk we will discuss some ideas of the proof, and, if time permits, some results in the more general setting when the bound on the clique size is removed.
On June 11, 2024, Maria Chudnovsky from Princeton University gave a talk at the Discrete Math Seminar on finding the disjoint union of two graphs of large treewidth as an induced subgraph. The title of her talk was “Anticomplete subgraphs of large treewidth“.
We will discuss recent progress on the topic of induced subgraphs and tree-decompositions. In particular this talk with focus on the proof of a conjecture of Hajebi that asserts that (if we exclude a few obvious counterexamples) for every integer t, every graph with large enough treewidth contains two anticomplete induced subgraphs each of treewidth at least t. This is joint work with Sepher Hajebi and Sophie Spirkl.
On May 11, 2023, Maria Chudnovsky from Princeton University gave a colloquium talk held at KAIST about bounding the tree-width of graphs by forbidding induced subgraphs. The titlte of her talk was “Induced subgraphs and tree decompositions.”
Tree decompositions are a powerful tool in both structural graph theory and graph algorithms. Many hard problems become tractable if the input graph is known to have a tree decomposition of bounded “width”. Exhibiting a particular kind of a tree decomposition is also a useful way to describe the structure of a graph. Tree decompositions have traditionally been used in the context of forbidden graph minors; bringing them into the realm of forbidden induced subgraphs has until recently remained out of reach. Over the last couple of years we have made significant progress in this direction, exploring both the classical notion of bounded tree-width, and concepts of more structural flavor. This talk will survey some of these ideas and results.
On July 28, 2021, Maria Chudnovsky from Princeton University gave an online talk at the Virtual Discrete Math Colloquium on structural aspects of graphs of large tree-width in terms of induced subgraphs. The title of her talk was “Induced subgraphs and tree decompositions“.
Tree decompositions are a powerful tool in structural graph theory; they are traditionally used in the context of forbidden graph minors. Connecting tree decompositions and forbidden induced subgraphs has until recently remained out of reach.
Tree decompositions are closely related to the existence of “laminar collections of separations” in a graph, which roughly means that the separations in the collection “cooperate” with each other, and the pieces that are obtained when the graph is simultaneously decomposed by all the separations in the collection “line up” to form a tree structure. Such collections of separations come up naturally in the context of forbidden minors.
In the case of families where induced subgraphs are excluded, while there are often natural separations, they are usually very far from forming a laminar collection. In what follows we mostly focus on families of graphs of bounded degree. It turns out that due to the bound on the degree, these collections of natural separations can be partitioned into a bounded number of laminar collections. This in turn allows to us obtain a wide variety of structural and algorithmic results, which we will survey in this talk.
