REVIEW 2 cited by
Polynomial-time approximation schemes for induced subgraph problems on fractionally tree-independence-number-fragile graphs
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
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 $\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.
Forward citations
Cited by 2 Pith papers
-
Subdivided expanders and counterexamples to the Tree Product Conjecture
For every integer d≥2, the paper constructs graphs of degree-d polynomial growth whose balanced separators are too large by a logarithmic factor to fit in the conjectured product structure.
-
Layered tree-independence number and clique-based separators
Map graphs, hyperbolic uniform disk graphs, and spherical uniform disk graphs are shown to have bounded or radius-dependent layered tree-independence number, yielding new weighted subexponential algorithms.
Discussion (0). Continue with ORCID to comment.