← All Problems
Open

Restricted Lexicographically First Maximal Independent Set (RLFMIS)

Category: Circuit Complexity

Input

An undirected, planar, bipartite graph $G = (V, E)$ with a numbering on the vertices in $V$.

Problem

Find the lexicographically first maximal independent set.

Status

Open (Miyano [1]).

Remarks

See LFMIS. Finding the lexicographically first maximal subgraph of maximum degree one in planar, bipartite graphs of degree at most three is $\P$-complete [1].

References

  1. S. Miyano (1989). The lexicographically first maximal subgraph problems: P-completeness and NC algorithms.
  2. Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem B.1.7.

Related Problems