Approximation Schemes for Bounded Distance Problems on Fractionally Treewidth-Fragile Graphs

Abstract

We give polynomial-time approximation schemes for monotone maximization problems expressible in terms of distances (up to a fixed upper bound) and efficiently solvable on graphs of bounded treewidth. These schemes apply in all fractionally treewidth-fragile graph classes, a property which is true for many natural graph classes with sublinear separators.

We also provide quasipolynomial-time approximation schemes for these problems in all classes with sublinear separators.

Keywords

• Approximation
• Schemes
• for
• Bounded
• Distance
• Problems
• Fractionally
• Treewidth-Fragile
• Graphs