Abstract
Given a graph, the Hamiltonian path completion problem is to find an augmenting edge set such that the augmented graph has a Hamiltonian path. In this paper, we show that the Hamiltonian path completion problem will unlikely have any constant ratio approximation algorithm unless NP = P. This problem remains hard to approximate even when the given subgraph is a tree. Moreover, if the edge weights are restricted to be either 1 or 2, the Hamiltonian path completion problem on a tree is still NP-hard. Then it is shown that this problem will unlikely have any fully polynomial-time approximation scheme (FPTAS) unless NP=P. When the given tree is a k-tree, we give an approximation algorithm with performance ratio 1.5.
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
S. R. Arikati and C. Pandu Rangan. Linear algorithm for optimal path cover problem on interval graphs. Inf. Process. Lett., 35(3):149–153, 1990.
S. Arora. Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. In Proc. 37th Annual IEEE Symposium on Foundations of Computer Science, pages 2–11. IEEE Computer Society, 1996.
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and Approximation. Springer-Verlag, Berlin Heidelberg, 1999.
B. S. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM, 41(1):153–180, 1994.
A. Blum, M. Li, J. Tromp, and M. Yannakakis. Linear approximation of shortest superstrings. Journal of the ACM, 41(4):630–647, 1994.
F. T. Boesch, S. Chen, and J. A. M. McHugh. On covering the points of a graph with point disjoint paths. In Lecture Notes in Mathematics, volume 46, pages 201–212. Springer, Berlin, 1974.
M. A. Bonuccelli and D. P. Bovet. Minimum node disjoint path covering for circular-arc graphs. Inf. Process. Lett., 8:159–161, 1979.
G. Galbiati, F. Maffioli, and A. Morzenti. A short note on the approximability of the maximum leaves spanning tree problem. Inf. Process. Lett., 52:45–49, 1994.
M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, 1979.
S. E. Goodman, S. T. Hedetniemi, and P. J. Slater. Advances on the Hamiltonian completion problem. Journal of the ACM, 22(3):352–360, 1975.
O. H. Ibarra and C. E. Kim. Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM, 22(4):463–468, 1975.
S. Kundu. A linear algorithm for the Hamiltonian completion number of a tree. Inf. Process. Lett., 5:55–57, 1976.
E. L. Lawler. Combinatorial Optimization: Networks and Matroids, chapter 6. Holt, Rinehart and Winston, New York, 1976.
J. Misra and R. E. Tarjan. Optimal chain partitions of trees. Inf. Process. Lett., 4:24–26, 1975.
C. H. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. J. Comput. Syst. Sci., 43:425–440, 1991.
C. H. Papadimitriou and M. Yannakakis. The traveling salesman problem with distances one and two. Mathematics of Operations Research, 18:1–11, 1993.
S. Sahni and T. Gonzalez. P-complete approximation problems. Journal of the ACM, 23(3):555–565, 1976.
Z. Skupien. Path partitions of vertices and Hamiltonicity of graphs. In Proc. 2nd Czechoslovakian Symp. on Graph Theory, pages 481–491, Prague, 1974.
R. Srikant, R. Sundaram, K. S. Singh, and C. P. Rangan. Optimal path cover problem on block graphs and bipartite permutation graphs. Theoretical Computer Science, 115(2):351–357, 1993.
P.-K. Wong. Optimal path cover problem on block graphs. Theoretical Computer Science, 225(1-2):163–169, 1999.
Q. S. Wu. On the Complexity and Approximability of Some Hamiltonian Path Problems. PhD Thesis, National Tsing Hua University, Taiwan, 2000.
J. H. Yan and G. J. Chang. The path-partition problem in block graphs. Inf. Process. Lett., 52:317–322, 1994.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wu, Q.S., Lu, C.L., Lee, R.C.T. (2000). An Approximate Algorithm for the Weighted Hamiltonian Path Completion Problem on a Tree. In: Goos, G., Hartmanis, J., van Leeuwen, J., Lee, D.T., Teng, SH. (eds) Algorithms and Computation. ISAAC 2000. Lecture Notes in Computer Science, vol 1969. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-40996-3_14
Download citation
DOI: https://doi.org/10.1007/3-540-40996-3_14
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41255-7
Online ISBN: 978-3-540-40996-0
eBook Packages: Springer Book Archive