Describe Clique Decision Problem (CDP)

The Clique Decision Problem (CDP) asks whether a given undirected graph contains a clique of a specified size. Formally, CDP is the decision version of the maximum clique problem: it does not ask for the largest clique size, but instead asks whether there exists at least a clique with $k$ vertices.

We model an input graph as $G=(V,E)$ (with $n=|V|$ vertices) and ask:

• Is there a subset $S \subseteq V$ with $|S|=k$ such that every pair of vertices in $S$ is connected by an edge?
• In other words, does there exist a $k$-clique?

This can be written as:
$\exists S \subseteq V,\ |S|=k,\ \forall u,v \in S,\ u\neq v \Rightarrow (u,v)\in E.$

Conceptually, a clique is a “complete subgraph.” You can visualize CDP as a yes/no test that checks whether a graph hides a fully-connected $k$-vertex “cluster.”

Key learning terms introduced in this section:

• Clique
• k-Clique
• Decision problem
• NP
• Reduction

CDP formal problem statement

Let the input be:

• an undirected simple graph $G=(V,E)$
• an integer $k$

The decision version is:

• CDP(G, k) = YES iff $G$ contains a clique of size at least $k$ (often phrased as “contains a $k$-clique”).

In certificate-verification language (for complexity):

• A certificate is a set $S \subseteq V$ with $|S|=k$.
• Verification checks whether for all distinct $u,v \in S$, the edge $(u,v)$ is in $E$.

Verification time is polynomial in $n$:

• There are $\binom{k}{2}$ pairs to check.
• With adjacency queries in $O(1)$ using a hash/set or adjacency matrix, the check is $O(k^2)$ (plus input parsing).

Key complexity learning terms:

• Certificate
• Verifier
• Adjacency query

Relationship to maximum clique and complement structure

The maximum clique problem asks for the largest clique size:

• output: the maximum $t$ such that a $t$-clique exists.

CDP instead asks:

• output: whether some clique of size $k$ exists.

So, if $f(G)$ is the size of the maximum clique, then CDP asks whether: $f(G) \ge k.$

A useful structural fact (often used in reasoning) is the connection between cliques in $G$ and independent sets in the complement graph $\overline{G}$:

• a clique in $G$ corresponds to an independent set in $\overline{G}$.

This is a “graph duality” perspective:

• Clique problems and independent-set problems are tightly related through graph complement.

Key terms:

• Graph complement
• Independent set

CDP is in NP; brute-force baseline

Membership in NP: CDP is in NP because a $k$-vertex candidate clique can be checked in polynomial time.

Brute-force algorithm idea: try all $\binom{n}{k}$ subsets of vertices and test if each subset forms a clique. This yields exponential time: $\binom{n}{k} \approx \frac{n^k}{k!}\ \text{(grows rapidly)}.$

This motivates why clique-finding is hard:

• the search space is combinatorial.

Key terms:

• Brute force
• Combinatorial explosion
• [Exponential time]{def="Runtime that grows like $c^n$ or faster"}

CDP hardness and classic reduction viewpoint

In computational complexity, CDP is a canonical example for illustrating NP-completeness:

• it captures a fundamental combinatorial selection problem,
• and it is widely used as a target for reductions from other NP problems.

The typical reasoning pattern is:

1. Choose a known NP-complete problem (e.g., SAT variants).
2. Construct a graph $G$ and integer $k$ so that:
   • SAT instance is satisfiable iff $G$ has a clique of size $k$.
3. Therefore, solving CDP would solve the original NP-complete problem.

Key terms:

• NP-complete
• Polynomial-time reduction
• 3-SAT