Let the algorithm be defined as follows:

Consider the following heuristic algorithm for finding the maximum size clique in a graph. (1). Delete from the graph a vertex that is not connected to every other vertex. (2). Repeat (1) until the remaining graph is a clique.

Now, how do I show that this algorithm does not give a solution which is within constant times of the optimal solution? I was reading about heuristic algorithms when I came across this problem. Any sort of input is appreciated.


1 Answer 1


Consider a graph which is the disjoint union of $K_i$ and $K_1$, the isolated vertex.

Let the order of selection of vertices be such that the isolated vertex is last.

Then your heuristic outputs solution 1 for any $i \in \mathbb{N}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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