On the Performance of a Simple Approximation Algorithm for the Longest Path Problem
Author affiliations
DOI:
https://doi.org/10.15625/1813-9663/35/1/12935Keywords:
Path, Hamiltonian path, Approximation algorithm, Performance ratioAbstract
The longest path problem is known to be NP-hard. Moreover, they cannot be approximated within a constant ratio, unless ${\rm P=NP}$. The best known polynomial time approximation algorithms for this problem essentially find a path of length that is the logarithm of the optimum.
In this paper we investigate the performance of an approximation algorithm for this problem in almost every case. We show that a simple algorithm, based on depth-first search, finds on almost every undirected graph $G=(V,E)$ a path of length more than $|V|-3\sqrt{|V| \log |V|}$ and so has performance ratio less than $1+4\sqrt{\log |V|/|V|}$.\
Metrics
References
D. Angluin and L.G. Valiant,
emph{Fast probabilistic algorithm for Hamiltonian circuits and matchings}.
J. Computer and System Sci., 18 (1979), 155--193.
S.R. Arikati and C.P. Rangan,
emph{Linnear algorithm for optimal path cover problem on interval graphs}.
Inform. Process. Lett., 35 (1990), 149--153.
N. Alon, R. Yuster, and U. Zwick,
emph{Color-coding}.
J. ACM, 42 (1995), 844--856.
A.A. Bertossi,
emph{Finding Hamiltolian circuits in proper interval graphs}.
Inform. Process. Lett., 17 (1983), 97--101.
A. Bj$ddot{rm o}$rklund and T. Husfeldt.
emph{Finding a path of superlogarithmic length}.
SIAM Journal on Computing, 32 (2003), 1395--1402.
H.L. Bodlaender,
emph{On linear time minor tests with depth-first search}.
J. Algorithms, 14 (1993), 1--23.
B. Bollob$acute{rm a}$s,
emph{Random Graphs,} 2nd Edition.
Cambridge University Press, 2001.
B. Bollob$acute{rm a}$s, T.I. Fenner and A.M. Frieze,
emph{An algorithm for finding Hamilton paths and cycles in random graphs}.
Combinatorica, 7 (1987), 327--341.
R.W. Bulterman, F.W. van der Sommen, G. Zwaan, T. Verhoeff, A.J.M. van Gasteren, and W.H.J. Feijen,
emph{On computing a longest path in a trees}.
Inform. Process. Lett., 81 (2002), 93--96.
P. Damaschke, J.S. Deogun, D. Kratsch, and G. Stener,
emph{Finding Hamiltolian paths in cocomparability graphs using the bump number algorithm}.
Order, 8 (1992) 383--391.
M.R. Garey and D.S. Johnson,
emph{Computers and Intractability - A~Guide to the NP-completeness}.
W.H. Freeman, 1979.
H.N. Gabow,
emph{Finding paths and cycles of superpolylogarithmic length}.
SIAM Journal on Computing, 36 (2007), 1649--1671.
H.N. Gabow and S. Nie,
emph{Finding long paths, cycles and circuits}.
th Annual International Symp. on Algorithms and Computation, LNCS 5369 (2008), 752--763.
K. Ioannidou, G.B. Mertzios, and S.D. Nikolopoulos,
emph{The longest path problem has a polynomial solution on interval graphs}.
Algorithmica, 61 (2011), 320--341.
J.M. Keil,
emph{Finding Hamiltonian circuits in interval graphs}.
Inform. Process. Lett., 20 (1983), 201--206.
D. Karger, R. Motwani, and G.D.S. Ramkumar,
emph{On approximating the longest path in a graph}.
Algorithmica, 18 (1997), 82--98.
B. Monien,
emph{How to find long paths efficiently}.
Annals of Discrete Mathematics, 25 (1985), 239--254.
E. Shamir,
emph{How many random edges make a graph Hamiltonian?}.
Combinatorica, 3 (1983), 123--132.
Y. Takahara, S. Teramoto, and R. Uehara,
emph{Longest path problems on ptolemaic graphs}.
IEICE Trans. Inform. System., E91-D (2008), 170--177.
L.C. Thanh,
emph{On the approximability of Max-Cut}.
Vietnam J. Math., 34:4 (2006), 389--395.
L.C. Thanh,
emph{Performance analysis of greedy algorithms for Max-IS and Min-Maxl-Match}.
Vietnam J. Math., 36:3 (2008), 327--336.
L.C. Thanh,
emph{Minimum connected dominating sets in finite graphs}.
Vietnam J. Math., 38:2 (2010), 157--168.
A. Thomason,
emph{A simple linear expected time algorithm for finding a Hamilton path}.
Discrete Math., 75 (1989), 373--379.
R. Uehara and Y. Uno,
emph{Efficient algorithms for the longest path problem}.
th Annual International Symp. on Algorithms and Computation, LNCS 3314 (2004), 871--883.
R. Uehara and G. Valiente,
emph{Linear structure of bipartite permutation graphs and the longest path problem}.
Inform. Process. Lett., 103 (2007), 71--77.
Downloads
Published
How to Cite
Issue
Section
License
1. We hereby assign copyright of our article (the Work) in all forms of media, whether now known or hereafter developed, to the Journal of Computer Science and Cybernetics. We understand that the Journal of Computer Science and Cybernetics will act on my/our behalf to publish, reproduce, distribute and transmit the Work.2. This assignment of copyright to the Journal of Computer Science and Cybernetics is done so on the understanding that permission from the Journal of Computer Science and Cybernetics is not required for me/us to reproduce, republish or distribute copies of the Work in whole or in part. We will ensure that all such copies carry a notice of copyright ownership and reference to the original journal publication.
3. We warrant that the Work is our results and has not been published before in its current or a substantially similar form and is not under consideration for another publication, does not contain any unlawful statements and does not infringe any existing copyright.
4. We also warrant that We have obtained the necessary permission from the copyright holder/s to reproduce in the article any materials including tables, diagrams or photographs not owned by me/us.
