Andreas Björklund, Thore Husfeldt, Sanjeev Khanna

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-\epsilon}$ for any $\epsilon>0$ unless

$\text{P}=\text{NP}$. In particular, the result holds for

more >>>