Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

LONGEST PATH

• INSTANCE: Graph $G=\left(V,E\right)$.

• SOLUTION: Simple path in G, i.e., a sequence of distinct vertices $v_1,v_2,\ldots,v_m$ such that, for any $1 \leq i \leq m-1$, $(v_i ,v_{i+1}) \in E$.

• MEASURE: Length of the path, i.e., the number of edges in the path.

  
  

• Good News: Approximable within $O(\vert V\vert/ \log \vert V\vert)$ [13].

• Bad News: Not in APX [289].

• Comment: Transformation from MINIMUM METRIC TRAVELING SALESPERSON PROBLEM with distances one and two: APX-hard and self-improvable. Not approximable within $2^{\log^{1-\varepsilon } \vert V\vert}$ for any $\varepsilon >0$ unless NP$\subset$QP [289]. Similar results hold for a chromatic version of the problem [67]. Variation in which the path must be induced subgraph of G, LONGEST INDUCED PATH, is NPO PB-complete and not approximable within $O(\vert V\vert^{1-\varepsilon })$ for any $\varepsilon >0$, see MAXIMUM INDUCED CONNECTED SUBGRAPH WITH PROPERTY P.

  Remains APX-hard even if restricted to dense instances [163].

• Garey and Johnson: ND29