Abstract
We show that for an integer k ≥ 2 and an n-vertex graph G without a K 3,3 (resp., K 5) minor, we can compute k induced subgraphs of G with treewidth ≤ 3k−4 (resp., ≤ 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 problems on graphs without a K 3,3 or K 5 minor. 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.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
N. Alon, P. Seymour, and R. Thomas, A separator theorem for graphs without an excluded minor and its applications, STOC'90.
T. Asano, An approach to the subgraph homeomorphism problem, TCS 38 (1985).
H.L. Bodlaender, Planar graphs with bounded treewidth, Technical Report.
H.L. Bodlaender, Dynamic programming algorithms on graphs with bounded treewidth, ICALP'88, LNCS 317.
B.S. Baker, Approximation algorithms for NP-complete problems on planar graphs, J. ACM 41 (1994).
N. Chiba, T. Nishizeki, and N. Saito, An approximation algorithm for the maximum independent set problem on planar graphs, SIAM-JC 11 (1982).
D. Eppstein, Subgraph isomorphism in planar graphs and related problems, SODA '95.
D.W. Hall, A note on primitive skew curves, Bull. Amer. Math. Soc. 49 (1943).
J. E. Hopcroft and R. E. Tarjan, Dividing a graph into triconnected components, SIAM-JC 2 (1973), 135–158.
A. Kanevsky and V. Ramachandran, Improved algorithms for graph four-connectivity, FOCS'87.
A. Kézdy and P. McGuinness, Sequential and parallel algorithms to find a K 5, minor, SODA'92.
R. J. Lipton and R. E. Tarjan, Applications of a planar separator theorem, SIAM-JC 9 (1980), 615–627.
N. Robertson and P.D. Seymour, Graph minors V. Excluding a planar graph, J. Combinatorial Theory Ser. B 41 (1986).
J.A. Telle and A. Proskurowski, Practical algorithms on partial k-trees with an application to domination-like problems, WADS'93, LNCS 709.
M. Yannakakis, Node-and edge-deletion NP-complete problems, STOC'78.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chen, ZZ. (1996). Practical approximation schemes for maximum induced-subgraph problems on K 3,3-free or K 5-free graphs. In: Meyer, F., Monien, B. (eds) Automata, Languages and Programming. ICALP 1996. Lecture Notes in Computer Science, vol 1099. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61440-0_134
Download citation
DOI: https://doi.org/10.1007/3-540-61440-0_134
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61440-1
Online ISBN: 978-3-540-68580-7
eBook Packages: Springer Book Archive