Sequential and Parallel Approximation of Maximum Induced-Subgraph Problems on Sparse Graphs
Zhi‐Zhong Chen · Institutional Repositories DataBase (IRDB) · 1996
We show that for an integer $k$ $\geq$ 2 and an $n$ -vertex graph $G$ without a $\mathrm{A}_{3,3}^{r}$ (resp., $I\iota_{5}^{r})$ minor, we can compute $k$ induced sub- graphs of $G$ with treewidth $\leq 3k-4$ (resp., $\leq 6k-7)$ in $O(kn)$ (resp., $O(kn+n^{2})$ ) time such that each vertex of $G$ appears in exactly $k-1$ of these subgraphs.This leads to practical polynomial-time approximation schemes for various maximum induced-subgraph prob- lems on graphs without a $I\iota_{3,3}^{ earrow}$ or $I\iota_{5}'$ mi- nor.The result extends a well-known result of Baker that there are practical polynomial-time approximation schemes for various maximum induced-subgraph problems on planar graphs.