Lexicographically First Maximal Matching (LFMM)

Input

An undirected graph $G = (V, E)$ with an ordering on its edges and a distinguished edge $e \in E$.

Problem

Is $e$ in the lexicographically first maximal matching of $G$?

Definitions

A matching is maximal if it cannot be extended.

Status

Open (Mayr and Subramanian [1]).

Remarks

This problem is in $\CC$, that is, it is equivalent to CCVP. It resembles LFMIS that is $\P$-complete. A $\P$-completeness proof for LFMM would imply that EWM, is also $\P$-complete.