Abstract
A bipartite graph G = (A ∪ B, E) is called a chain graph if there exists an ordering \(\rho=<\!v_1, v_2, \ldots v_n\!>\) of the vertices in A = {v 1,...,v n } such that N(v 1) ⊆ N(v 2) ... ⊆ N(v n ). Here N(v) denotes the set of neighbors of the vertex v in G. We call the vertex-deletion problem corresponding to the class of chain graphs as the Minimum Chain Vertex Deletion problem and the induced subgraph problem corresponding to chain graphs as the Maximum Induced Chain Subgraph problem. A weighted version of these problems is obtained by assigning positive weights on vertices and asking for a minimum weight deletion set to get into the class of chain graphs or asking for maximum weight induced chain subgraph. Using a rounding technique we show that the weighted version of Minimum Chain Vertex Deletion, has a factor 2 approximation algorithm on bipartite graphs. We also give a factor 3/2 approximation algorithm for a weighted version of Maximum Induced Chain Subgraph on bipartite graphs. We also show that both these problems are APX-complete.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arora, S., Lund, C.: Hardness of Approximations. In: Approximation Algorithms for NP-hard Problems, Dorit Hochbaum. PWS Publishing (1996)
Bafna, V., Berman, P., Fujito, T.: A 2-Approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discrete Math. 12(3), 289–297 (1999)
Feder, T., Mannila, H., Terzi, E.: Approximating the Minimum Chain Completion Problem. Information Processing letters 109, 980–985 (2009)
Feige, U., Goldwasser, S., Lovász, L., Safra, S., Szegedy, M.: Interactive proofs and the hardness of approximating cliques. J. ACM 43(2), 268–292 (1996)
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)
Khot, S., Regev, O.: Vertex Cover Might be Hard to Approximate to Within 2 − ε. Journal of Computer and System Sciences 74(3), 335–349 (2008)
Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. Journal of Computer and System Sciences 20(2), 219–230 (1980)
Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. the ACM 41, 960–981 (1994)
Natanzon, A., Shamir, R., Sharan, R.: A polynomial approximation algorithm for the minimum fill-in problem. SIAM Jr. Computing 30(4), 1067–1079 (2000)
Papadimitriou, C.H., Yannakakis, M.: Optimization, Approximation and Complexity Classes. Jr. Comput. System Sci. 43, 425–440 (1991)
Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001)
Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Alg. Disc. Meth. 2(1), 77–79 (1981)
Yannakakis, M.: Node deletion problems on bipartite graphs. SIAM Journal of Computing 10(2), 310–327 (1981)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kumar, M., Mishra, S., Devi, N.S., Saurabh, S. (2011). Approximation Algorithms for Minimum Chain Vertex Deletion. In: Katoh, N., Kumar, A. (eds) WALCOM: Algorithms and Computation. WALCOM 2011. Lecture Notes in Computer Science, vol 6552. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-19094-0_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-19094-0_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-19093-3
Online ISBN: 978-3-642-19094-0
eBook Packages: Computer ScienceComputer Science (R0)