***********************************
* 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)