On the Complexity of Dissociation Set Problems in Graphs
Information Control Problems in Manufacturing, Volume # 13 | Part# 1
Orlovich, Yuri; Dolgui, Alexandre; Finke, Gerd; Gordon, Valery; Werner, Frank
Digital Object Identifier (DOI)
Computational Science; Discrete Applied Mathematics; Graph theory
A subset of vertices in a graph is called a dissociation set if it induces a subgraph with vertex degree at most 1. A dissociation set D is maximal if no other dissociation set contains D. The complexity of finding a dissociation set of maximum size in line graphs and finding a maximal dissociation set of minimum size in general graphs is considered.
REFERENCES Alekseev, V.E. (2004). Polynomial algorithm for finding the largest independent sets in graphs without forks. Discrete Applied Mathematics, 135, 3–16. Boliac, R., Cameron, K., and Lozin, V. (2004). On computing the dissociation number and the induced matching number of bipartite graphs. Ars Combinatoria, 72, 241–253. Brandstädt, A., Le, V.B., and Spinrad, J.P. (1999). Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia, PA. Garey, M.R. and Johnson, D.S. (1979). Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman and Co., San Francisco, CA. Golumbic, M.C. and Lewenstein, M. (2000). New results on induced matchings. Discrete Applied Mathematics, 101, 157–165. Harary, F. and Holzmann, C. (1974). Line graphs of bipartite graphs. Review of the Society of Mathematics of Chile, 1, 19–20. Haynes, T.W., Hedetniemi, S.T., and Slater, P.J. (1998). Fundamentals of Domination in Graphs. Marcel Dekker, Inc., New York, NY. Kirkpatrick, D.G. and Hell, P. (1978). On the complexity of a generalized matching problem. Proceedings of the 10th Annual ACM Symposium on Theory of Computing. ACM, New York, 240–245. Lozin, V. and Milanic, M. (2008). A polynomial algorithm to find an independent set of maximum weight in a fork-free graph. Journal of Discrete Algorithms, 6, 595–604. Lozin, V. and Rautenbach, D. (2003). Some results on graphs without long induced paths. Information Processing Letters, 88, 167–171. Orlovich, Yu., Finke, G., Gordon, V., and Zverovich, I. (2008). Approximability results for the maximum and minimum maximal induced matching problems. Discrete Optimization, 5, 584–593. Papadimitriou, C.H. and Yannakakis, M. (1982). The complexity of restricted spanning tree problems. Journal of the ACM, 29, 285–309. Yannakakis, M. (1981). Node-deletion problems on bipartite graphs. SIAM Journal of Computing, 10, 310– 327.