Options
Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs
Citation Link: https://doi.org/10.15480/882.9391
Publikationstyp
Conference Paper
Date Issued
2023-06
Sprache
English
Author(s)
TORE-DOI
First published in
Number in series
Volume
258
Article Number
34
Citation
International Symposium on Computational Geometry (SoCG 2023)
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Dagstuhl Publishing
ISBN
9783959772730
We investigate a relaxation of the notion of treewidth-fragility, namely tree-independence-number-fragility. In particular, we obtain polynomial-time approximation schemes for independent packing problems 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.
Subjects
Independent packings
intersection graphs
polynomial-time approximation schemes
tree-independence number
DDC Class
510: Mathematics
Publication version
publishedVersion
Loading...
Name
LIPIcs.SoCG.2023.34.pdf
Type
Main Article
Size
783.09 KB
Format
Adobe PDF