Martin Milanič, Tree Decompositions with Bounded Independence Number

The independence number of a tree decomposition $\mathcal{T}$ of a graph is the smallest integer $k$ such that each bag of $\mathcal{T}$ induces a subgraph with independence number at most $k$. If a graph $G$ is given together with a tree decomposition with bounded independence number, then the Maximum Weight Independent Set (MWIS) problem can be solved in polynomial time. Motivated by this observation, we consider six graph containment relations—the subgraph, topological minor, and minor relations, as well as their induced variants—and for each of them characterize the graphs $H$ for which any graph excluding $H$ with respect to the relation admits a tree decomposition with bounded independence number. Furthermore, using a variety of tools including SPQR trees and potential maximal cliques, we show how to obtain such tree decompositions efficiently.

As an immediate consequence, we obtain that the MWIS problem can be solved in polynomial time in an infinite family of graph classes that properly contain the class of chordal graphs. In fact, our approach shows that the Maximum Weight Independent $\mathcal{H}$-Packing problem, a common generalization of the MWIS and the Maximum Weight Induced Matching problems, can be solved in polynomial time in these graph classes.

This is joint work with Clément Dallard and Kenny Štorgel.