Ordered Vertices Remaining (OVR)

Input

An undirected graph $G = (V, E)$ with a numbering on the vertices in $V$, a designated vertex $u$, and an integer $k$.

Problem

Is there an elimination order on $V$: $v_1, \ldots, v_n$ satisfying the properties that $u = v_j$ for some $j < (n - k)$ and for $1 \leq i \leq n$, $v_i$ is the lowest numbered vertex of maximum degree in the $(i-1)$-st remaining subgraph of $G$?

Definitions

See OHDVR.

Status

$\P$-complete (Greenlaw [1]).

Remarks

The reduction to show hardness is from OHDVR. The Ordered Low Degree Subgraph Membership Problem is also $\P$-complete. The problem here is to determine whether a designated vertex is in a remaining subgraph when all vertices in that remaining subgraph have small degree.