Abstract
This paper discusses the complexity of packingk-chains (simple paths of lengthk) into an undirected graph; the chains packed must be either vertex-disjoint or edge-disjoint. Linear-time algorithms are given for both problems when the graph is a tree, and for the edge-disjoint packing problem when the graph is general andk = 2. The vertex-disjoint packing problem for general graphs is shown to be NP-complete even when the graph has maximum degree three andk = 2. Similarly the edge-disjoint packing problem is NP-complete even when the graph has maximum degree four andk = 3.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass. (1974).
C. Berge,Graphs and Hypergraphs, North-Holland, Amsterdam (1973).
F. T. Boesch and J. F. Gimpel, Covering the points of a digraph with point-disjoint paths and its application to code optimization,J. Assoc. Comput. Mach.,24 (1977), 192–198.
G. Cornuejols, D. Hartvigsen, and W. R. Pulleyblank, Packing subgraphs in a graph,Oper. Res. Lett.,4 (1982), 139–143.
M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco (1979).
F. Harary,Graph Theory, Addison-Wesley, Reading, Mass. (1969).
P. Hell and D. G. Kirkpatrick, On generalized matching problems,Inform. Process. Lett.,12 (1981), 33–35.
P. Hell and D. G. Kirkpatrick, Packings by cliques and by. finite families of graphs,Discrete Math.,49 (1984), 45–99.
P. Hell and D. G. Kirkpatrick, Packings by complete bipartite graphs,SIAM J. Algebraic Discrete Methods,7 (1986), 199–209.
I. Holyer, The NP-completeness of some edge-partition problems,SIAM J. Comput.,10 (1981), 713–717.
M. Jünger, G. Reinelt, and W. R. Pulleyblank, On partitioning the edges of graphs into connected subgraphs,J. Graph Theory,9 (1985), 539–549.
D. G. Kirkpatrick and P. Hell, On the complexity of general graph factor problems,SIAM J. Comput,12 (1983), 601–609.
E. L. Lawler,Combinatorial Optimization: Networks and Matroids, Holt, Rinehart, and Winston, New York (1976).
S. Masuyama, On the tree packing problem, Technical Report No. 87014, Dept. of Applied Mathematics and Physics, Faculty of Engineering, Kyoto University, Kyoto 606 (1987); to appear inDiscrete Appl. Math.
S. Masuyama and T. Ibaraki, Computational complexity of chain packing problems, Technical Report No. 87001, Dept. of Applied Mathematics and Physics, Faculty of Engineering, Kyoto University, Kyoto 606 (1987).
R. E. Tarjan, Depth first search and linear graph algorithms,SIAM J. Comput.,1 (1972), 146–160.
W. T. Tutte, The factorization of linear graphs,J. London Math. Soc.,22 (1947), 107–111.
Z. Z. Zhang, S. Masuyama, T. Ibaraki, and H. Mine, Graph packing over a rooted tree,Mem. Fac. Engrg. Kyoto Univ.,49, (1987), 206–215.
Author information
Authors and Affiliations
Additional information
Communicated by Tatsuo Ohtsuki.
This is a revised version of the technical report [15].
Rights and permissions
About this article
Cite this article
Masuyama, S., Ibaraki, T. Chain packing in graphs. Algorithmica 6, 826–839 (1991). https://doi.org/10.1007/BF01759074
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01759074