P-complete

Graph Closure (GC)

Input

An undirected graph $G = (V, E)$ with $N = |V|$ and a designated edge $e = uv$.

Problem

Is $e$ in the $N$-closure of $G$?

Definitions

The $c$-closure of a graph is the graph obtained from $G$ by repeatedly joining nonadjacent pairs of vertices $u$ and $v$ whose degree sum is at least $c$.

Status

$P$-complete under $\LOGSPACE$ reductions (Monti [1]).

Remarks

An $O(n^3)$ algorithm solving the problem is given in [1]. Monti shows the $(N+k)$-closure problem is $\P$-complete for any (fixed) integer $k$. As for the $(2N-k)$-closure problem, it is trivial for $k \leq 4$, in $\LOGSPACE$ for $k=5$ and $\P$-complete for $k \geq 6$ [1]. All reductions are from MCVP.

The problem was stated as “Open” in the classic Greenlaw, Hoover, and Ruzzo book [3], but the completeness was settled shortly after.

References

A. Monti (1996). On the computational complexity of graph closures.
S. Khuller (1989). On computing graph closures.
Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem B.1.4.