Ordered Low Degree Vertex Removal (OLDVR)

Input

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

Problem

Is there an elimination order on $V$, $v_1, v_2, \ldots, v_n$, satisfying the properties that $u$ is eliminated before $v$ and for $1 \leq i \leq n$, $v_i$ is the lowest numbered vertex of minimum degree in the $(i-1)$-st remaining subgraph of $G$?

Definitions

See OHDVR.

Status

$\P$-complete (Vishwanathan and Sridhar [1], Greenlaw [2]).

Remarks

This is the complementary of OHDVR,

The problem defined in [1] is more restricted than the one presented here. Their graphs are also required to have the property that $u$ appears before $v$ in some minimum elimination sequence if and only if $u$ appears before $v$ in all minimum degree elimination sequences.