Class Description

UCC: Unique Connected Component

The class of problems reducible in L to the problem of whether an undirected graph has a unique connected component.

See [AG00] for more information.

Equals L. [Rei04]

The corresponding class for directed graphs equals NL. On the other hand, none of that class's corresponding search problems are obviously FNL-hard.

Linked From

coUCC: Complement of UCC

[Tor00] showed the following problem complete for coUCC under L reductions:

Given a colored graph G with at most two vertices having any given color, does G have any nontrivial automorphisms?

More about...