We show that for an integer K large than or equal to 2 and an n-vertex graph G without a K sub 3,3 minor, we can compute k induced subgraphs of G with treewidth less than or equal to 3k-4 in O(kn) 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-subgraphs problems on graphs without a K sub 3,3 or K sub 5 minor. The result extends a well-known results of Baker that there are practical polynomial-time approximation schemes for various maximum induced-subgraph problems on planar graphs.
展开▼
机译：我们表明，对于一个大于或等于2的整数K和一个没有K sub 3,3 minor的n顶点图G，我们可以计算出树形宽度小于或等于3k-4的G的k个诱导子图。 kn）时间，以使G的每个顶点恰好出现在这些子图的k-1中。对于没有K sub 3,3或K sub 5 minor的图，这导致了针对各种最大诱导子图问题的实用多项式时间近似方案。该结果扩展了Baker的著名结果，即对于平面图上的各种最大诱导子图问题，存在实用的多项式时间近似方案。
展开▼
