Lexicographically First Maximal Path (LFMP)

Input

An undirected graph $G = (V, E)$ with a numbering on the vertices, and two designated vertices $s$ and $t$.

Problem

Is vertex $t$ on the lexicographically first maximal path in $G$ beginning at $s$?

Definitions

A maximal path is a path that cannot be extended because any attempt at extending it will result in an encounter with a vertex that is already on the path. The lexicographically first maximal path is the maximal path that would appear first in the “alphabetical” listing of all paths from $s$, where the alphabetizing is done with respect to the vertex numbers.

Status

$\P$-complete (Anderson and Mayr [1]).

Remarks

The reduction to show hardness is from a restricted version of CVP. LFMP remains $\P$-complete when restricted to planar graphs with maximum degree three. If the maximum degree of any vertex in $G$ is at most $\Delta$, there is an algorithm that can find a maximal path in $O(\Delta(\log n)^3)$ time using $n^2$ processors [1].

There is also an $\NC$ algorithm for finding a maximal path in planar graphs [1]. The complexity of the general problem of finding a maximal path is open [1], although Anderson shows it to be in $\mathsf{RNC}$ [2]. See MP.