The independence number of a tree decomposition T of a graph is the smallest integer k such that each bag of T induces a subgraph with independence number at most k. If a graph is given together with a tree decomposition with a 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 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 Martin Milanič and Kenny Štorgel.

We are looking forward to meeting you at FAMNIT-MP1. 

This Monday, November 22,  2021, from 10 am to 11 am.

Our Math Research Seminar will also be broadcasted via Zoom.

Join Zoom Meeting Here.

 Everyone is welcome and encouraged to attend.