# Does k-PATH admit a constant approximation?

In the $k$-PATH problem, we receive as input a graph $G$ and an integer $k$. The goal is to decide whether there exists a simple path of length $k$ in $G$.

A $\alpha$-approximation for $k$-PATH is an algorithm which given an input $\langle G,k\rangle$ either confirms that a path of length $k/\alpha$ exists in $G$, or denies the existence of a $k$-path. It may act arbitrarily if the longest simple path in $G$ is at least of size $k/\alpha$ and at most of size $k$.

Is there a constant $\alpha>0$ for which $k$-PATH is $\alpha$-approximable in poly time?

Karger, Motwani and Ramkumar (1997) discuss this question. They show that if any polynomial-time algorithm can approximate the longest path to a ratio of $2^{O(\log^{1−\epsilon} n)}$, for any $\epsilon>0$, then NP has a quasi-polynomial deterministic time simulation; this results even holds for graphs of bounded degree.
{"ft_lang_label":"__label__en","ft_lang_prob":0.8411198,"math_prob":0.9998109,"size":556,"snap":"2021-43-2021-49","text_gpt3_token_len":161,"char_repetition_ratio":0.117753625,"word_repetition_ratio":0.0,"special_character_ratio":0.28057554,"punctuation_ratio":0.06837607,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9999808,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-11-28T11:03:42Z\",\"WARC-Record-ID\":\"<urn:uuid:6f153a41-57ac-4420-a9c9-ef11e17ba910>\",\"Content-Length\":\"137340\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:cf4d8853-9e3e-4010-ae91-5474188f2b24>\",\"WARC-Concurrent-To\":\"<urn:uuid:e8630f86-0419-42b8-abb6-b51200a0eb03>\",\"WARC-IP-Address\":\"151.101.1.69\",\"WARC-Target-URI\":\"https://cstheory.stackexchange.com/questions/34055/does-k-path-admit-a-constant-approximation\",\"WARC-Payload-Digest\":\"sha1:OA6WDDXVA3FSRNGUO3T24VOBC7WCUWCS\",\"WARC-Block-Digest\":\"sha1:4GPZNSDU6LHDAGJ3UVH4JJOLHG5ME2KE\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-49/CC-MAIN-2021-49_segments_1637964358520.50_warc_CC-MAIN-20211128103924-20211128133924-00448.warc.gz\"}"}