Abstrakt. Vi undersöker hårdheten av att approximera den längsta vägen och den längsta cykeln i riktade grafer på n hörn. Vi visar att inget av dessa två problem kan vara polynom tid approximerad inom n 1— för någon > 0 om inte P = NP. I synnerhet, resultatet håller för digrafer av konstant avgränsad utgrad som innehåller en Hamiltonian cykel. Om man antar att tillfredsställelsen inte kan lösas i subexponentiell tid, visar vi att det inte finns någon polynomtidsalgoritm som finner en riktad väg av längd (f (n) log 2 n), eller en riktad cykel av längd (f (n) log n), för varje icke-decreasing, polynomisk tidsberäknad funktion f i  och (1). Med en ny algoritm för oriktade grafer av Gabow, visar detta att långa vägar och cykler är svårare att hitta i riktade grafer än i oriktade grafer. Vi hittar också en riktad väg av längd (log 2 n/ log log n) i Hamiltonian digraphs med avgränsad utgrad. Med våra hårdhetsresultat visar detta att långa, riktade cykler är svårare att hitta än långa, riktade vägar. Dessutom presenterar vi en enkel polynom-tidsalgoritm som finner vägar av längd (n) i riktade expanders av konstant avgränsade utgrader.
Med starkare antaganden är det riktade problemet svårt att närma sig inom en faktor av n/ log 2+ n för alla > 0 REF.
Approximating longest directed paths and cycles
{'venue': 'In Proceedings of the 31st International Colloquium on Automata, Languages and Programming', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}