View source for 2-sensitive (7/5)-approximate st-shortest paths

{{DISPLAYTITLE:2-sensitive (7/5)-approximate st-shortest paths (Shortest Path (Directed Graphs))}}
== Description == 

Approximate the st-shortest paths problem within a factor of 7/5 with a sensitivity of 2.

== Related Problems == 

Generalizations: [[st-Shortest Path]]

Related: [[General Weights]], [[Nonnegative Weights]], [[Nonnegative Integer Weights]], [[Second Shortest Simple Path]], [[1-sensitive (3/2)-approximate ss-shortest paths]], [[1-sensitive decremental st-shortest paths]], [[2-sensitive decremental st-shortest paths]], [[Replacement Paths Problem]]

== Parameters == 

$V$: number of vertices

$E$: number of edges

$L$: maximum absolute value of edge cost

== Table of Algorithms == 

Currently no algorithms in our database for the given problem.

== Reductions FROM Problem == 

{| class="wikitable sortable"  style="text-align:center;" width="100%"

! Problem !! Implication !! Year !! Citation !! Reduction

|-

| [[BMM]] ||  style="text-align:left;" | assume: BMM<br/>then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ in undirected unweighted graphs || 2017 || https://arxiv.org/pdf/1703.01638.pdf || [[Reduction from BMM to 2-sensitive (7/5)-approximate st-shortest paths|link]]
|-
|}