UNIQUE-PATH in P assuming LPATH is in P

Question

We define the following languages:

LPATH = {<G, a, b, k>|G is an undirected graph that contains a simple path of length at least k from a to b}.

UNIQUE-PATH = {<G, a, b>| G is an undirected graph. The longest simple path from a to b in G is unique}.

Assuming LPATH ∈ P, prove that UNIQUE-PATH ∈ P.

Any idea I had resulted in me getting stuck at the part where I needed to differentiate if an edge was needed to the path or not (so I could delete it and see if the path was unique). I would appreciate any ideas you might have regarding this one.

Answer 1

Hint: this is perhaps not the best argument, but it follows the intuition you mentioned in the question. Note that, assuming $\text{LPATH} \in \text{P}$, it is easy to find, in polynomial time, a longest simple path $p$ in $G$ ( I leave the details to you). Then, it is straight-forward to take it from here and use $p$ to find if there is a different longest simple path in $G$.

Answer 2

Let $G = (V,E)$ and $n = |V|$. An easy polytime algorithm solving $UNIQUE-PATH$:

for i in range(n, -1, -1):
    if LPATH(G, i):
        for v in V:
            Let G’ be G with v removed from its vertices.
            if LPATH(G’, i):
                Return False
    return True

Proof is simply that the first time the $LPATH(G, i)$ guard passes, the program variable $i$ will be the length of the longest simple path(s). Fix a path $p$, and assume there is another simple path $q$ of the same length. Because $|p|=|q|$ there is at least one vertex $v*$ in $p$ not found in $q$. Thus for the $v*$ iteration of the inner loop, $LPATH(G, i) = LPATH(G', i)$ since removing $v*$ leaves $q$ intact and the program will return False.

The case where the path $p$ was unique is symmetric - there is no such $q$ and $v*$ and upon exiting the inner loop the algorithm returns True.