Open Access Open Access  Restricted Access Subscription Access

On the Performance of a Simple Approximation Algorithm for the Longest Path Problem

Nguyen Thi Phuong, Tran Vinh Duc, Le Cong Thanh

Abstract


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|}$.\


Keywords


Path; Hamiltonian path; Approximation algorithm; Performance ratio

Full Text:

PDF

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.




DOI: https://doi.org/10.15625/1813-9663/35/1/12935

Journal of Computer Science and Cybernetics ISSN: 1813-9663

Published by Vietnam Academy of Science and Technology