***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Martin Milanic (U Primorska, Koper, Slovenia)

Thursday 26th January, 3:00 via Zoom.

Title: Tree decompositions with bounded independence number and their 
algorithmic applications

The independence number of a tree decomposition of a graph is the
smallest integer k such that each bag 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. More generally, 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 Clément Dallard and Kenny Storgel.

		----------------------------------

Next week: TBA

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)