BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20200101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211105T163000
DTEND;TZID=Asia/Seoul:20211105T173000
DTSTAMP:20260420T010659
CREATED:20211105T073000Z
LAST-MODIFIED:20240707T080839Z
UID:4555-1636129800-1636133400@dimag.ibs.re.kr
SUMMARY:Martin Milanič\, Tree Decompositions with Bounded Independence Number
DESCRIPTION: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. \nAs 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. \nThis is joint work with Clément Dallard and Kenny Štorgel.
URL:https://dimag.ibs.re.kr/event/2021-11-05/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR