Lexicographically First Maximal Independent Set (LFMIS)

Input

An undirected graph $G = (V, E)$ with an ordering on the vertices and a designated vertex $v$.

Problem

Is vertex $v$ in the lexicographically first maximal independent set of $G$?

Status

$\P$-complete under $\NC^1$ reductions (Greenlaw, Hoover and Ruzzo [9, Theorem 7.1.2], Cook [1]).

Remarks

The reduction to show hardness is from NORCVP. This is an instance of the LFMS(π). LFMIS is $\P$-complete for bipartite or planar graphs restricted to degree at most three [2]. Karp observed that the completeness of LFMIS implies that determining the $i^\text{th}$ vertex chosen by any deterministic sequential algorithm for either LFMIS or LFMC is also complete [3]. Computing or approximating the size of the lexicographically first maximal independent set is also $\P$-complete [9, Section 10].

Luby gave the first $\NC$ algorithm for finding a maximal independent set [4], subsequently improved by Luby [5], by Alon, Babai, and Itai [6], and by Goldberg and Spencer [7]. These algorithms do not compute the lexicographically first maximal independent set. Using a general result involving inference systems, when $G$ is a forest LFMIS can be solved on a CREW-PRAM in $O(\log |V|)$ time using a polynomial number of processors [8].