Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs
| Autor: | Galby, Esther, Munaro, Andrea, Yang, Shizhou |
|---|---|
| Rok vydání: | 2023 |
| Předmět: |
Computational Geometry (cs.CG)
FOS: Computer and information sciences Independent packings Computer Science - Data Structures and Algorithms FOS: Mathematics Computer Science - Computational Geometry Mathematics - Combinatorics Data Structures and Algorithms (cs.DS) polynomial-time approximation schemes tree-independence number Combinatorics (math.CO) intersection graphs Theory of computation → Approximation algorithms analysis |
| DOI: | 10.48550/arxiv.2303.07444 |
| Popis: | 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. Comment: Full version of a paper to appear in a shorter form in the 39th International Symposium on Computational Geometry (SoCG 2023) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|