← All Problems
Open

Lexicographically First Maximal Three-cycle Free Edge Induced Subgraph (LF3Edge)

Category: Circuit Complexity

Input

An undirected graph $G = (V, E)$ with an ordering on the edges in $E$ and having a maximum degree of five or less.

Problem

Compute the lexicographically first maximal three-cycle free edge induced subgraph of $G$. That is, the lexicographically first maximal edge induced subgraph that does not contain any cycles of size three or more.

Status

Open (Miyano [1][2]).

Remarks

Numerous variants of this problem are $\P$-complete. See LFEdge for a description of several of them. LF3Edge is in $\NC^2$ when the degree restriction on $G$ is four. For planar graphs, the complexity of the problem is also open. That is, there is no known degree restriction for LF3Edge that makes the problem $\P$-complete nor is it clear when the problem is in $\NC$ [1].

References

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

Related Problems