Problem: Domination

Definition:
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of vertices, with |S| <= k, such that every vertex in G is either in S or adjacent to a vertex in S.

Linear

Polynomial

GI-complete

NP-hard

NP-complete

coNP-complete

Open

Unknown to ISGCI