2
$\begingroup$

In the textbook of CLRS, 'ch. 34.2 Polynomial-time verification' it says the following:

Suppose that a friend tells you that a given graph G is hamiltonian, and then offers to prove it by giving you the vertices in order along the hamiltonian cycle. It would certainly be easy enough to verify the proof: simply verify that the provided cycle is hamiltonian by checking whether it is a permutation of the vertices of $V$ and whether each of the consecutive edges along the cycle actually exists in the graph. You could certainly implement this verification algorithm to run in $O(n^2)$ time, where $n$ is the length of the encoding of $G$.

To me, for each consecutive pair $(u,v)$ of the given cycle, we could verify if it's an edge in $G$. Further we could use some color coding for each vertex to ensure we don't revisit a vertex. By doing so, we could verify if the given cycle is Hamiltonian in $O(E)=O(m^2)$ time where $m$ is the number of vertices in $G$. Further we can see the minimum encoding $n$ of $G$ is $m^2=n$. Thus $O(E)=O(m^2)=O(n)$. Can anyone help me understand, why it is mentioned as $O(n^2)$ instead!

$\endgroup$
3
$\begingroup$

The statement in CRLS is not wrong in any case; an algorithm that runs in $O(n)$ time also runs in $O(n^2)$ time. Of course, it would be more precise to state the running time as $O(n)$ if this were true, so why doesn't CLRS do this?

First off, this depends on the encoding chosen for $G$. If an adjacency matrix is used, a graph with $V$ vertices always has an encoding of size $V^2$. However, if an adjacency list encoding is used, we would only need an encoding of size $O(E \log V + V)$.

Your algorithm does indeed run in $O(n)$ time for a dense graph (with $\sim V^2$ edges); does it also run in $O(n)$ time if the graph is sparse ($O(V)$ edges)? In that case, the encoding might be shorter (if an adjacency matrix is used). Is your algorithm still $O(n)$ in that case? If it enumerates over all potential edges or creates and adjacency matrix, it would not be.

CLRS wants to avoid peculiarities with having to implement the algorithm in a particular way or having to specify a specific encoding, which is why they state "you could certainly implement this algorithm to run in $O(n^2)$ time". The "certainly" means "in any case, you can get $O(n^2)$, but it might be possible to do better". In any case, all they care about is that it is polynomial, which both $O(n)$ and $O(n^2)$ are.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.