Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2303.07444 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915252626522112 |
|---|---|
| author | Galby, Esther Munaro, Andrea Yang, Shizhou |
| author_facet | Galby, Esther Munaro, Andrea Yang, Shizhou |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_07444 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs Galby, Esther Munaro, Andrea Yang, Shizhou Data Structures and Algorithms Computational Geometry Combinatorics 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. |
| title | Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs |
| topic | Data Structures and Algorithms Computational Geometry Combinatorics |
| url | https://arxiv.org/abs/2303.07444 |