zbMATH — the first resource for mathematics

On approximating the longest path in a graph. (English) Zbl 0876.68083
Summary: We consider the problem of approximating the longest path in undirected graphs. In an attempt to pin down the best achievable performance ratio of an approximation algorithm for this problem, we present both positive and negative results. First, a simple greedy algorithm is shown to find long paths in dense graphs. We then consider the problem of finding paths in graphs that are guaranteed to have extremely long paths. We devise an algorithm that finds paths of a logarithmic length in Hamiltonian graphs. This algorithm works for a much larger class of graphs (weakly Hamiltonian), where the result is the best possible. Since the hard case appears to be that of sparse graphs, we also consider sparse random graphs. Here, we show that a relatively long path can be obtained, thereby partially answering an open problem of A. Broder, A. M. Frieze and E. Shamir [Finding hidden Hamiltonian cycles, Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 182-189 (1991)].
To explain the difficulty of obtaining better approximations, we also prove hardness results. We show that, for any $$\varepsilon<1$$, the problem of finding a path of length $$n-n^\varepsilon$$ in an $$n$$-vertex Hamiltonian graph is NP-hard. We then show that no polynomial-time algorithm can find a constant factor approximation to the longest-path problem unless $$\text{P}=\text{NP}$$. We conjecture that the result can be strengthened to say that, for some constant $$\delta>0$$, finding an approximation of ratio $$n^\delta$$ is also NP-hard. As evidence toward this conjecture, we show that if any polynomial-time algorithm can approximate the longest path to a ratio of $$2^{O(\log^{1-\varepsilon}n)}$$ for any $$\varepsilon>0$$, then NP has a quasi-polynomial deterministic time simulation. The hardness results apply even to the special case where the input consists of bounded degree graphs.

MSC:
 68R10 Graph theory (including graph drawing) in computer science 68W10 Parallel algorithms in computer science
Keywords:
undirected graphs; greedy algorithm
Full Text:
References:
 [1] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof verification and hardness of approximation problems,Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, 1992, pp. 14–23. · Zbl 0977.68539 [2] S. Arora and S. Safra, Approximating clique is NP-complete,Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, 1992, pp. 2–13. · Zbl 0945.68516 [3] M. Bellare, Interactive Proofs and Approximation, IBM Research Report RC 17969, 1992. [4] P. Berman and G. Schnitger, On the complexity of approximating the independent set problem,Information and Computation,96 (1992), 77–94. · Zbl 0804.90121 [5] A. Blum, Some tools for approximate 3-coloring,Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, 1990, pp. 554–562. [6] B. Bollobas,Random Graphs, Academic Press, New York, 1985. [7] R. B. Boppana and M. M. Halldorsson, Approximating maximum independent sets by excluding subgraphs,Proceedings of the 2nd Scandanavian Workshop on Algorithmic Theory, Lecture Notes in Computer Science, No. 447, Springer-Verlag, Berlin, 1990, pp. 13–25. [8] A. Broder, A. M. Frieze, and E. Shamir, Finding hidden Hamiltonian cycles,Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991, pp. 182–189. · Zbl 0809.05064 [9] V. Chvatal, Tough graphs and Hamiltonian circuits,Discrete Mathematics,5 (1973), 215–228. · Zbl 0256.05122 [10] V. Chvatal, Edmonds polytopes and weakly Hamiltonian graphs,Mathematical Programming,5 (1973), 29–40. · Zbl 0267.05118 [11] V. Chvatal, Hamiltonian cycles, inThe Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (ed. E. L. Lawleret al.), Wiley, New York, 1985, pp. 402–430. [12] R. Fagin, Generalized first-order spectra and polynomial-time recognizable sets, inComplexity of Computer Computations (ed. R. Karp), American Mathematical Society, Providence, RI, 1974. · Zbl 0303.68035 [13] U. Feige, S. Goldwasser, L. LovĂˇsz, S. Safra, and M. Szegedy, Approximating clique is almost NP-complete,Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science, 1991, pp. 2–12. [14] W. F. de la Vega and G. S. Lueker, Bin packing can be solved within 1+{$$\epsilon$$} in linear time,Combinatorica,1 (1981), 349–355. · Zbl 0485.68057 [15] M. Furer and B. Raghavachari, Approximating the minimum degree spanning tree to within one from the optimal degree,Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, 1992, pp. 317–324. · Zbl 0829.68097 [16] M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979. · Zbl 0411.68039 [17] D. S. Johnson, The Tale of the Second Prover, The NP-Completeness Column: An Ongoing Guide,Journal of Algorithms,13 (1992), 502–524. · Zbl 0786.68035 [18] D. R. Karger, R. Motwani, and M. Sudan, Approximate graph coloring by semidefinite programming,Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 2–13. · Zbl 0904.68116 [19] N. Karmakar and R. M. Karp, An efficient approximation scheme for the one-dimensional bin packing problem,Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, 1982, pp. 312–320. [20] C. Lund and M. Yannakakis, On the hardness of approximating minimization problems,Proceedings of the 25th Annual ACM Symposium on Theory of Computing, 1993, pp. 286–293. · Zbl 1310.68094 [21] B. Monien, How to find long paths efficiently,Annals of Discrete Mathematics,25 (1984), 239–254. [22] R. Motwani, Lecture Notes on Approximation Algorithms, Technical Report No. STAN-CS-92-1435, Department of Computer Science, Stanford University, 1992. [23] C. H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes,Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988, pp. 229–234. [24] C. H. Papadimitriou and M. Yannakakis, The traveling salesman problem with distances one and two,Mathematics of Operations Research,18 (1993), 1–11. · Zbl 0778.90057 [25] A. Subramanian, Personal communication, 1994.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.