Raziskovalni matematični seminar
Raziskovalni matematični seminar poteka v organizaciji oddelkov za matematiko dveh članic Univerze na Primorskem - UP FAMNIT in Inštituta Andrej Marušič (UP IAM), in sicer vsak ponedeljek od oktobra do junija.
Vljudno vabljeni k udeležbi na prihodnjih seminarjih!
Datum in ura / Date and time: 8.4.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Andrea Munaro (University of Parma)
Naslov / Title: Polynomial-time approximation schemes for induced subgraph problems on fractionally tree-independence-number-fragile graphs
Vsebina / Abstract:
We investigate a relaxation of the notion of fractional treewidth-fragility, namely fractional tree-independence-number-fragility. In particular, we obtain polynomial-time approximation schemes for meta-problems such as finding a maximum-weight sparse induced subgraph satisfying a given CMSO_2 formula on fractionally tree-independence-number-fragile graph classes. Our approach unifies and extends several known polynomial-time approximation schemes on seemingly unrelated graph classes, such as classes of intersection graphs of fat objects in a fixed dimension or proper minor-closed classes. We also study the related notion of layered tree-independence number, a relaxation of layered treewidth, and its applications to exact subexponential-time algorithms.
Joint work with Esther Galby and Shizhou Yang.
