EFFICIENT APPROXIMATION SCHEMES FOR MAXIMIZATION PROBLEMS ON K-3,K-3-FREE OR K-5-FREE GRAPHS

We show that for any integer k greater than or equal to 2 and any n-ve rtex graph G without a K-3,K-3 (or K-5) minor, one can compute k induc ed subgraphs of G with treewidth no more than 3k - 4 (respectively, 6k - 7) in O(kn) (respectively, O(kn + n(2))) time such that each vertex of G appears in exactly k - 1 of these subgraphs. This leads to pract ical polynomial-time approximation schemes for various maximum induced -subgraph problems on graphs without a K-3,K-3 (respectively, K-5) min or. The result extends the well-known practical polynomial-time approx imation schemes of Baker for various maximum induced-subgraph problems on planar graphs. (C) 1998 academic Press.