Polynomial-time approximation schemes for induced subgraph problems on fractionally tree-independence-number-fragile graphs
<|reference_start|>Polynomial-time approximation schemes for induced subgraph problems on fractionally tree-independence-number-fragile graphs: 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 $\mathsf{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.<|reference_end|>
@article{galby2024polynomial-time,
    title={Polynomial-time approximation schemes for induced subgraph problems on
  fractionally tree-independence-number-fragile graphs},
    author={Esther Galby and Andrea Munaro and Shizhou Yang},
    journal={arXiv preprint arXiv:2402.18352},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.18352},
    primaryClass={cs.DS cs.CG math.CO}
}