Decision and Optimization Versions of Graph Problems

Two Ways to Ask a Graph Problem

Many graph questions can be phrased in either of two ways. A decision problem asks for a yes-or-no answer, usually after a numerical threshold is supplied: does the graph contain a clique of size at least $k$? An optimization problem asks for an extremal value and, in an exact version, a structure attaining it: what is the largest clique, or what is its size? These formulations are related, but they are not the same task.

Throughout, graphs are finite and simple. A clique is a set of pairwise adjacent vertices; an independent set is a set whose distinct vertices are not adjacent; a vertex cover is a set containing at least one endpoint of every edge. A cycle here is a simple cycle, so it has at least three distinct vertices. We use the convention that the empty set is both a clique and an independent set, and is a vertex cover when the graph has no edges.

Definition: For a graph $G=(V,E)$, the clique number $\omega(G)$ is the largest size of a clique, the independence number $\alpha(G)$ is the largest size of an independent set, and the vertex cover number $\tau(G)$ is the smallest size of a vertex cover. An exact optimizer returns an optimal value and a feasible structure attaining that value. For longest cycle, let $L(G)$ be the largest number of vertices in a cycle of $G$, and set $L(G)=0$ if $G$ has no cycle.

The convention for $L(G)$ makes the objective defined even when there is no cycle to return: in that case an exact optimizer reports that no cycle exists and returns the value $0$. For the empty graph, $\omega(G)=\alpha(G)=\tau(G)=0$ under the conventions above. These boundary cases matter when turning an optimizer’s answer into a decision.

Decision and Optimization Formulations

For Clique, the decision input includes a threshold $k$: is there a clique with at least $k$ vertices? Its optimization counterpart asks for $\omega(G)$ and a clique of that size. Independent Set has the same threshold form, with an independent set in place of a clique; its exact optimizer returns $\alpha(G)$ and a maximum independent set.

For Vertex Cover, the threshold question is naturally phrased as “is there a vertex cover of size at most $k$?” Its optimization counterpart minimizes size and returns $\tau(G)$ and a minimum vertex cover. Thus Clique and Independent Set use a lower bound on a maximized quantity, while Vertex Cover uses an upper bound on a minimized quantity.

Hamiltonian Cycle is a decision problem asking whether the graph has a cycle containing every vertex. Its optimization counterpart is the longest-cycle problem: find $L(G)$ and, when $L(G)>0$, a cycle with that many vertices. A Hamiltonian cycle can exist only when $|V(G)|\ge3$, because cycles in a simple graph have at least three vertices.

Theorem: Given exact optimizers for the four objectives above, the associated decision questions are answered by these tests:

Clique: answer yes exactly when $\omega(G)\ge k$.
Independent Set: answer yes exactly when $\alpha(G)\ge k$.
Vertex Cover: answer yes exactly when $\tau(G)\le k$.
Hamiltonian Cycle: answer yes exactly when $|V(G)|\ge3$ and $L(G)=|V(G)|$.

These equivalences hold for every graph and every integer threshold $k$.

Proof. By definition, $\omega(G)$ is the size of a largest clique. If $\omega(G)\ge k$, a largest clique itself has at least $k$ vertices, so the decision answer is yes. Conversely, if there is a clique of size at least $k$, the largest clique is at least as large, so $\omega(G)\ge k$. The same argument, using largest independent sets, proves the Independent Set equivalence. For Vertex Cover, if $\tau(G)\le k$, a minimum cover is a cover of size at most $k$; if some cover has size at most $k$, the minimum size cannot be larger than that, so $\tau(G)\le k$. Finally, if the graph has a Hamiltonian cycle, it has a cycle containing $|V(G)|$ vertices, so $L(G)=|V(G)|$. In the other direction, when $|V(G)|\ge3$, the value $L(G)=|V(G)|$ is attained by a cycle containing all vertices, which is a Hamiltonian cycle. If $|V(G)|<3$, the decision answer is no by the definition of a cycle, so the stated size condition prevents a false yes. The convention $L(G)=0$ when no cycle exists also makes the test return no in that case. $\square$

A Useful Link Between Independent Sets and Covers

Independent Set and Vertex Cover are complementary formulations: choosing vertices not in a cover leaves no edge between them. This relation gives an exact translation between their optimum values, not just a connection between their threshold questions.

Proposition: For every finite simple graph $G=(V,E)$, $$ \alpha(G)+\tau(G)=|V|. $$

Proof. If $C\subseteq V$ is a vertex cover, then $V\setminus C$ is independent: an edge with both endpoints in $V\setminus C$ would have neither endpoint in $C$, contradicting that $C$ covers every edge. Hence $|V\setminus C|\le\alpha(G)$, so $|C|=|V|-|V\setminus C|\ge |V|-\alpha(G)$. Applying this to a minimum cover gives $\tau(G)\ge |V|-\alpha(G)$.

Conversely, if $I\subseteq V$ is independent, every edge has at least one endpoint in $V\setminus I$; otherwise both endpoints would belong to $I$, contrary to independence. Thus $V\setminus I$ is a vertex cover. Taking $I$ to be a maximum independent set gives $\tau(G)\le |V|-\alpha(G)$. The two inequalities imply $\tau(G)=|V|-\alpha(G)$, as required. This argument also covers $V=\varnothing$, for which both optimum sizes are zero. $\square$

Worked Example: Exact Optima for a Graph with Two Triangles

Let $G=(V,E)$ have $V=\{1,2,3,4,5\}$ and $E=\{12,13,23,34,35,45\}$. We find its clique, independent set, and vertex cover optimum values.

The vertices $\{1,2,3\}$ are pairwise adjacent, since $12,13,23\in E$, so they form a clique of size $3$. The vertices $\{3,4,5\}$ also form a clique of size $3$, since $34,35,45\in E$. To see that no larger clique exists, first consider a clique containing $3$. The other vertices split into $\{1,2\}$ and $\{4,5\}$; no vertex in the first set is adjacent to a vertex in the second set. Such a clique can therefore use vertices from at most one of these sets, and each set has only two vertices. A clique containing $3$ has size at most $3$. A clique not containing $3$ lies in $\{1,2,4,5\}$; among these vertices the only edges are $12$ and $45$, so it has size at most $2$. Thus $\omega(G)=3$.

Vertex $3$ is adjacent to $1,2,4,5$, so an independent set containing $3$ has size at most $1$. If an independent set omits $3$, it can use at most one vertex from $\{1,2\}$, because $12\in E$, and at most one from $\{4,5\}$, because $45\in E$. Its size is at most $2$, and $\{1,4\}$ is independent because $14\notin E$. Hence $\alpha(G)=2$.

The proposition gives $\tau(G)=|V|-\alpha(G)=5-2=3$. For a direct check, the complement of $\{1,4\}$ is $\{2,3,5\}$. This set covers $12$ and $23$ through $2$ or $3$, covers $13$, $34$, and $35$ through $3$ or $5$, and covers $45$ through $5$. It is a cover of size $3$; the proposition proves that no smaller cover exists.

Check: the computed values satisfy $\alpha(G)+\tau(G)=2+3=5=|V|$. The exhibited clique has size $3$, and the upper-bound argument shows that no clique can be larger.

Using the Optima to Answer Threshold Questions

An exact optimizer can answer more than one threshold question on the same graph: its optimum value can be compared with different $k$ values. A returned witness is also useful because it verifies a yes answer directly. For a no answer, the exact optimum certifies that no better feasible object exists; merely displaying one smaller feasible object would not suffice.

Worked Example: Several Thresholds from One Exact Output

Use the graph $G$ from the previous example, with $V=\{1,2,3,4,5\}$ and $E=\{12,13,23,34,35,45\}$. The exact values computed there are $\omega(G)=3$, $\alpha(G)=2$, and $\tau(G)=3$. We test each threshold by substitution into its decision condition.

For Clique with $k=3$, substitute the exact value: $\omega(G)=3\ge3$, so the answer is yes; the clique $\{1,2,3\}$ witnesses it. For Clique with $k=4$, $3\not\ge4$, so the answer is no.

For Independent Set with $k=2$, $\alpha(G)=2\ge2$, so the answer is yes; $\{1,4\}$ is a witness. For Independent Set with $k=3$, $2\not\ge3$, so the answer is no.

For Vertex Cover with $k=3$, $\tau(G)=3\le3$, so the answer is yes; $\{2,3,5\}$ is a witness. For Vertex Cover with $k=2$, $3\not\le2$, so the answer is no.

Check: the direction of the comparison changes for Vertex Cover because its objective is minimized. The same exact cover of size $3$ satisfies the threshold $3$, but the exact minimum value rules out a cover of size $2$.

Longest Cycle and the No-Cycle Case

For Hamiltonian Cycle, an optimizer must specify what it does if there is no cycle. Saying only “return a longest cycle” is incomplete on such an input, because there is no feasible cycle to return. The value convention $L(G)=0$ handles this case, while the optimizer can report that no cycle exists. If at least one cycle exists, the optimizer returns both its length and a cycle attaining that length.

Worked Example: A Hamiltonian Cycle and an Exact Optimum

Let $H=(V,E)$ have $V=\{1,2,3,4,5\}$ and $E=\{12,23,34,45,51,13\}$. The sequence $1,2,3,4,5,1$ is a cycle: its consecutive edges are $12,23,34,45,51$, all of which are in $E$, and its five vertices before returning to $1$ are distinct. Therefore $L(H)\ge5$. Every cycle uses vertices of $H$, which has $|V|=5$, so no cycle can contain more than $5$ vertices. It follows that $L(H)=5$, and the displayed cycle attains it.

Now apply the decision test. The graph has $|V|=5\ge3$, and the optimizer returns $L(H)=5=|V|$. Hence $H$ has a Hamiltonian cycle, witnessed by $1,2,3,4,5,1$.

Check: the witness uses each vertex $1,2,3,4,5$ exactly once before returning to its start, and its five required edges are all listed in $E$. The upper bound of five vertices comes from the order of the graph itself.

Worked Example: An Exact Optimizer Reports No Cycle

Let $P=(V,E)$ have $V=\{1,2,3,4\}$ and $E=\{12,23,34\}$. This is a path. Vertex $1$ has only neighbor $2$, so any cycle containing $1$ would need two distinct neighbors of $1$ on that cycle, which is impossible. A cycle in $P$ would have to contain at least one vertex; if it contained $1$, the preceding argument rules it out. If it did not contain $1$, it would lie in the path on $\{2,3,4\}$, where vertex $2$ has only neighbor $3$, again ruling out a cycle containing $2$; what remains is the single edge $34$, which is not a cycle. Therefore $P$ has no cycle.

By convention, $L(P)=0$, and an exact longest-cycle optimizer reports that no cycle exists. Since $|V|=4\ge3$ but $L(P)=0\ne4$, the Hamiltonian Cycle decision answer is no.

Check: the test does not treat “no returned cycle” as though an optimizer had returned a Hamiltonian one. It uses the specified value $L(P)=0$, which differs from the required value $|V|=4$.

Common Mistakes and Why the Distinction Matters

Wrong calculation: for the first graph, one might say “the optimizer finds a clique of size $3$, so the Clique decision answer is yes for every threshold.” That conclusion ignores the threshold. At $k=4$, the required test is $3\ge4$, which is false, so the answer is no. The correction is to compare the exact optimum with the particular $k$ in the decision instance.

A second error is to use the wrong inequality for Vertex Cover. If the exact minimum cover has size $3$, a threshold of $2$ is not met: the test is $3\le2$, which is false. A cover of size at most $k$ is sought, so the relevant comparison is $\tau(G)\le k$, not $\tau(G)\ge k$.

Finally, an exact optimizer’s mathematical output should not be confused with a guarantee about runtime. An optimizer that returns an exact maximum or minimum gives the optimum needed for the decision test, but that fact alone says nothing about how many computation steps are required to find it. The decision and optimization formulations clarify what is being asked; they do not, by themselves, make the search efficient.

Check Your Understanding

For each question, state the relevant optimum or threshold comparison and justify the answer.

If an exact Clique optimizer returns $\omega(G)=4$, what is the decision answer when $k=4$, and what is it when $k=5$?
Explain why a minimum vertex cover of size $\tau(G)$ yields an independent set of size $|V(G)|-\tau(G)$.
A graph has $6$ vertices and a longest cycle of length $5$. Does it have a Hamiltonian cycle? State the test.
Why must a longest-cycle optimization formulation say what happens when the graph has no cycle?
For a Vertex Cover decision instance with threshold $k$, which comparison with $\tau(G)$ gives a yes answer, and why?