期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We investigate the hardness of approximating the longest path and the longest cycle in directed graphs on n vertices. We show that neither of these two problems can be polynomial time approximated within n 1 − for any 0"> 0 unless P = NP . In particular, the result holds for digraphs of constant bounded outdegree that contain a Hamiltonian cycle. Assuming the stronger complexity conjecture that Satisfiability cannot be solved in subexponential time, we show that there is no polynomial time algorithm that always finds a path of length ( log 2+ n ) , or a cycle of length ( log 1+ n ) , for any constant 0"> 0 in these graphs. In contrast we show that there is a polynomial time algorithm always finding a path of length ( log 2 n log log n ) in these graphs. This separates the approximation hardness of Longest Path and Longest Cycle in this class of graphs. Furthermore, we present a polynomial time algorithm that finds paths of length ( n ) in most digraphs of constant bounded outdegree.
关键词：Approximation Algorithms , Hamiltonian graphs , Long paths and cycles
for any 0"> 
