← All Problems
P-complete

Lexicographically First Maximal Clique (LFMC)

Category: Graph Theory

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 clique of $G$?

Status

$\P$-complete (Cook [1]).

Remarks

Finding a maximal clique is equivalent to finding a maximal independent set in the complement graph of $G$, see LFMIS. Stewart shows that Ordered Greedy Clique and Ordered Remaining Clique are both $\P$-complete [2]. These two decision problems are based on heuristic greedy algorithms for computing cliques.

References

  1. S. A. Cook (1985). A taxonomy of problems with fast parallel algorithms.
  2. I. A. Stewart (1993). On two approximation algorithms for the clique problem.
  3. Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem A.2.2.

Related Problems